Part 4 · Where the fictions break
The memory hierarchy
Fiction three. One `mov` instruction, two orders of magnitude of cost — and this is the fiction that dominates real programs.
What this lesson is trying to break (3)
- A memory access costs a memory access.
- Optimising means reducing instruction count.
- A linked list and an array with the same number of elements do comparable work.
This is a threshold concept: troublesome, transformative, and irreversible. You should expect to be genuinely stuck here, and being stuck is the mechanism rather than a sign that you are failing. Budget several sessions. Do not move on because you are bored — move on when you can explain it out loud without notes.
Reading a value from memory costs a memory read. It may be slower than arithmetic, but it is one operation with one cost, and you count them the same way you count everything else.
The same mov instruction, on the same machine, can take
4 cycles or 300, depending only on where the data happens to
be at that moment. It is not a property of the instruction. Nothing in the
listing tells you which case you are in.
Read every memory access as a lottery ticket on the cache hierarchy. And accept the consequence: for most real programs, where your data is matters more than how many instructions you execute. This is the fiction whose collapse changes the most.
The numbers
Approximate, and the ratios matter far more than the values:
| Level | Latency | Typical size |
|---|---|---|
| register | 0 | ~16 |
| L1 cache | ~4–5 cycles | 32–128 KB |
| L2 cache | ~12–15 cycles | 0.5–4 MB |
| L3 cache | ~40 cycles | 8–64 MB, shared |
| main memory | ~200–300 cycles | GBs |
An L1 hit and a DRAM access differ by roughly 50×. In the time one main-memory access completes, the core could have executed several hundred independent arithmetic instructions.
Which reframes optimisation entirely: arithmetic is nearly free and memory is expensive. Trading three multiplies to avoid one cache miss is a good deal, and that is the opposite of how instruction counting would advise you.
You cannot load one byte
Memory moves in cache lines — 64 bytes on x86-64 and on your M1. Ask for one byte and you get all 64, and they occupy a line’s worth of cache.
Two consequences that explain most real performance differences:
Nearby data is free. Having paid for the line, the next 63 bytes cost nothing.
Sequential access gets ~16 ints per miss.
Scattered data wastes almost everything. Touching one int from each of many
lines pays a full miss per element and fills your cache with 60 bytes of unwanted
data each time.
This is why 3.5’s padding lesson matters beyond size: a 24-byte struct fits 2 per line with 16 bytes wasted; a 16-byte one fits 4 exactly.
Both sum a million integers. Same count, same arithmetic.
// A — array
long a(const int *v, int n) { long s=0; for (int i=0;i<n;i++) s+=v[i]; return s; }
// B — linked list, nodes allocated separately in random order
struct Node { int val; struct Node *next; };
long b(struct Node *h) { long s=0; while (h) { s+=h->val; h=h->next; } return s; }A is commonly 10× faster or more, and neither instruction count nor llvm-mca
would tell you.
Three separate effects stack up against B:
Line utilisation. A gets 16 ints per 64-byte line. B’s nodes are 16 bytes
and scattered, so each line delivers one useful val and 60 wasted bytes.
Prefetching. The hardware prefetcher detects sequential strides and fetches ahead, so A’s misses are hidden. B’s addresses are unpredictable, so nothing can be prefetched and every access pays full latency.
Dependency chain. This is the worst one. h = h->next means you cannot compute
the next address until the current load completes. So B is a chain of
full-latency memory accesses — 4.1 meeting
fiction 3. A’s loads are independent, so dozens are in flight at once.
That third point is why pointer chasing is a named performance anti-pattern. It converts memory latency, which is normally hideable by overlapping, into a serial dependency that cannot be hidden at all.
And it is the honest justification for the arena-and-indices pattern the Rust course recommended in its escape-hatches lesson: an arena is contiguous, so it is prefetchable, and indices are computed rather than loaded.
False sharing
The multithreaded failure mode, and it produces genuinely baffling numbers.
struct { long counter; } counters[4]; // 8 bytes each — all in ONE cache lineFour threads each increment their own counter. No shared data, no locks needed, no race. And it can be slower than a single thread, because a cache line can only be held for writing by one core at a time. The line ping-pongs between cores on every increment.
The fix is padding to a cache line each:
struct { long counter; char pad[56]; } counters[4];Wasteful of memory, dramatically faster. In Rust, crossbeam’s CachePadded
does this for you.
False sharing is the reason a parallel version can be slower than serial with no lock contention anywhere. When someone reports that, this is the first thing to check.
A colleague has optimised a hot loop from 20 instructions per element to 12, and measured no improvement at all.
Give the most likely explanation, and name the two measurements you would ask for to confirm it. One of them is a profiler counter, not a timing.
What you should now be able to say
- The same load costs ~4 to ~300 cycles. Nothing in the listing says which.
- Arithmetic is nearly free; memory is expensive. Trading instructions for locality is usually right.
- Memory moves in 64-byte lines — nearby data is free, scattered data wastes most of every transfer.
- Pointer chasing serialises memory latency and defeats prefetching, which is why linked structures lose badly to contiguous ones.
- False sharing makes correct, lock-free parallel code slower than serial.