Memory Hierarchy Primer

Our curl process holds a URL string somewhere in memory. Reading its first byte is one instruction, identical whichever rung answers it; what changes is the wait. Every number here is one machine: an Intel Golden Cove core at 3.2 GHz, 48 KB L1d, 1.25 MB L2, 30 MB L3, dual-channel DDR5-6400.

Seven places can hold that byte, and which one answers decides everything. Drag the slider down the rungs — the bar beside the rung that answers is its latency on a log axis, and the readout gives the same number in cycles:

Notice where the spread actually lives. The four rungs inside the chip cover 0.31 ns to 15.6 ns — a factor of fifty across the whole core. Then one step to DRAM, and one much larger step to storage. Rescaled so an L1 hit takes one second, DRAM is fifty seconds away and the disk is seventy-two days.

Folklore says each step down the hierarchy costs about 100×. That is worth checking rather than repeating: put the faster rung and the slower rung on the two sliders and read the ratio between them:

The folklore is far too big inside the chip and far too small outside it. L2 over L1 is 2.9×, L3 over L2 is 3.3×, DRAM over L3 is 5.1× — a gentle ramp. Then DRAM to SSD is 1,250× in a single step. This is not a staircase; it is a ramp with a cliff at the end of it.

A latency only means something next to the work it displaces. While a load is outstanding the core keeps issuing whatever it can find, and the issue slots it cannot fill are the real bill. Drag the load's latency and watch the slots go:

At 80 ns the core has burned 256 cycles and 768 instruction slots at three per cycle. Out-of-order execution recovers whatever independent work happens to sit in the scheduling window — a few dozen instructions, not eight hundred — which is why memory-bound loops run below one instruction per cycle on a core that sustains three on data it already has.

The core does not wait for one miss at a time. It has ten line-fill buffers, so up to ten misses can be in flight at once, and Little's law turns that count directly into bandwidth. Raise the number in flight:

Ten misses of 64 bytes each, one batch every 80 ns, is 8.0 GB/s — 7.8% of what two DDR5-6400 channels deliver. A single core cannot saturate this machine's memory system; it takes roughly a dozen of them. That asymmetry is why a single-threaded microbenchmark and a loaded server disagree about what memory costs.

They disagree in the direction nobody plans for. As the cores together approach the peak the channels can serve, requests start queueing behind each other, and the latency each core sees stops being a constant:

Watch the curve leave the 80 ns line long before the bus is full. At 80% of peak the wait is 160 ns; at 95% it is 460 ns. The number printed in every latency table is an idle number, measured on a quiet machine, and it is the number least likely to describe production.

The honest cost is not "80 ns". The rest of this page is about not paying it.

The explanation people reach for first is the speed of light, and it is the wrong one. A signal crosses copper at roughly 15 cm per nanosecond, so distance does put a floor under every access — worth measuring before blaming.

Drag the memory block away from the ALU. The marks are the edge of the die, the edge of the package, and a DIMM slot on the far side of the board; the readout is the round trip that distance alone costs:

Notice how little it buys. Sixty millimetres out and back is 0.80 ns — 2.6 cycles. DRAM answers in 80 ns, a hundred times that. Distance sets the floor and nothing more; the rest of the wait happens inside the memory array itself.

That is where the two technologies part. An SRAM cell is six transistors wired into a latch that holds its own state. A DRAM cell is one transistor and one capacitor, and the charge on that capacitor leaks away. Drag time forward from the last refresh:

Past 64 ms the charge falls under the sense threshold and the bit is gone, so DDR4 refreshes every row inside that window — 8,192 refresh commands, one every 7.8 µs. Reading the cell drains it too, so every read is followed by a write-back. That sequence, not the wire, is the 80 ns.

The payoff for all that fragility is density, and density is price. One bit costs six transistors in SRAM and one-and-a-bit in DRAM, and the gap compounds through the whole supply chain. Slide the capacity you want up and watch which rows stay buyable:

At one terabyte, the disk costs $15 and the SRAM costs $409,600 — a factor of 26,667 for the same bytes. A machine with a terabyte of cache-grade SRAM is not slow or hot; it is simply not a product anyone would buy.

Suppose the money were free. You still could not build it, because a bigger array is a slower array: longer word lines, more sense amplifiers, a deeper decoder. Drag the capacity of the cache up and read the access latency off the curve:

Watch the curve pass through the three measured points on this core. A 1 MB L1 would answer in 14.6 cycles — which is what L2 already costs. There is no such thing as a large fast cache: build one and you have built the next level down and given it the wrong name.

So the levels get stacked, and stacking raises a question of its own: when a line sits in L2, does L3 keep a copy? Switch the policy and slide the core count — what the stack can hold against what it spends on duplicates:

An inclusive L3 makes coherence cheap: a snoop that misses in L3 provably misses in every L2 above it. It pays with capacity — at eight cores, 10 MB of a 30 MB L3 holds nothing but copies. Exclusive designs get 40 MB and broadcast instead.

64 bytes has been the x86 line size since the Pentium 4, and it is what Arm's Cortex and Neoverse cores use — it is the size this tape draws.

Drag the word being read along the tape. Each cell is an eight-byte word, the bracket above marks the line that contains it, and the outlined cells are the bytes that come along uninvited:

Notice that the cost does not change as you move. One word or the next, the transaction is the same 64 bytes and the same 80 ns; the only thing under your control is how much of it you use. That is the whole content of the phrase "spatial locality".

That 64 is not universal, which matters the moment you pad for it: IBM POWER and Apple silicon both move 128, so sysctl hw.cachelinesize answers 128 on an M-series Mac and 64 on the Intel one beside it. Padding a struct to 64 to keep two cores off one line therefore buys nothing on half the machines it will run on — HotSpot pads @Contended fields to 128. Either number is the same compromise between tag storage per useful byte and data nobody asked for.

A loop that walks memory at a stride decides that ratio directly. Set the stride between elements and read the gauge — it is the fraction of every fetched line the program actually touches:

As soon as the stride reaches 64 bytes, every four-byte element sits on its own line: 4 of every 64 bytes used, 6.3%, and sixteen times the memory traffic for the same answer. Past 128 the picture stops getting worse, because it cannot — one line per element is the floor.

Which slot the line lands in is decided by the address itself, split into three fields with no arithmetic beyond a shift and a mask. Drag the address, then change the capacity and watch the boundary between index and tag move:

The bottom six bits are the offset — which byte inside the line — and never reach the cache at all. The next bits are the index, and they alone choose the set. Two addresses that agree on those bits compete for one set no matter how far apart they are in memory.

A set holds more than one line, and how many is the associativity. Here eight hot lines all index to the same set, and the loop walks them in a cycle. Raise the ways per set:

Watch the miss rate fall off a cliff rather than a slope. At seven ways every pass evicts the line the loop is about to want; at eight, all eight lines stay resident and the miss rate is zero. Capacity is not the question — the set was never full in bytes, only in ways.

That cliff has a policy behind it. When a set is full something must go, and the choice is the difference between a working set that fits and one that thrashes. Switch the policy and add one more hot line than the set has ways:

At nine lines in an eight-way set, LRU misses on every single access — it evicts the line that is next in the cycle, every time. FIFO does the same. Random, which cannot be that unlucky repeatedly, misses 23%.

Real caches use neither: exact LRU order costs log₂(N!) bits per set, so hardware approximates it with a tree of bits or one not-recently-used bit per line — which softens the pathology without removing it.

The temporal half has a measurable shape: reuse distance, the number of distinct lines touched between two uses of the same line. A cache of capacity C turns every access under C into a hit, and nothing else.

Below is the distance histogram of one 96-access trace. Drag the capacity cut right — left of it is a hit, right of it a miss, and the far column is each line's first touch:

Notice how uneven the return is. The first four lines of capacity buy 44% of the accesses; going from twelve to sixteen buys nothing at all, because there is nothing left in that range. Cache sizing is a curve with a knee, and the knee is a property of the program, not of the hardware.

The spatial half is decided by the order the loop visits memory. A C array M[N][N] stores M[i][j] beside M[i][j+1]; here each row is exactly one line. Step the walk, then switch the iteration order:

Watch the line column on the left. Row-major, eight elements cost one line; column-major, the same eight cost eight. On a 4096×4096 matrix of doubles that is 2,097,152 lines against 16,777,216 — eight times the traffic for byte-identical arithmetic. Fortran stores column-major, so the same loop nest is correct there and wrong here.

The same argument applies inside a record. A particle with position, velocity and colour is nine floats; an update step that reads position and velocity needs six of them. Slide how many fields the loop reads, then switch the layout:

As soon as the loop reads fewer than all nine, the array-of-structs layout moves 36 bytes per particle to use 24, and a third of the bandwidth is spent on colour nobody asked for. The struct-of-arrays layout moves exactly what it reads, and each field array vectorises without a gather.

Both effects compound into one curve. Below, the same region is walked twice: once in address order, once as a dependent chain of pointers into it. Drag the size of the region from 4 KB to 1 GB:

The sequential sweep barely moves: it stays under a nanosecond per element everywhere, because sixteen elements share a line and ten lines are in flight at once. The chase climbs to 103 ns per step at a gigabyte — 211× — while executing the same number of instructions.

The sequential curve stays flat because hardware is helping. After two consecutive lines a stream prefetcher locks on and issues loads eight lines ahead of the program. Drag the read along the tape, then switch the walk to random order:

In sequential order the lines ahead of the readare already on their way and the demand load hits. In random order there is no stride to detect, the stream never forms, and every read pays the full 80 ns. This is the mechanical reason a vector beats a linked list at identical asymptotic complexity.

Which makes fanout, not depth, the thing to optimise in a search structure. A binary tree costs one line per level; a B-tree node fills a whole line or page and compares all of it. Set the node size and the number of keys:

With 4 KB nodes and 16-byte keys the fanout is 256, so a billion keys are four fetches deep instead of thirty. Both are O(log n); the base of the logarithm is set by the transfer unit.

Start with the invariant the whole hierarchy runs on. At every access the line is held by some level, and the cost is the latency of the smallest level holding it. Miss rates are the distribution over which level that is.

For uniform random access over a working set of W bytes, a cache of C bytes hits at exactly C/W once W exceeds C. Drag the working set across the three capacities and read the mean off the curve:

At 30 MB — exactly L3 — the mean access is 15.1 ns. At 60 MB it is 47.6 ns. Nothing changed in the program: the same loop, the same instruction count, three times the wall-clock. This is the working-set cliff, and the only warning it gives is the number itself.

The curve is not magic; it is one nested expression. Average memory access time is the L1 hit time plus, for the fraction that miss, the L2 time, plus for the fraction that miss again, the L3 time, and so on. Drag the L1 miss rate and the L3 miss rate:

Because every term is multiplied by the miss rates above it, the deepest term is the most leveraged: at 30 L1 misses per thousand, doubling the L3 miss rate from 20% to 40% moves the average from 2.1 ns to 2.3 ns — on every access in the program. That is the whole argument for measuring LLC-load-misses rather than guessing.

There is a second cache that fails the same way and is much easier to overlook. Every access is also translated, and the TLB caches those translations: 1,536 entries on this core. Slide the working set, then change the page size:

With 4 KB pages that is 6 MB of reach — not the 256 MB the folklore quotes — so a 30 MB working set sends 80% of its accesses through a page walk before the data access even begins. Switching to 2 MB pages multiplies the reach by 512 and the whole working set fits inside it.

The last cliff is the one that catches good engineers, because the code looks right. A column walk down a matrix whose rows are a power of two apart lands every row in one set. Slide the padding per row from zero:

At zero padding all 64 rows index to one set of 8 ways, so every pass re-misses all 64. One line of padding spreads the walk across all 64 sets and the misses go to zero, for an array 1.6% larger.

double M[512][512];      /* 4096 B rows: every  */
                         /* M[i][0] hits set 0  */

double M[512][512 + 8];  /* +64 B: the column   */
                         /* now covers 64 sets  */

None of the three announces itself: no exception, no log line, no failed assertion — just the right answer, twenty times slower, on inputs large enough to matter.

Under 48 KB the answer is L1 and the mean is 1.6 ns. Past 30 MB DRAM answers the majority and the mean heads for 80. The useful reading is not the endpoint but the share: the moment DRAM answers more than a few percent of accesses, that term dominates the average and everything else is rounding.

Each is the same trade in a different costume: something the loop does not read is riding along with something it does. A linked list moves 64 bytes to use 8; an array of pointers pays two lines per object; chaining pays a line per probe.

The fourth is invisible in review because the byte counts are correct. Confirm any of them with perf stat -e cache-misses,LLC-load-misses,dTLB-load-misses before changing code, and again after.