Cache Hierarchy

A cache hierarchy is the stack of small, fast memories a CPU checks before going to DRAM — typically an L1 of a few dozen kilobytes, a larger L2, and a shared L3. Each level is checked in turn and charges its own latency, so the same load can cost 4 cycles or 250 depending on which level holds the data.

The thing to hold on to is that a cache never moves a word. It moves a line: a fixed run of neighbouring bytes — 64 on x86 and on most ARM cores, 128 on Apple silicon. Think of a courier who only delivers by the crate. You order one screw, and a crate of sixty-four arrives, because the trip is what costs money — the cargo is nearly free. Use every screw in the crate and you paid for one trip. Use one screw per crate and you pay a trip for each.

That is the whole lesson, and it has a consequence people find hard to believe until they measure it. Sum a 2-D array along its rows and you use every word of each line you fetch. Sum the same array down its columns — same elements, same additions, same instruction count — and you fetch a line, take one word out of it, and move on. The arithmetic is identical; the memory traffic is not, and on a large enough array the second version takes several times as long. The cost of a load is not a property of the load. It is a property of the sequence it sits in.

How a Cache Hierarchy Works

This page animates a scale model — 64 words of memory cut into 16 lines of 4 words, an L1 that holds 4 lines, an L2 that holds 8, an L3 that holds all 16, and DRAM behind them. Real numbers are thousands of times bigger. The mechanism is identical, and small enough to watch.

Start with the address. w9 is word 9, and the cache does not care about word 9 as such — it cares that word 9 lives in line #2 (9 // 4), at offset 1 inside it (9 % 4). Those two numbers come from splitting the address into fields: the bottom 2 bits are the offset, the next 2 bits are the index, and whatever is left over is the tag. In hardware the split costs nothing at all — the three fields are just different wires coming off the same address. The // and % notation is a readable description of that fixed wiring, not arithmetic performed by the cache.

The index is the interesting one. It picks which row of L1 this line is allowed to occupy — and a line is allowed exactly one row, in the direct-mapped scheme the default run animates. Line #2 goes in row 10 and nowhere else. That is what makes the lookup fast: there is no searching, just an array subscript. The tag is the leftover high bits, stored alongside the data so the cache can tell which of the four lines that share row 10 is actually sitting there.

Now the lookup: read the row the index points at, and if it is valid and its tag matches, you are done. Otherwise the request goes down to L2, then L3, then DRAM, stopping at the first level that has the line. Whatever level answers hands back the whole line, and on the way home the line is installed in L3, L2 and L1 — evicting whatever was in the L1 row it landed on.

The costs, and this is the part worth memorising as a shape rather than as numbers: a level charges its latency whether or not it has your data, because you had to look. In the model here that is 4 for L1, 12 for L2, 40 for L3, 200 for DRAM. So an L1 hit costs 4, an L2 hit costs 16, an L3 hit costs 56, and a trip to DRAM costs 256 — not 200. Every miss pays for all the searching that failed.

Cache Hierarchy Step by Step

The default run issues twelve loads, w0 through w11, straight down memory in order, against a direct-mapped L1.

Load 1 — w0. Line #0, offset 0. Index 00, tag 00. Row 00 of L1 is empty, so it is a miss, and a compulsory one: nothing has ever loaded this line. L2 does not have it. L3 does not have it. DRAM does, because DRAM has everything. Bill: 4 + 12 + 40 + 200 = 256 cycles. Four words come back together — w0, w1, w2, w3 — and get installed in L3, in L2, and in L1 row 00, which was empty, so nothing is evicted.

Load 2 — w1. Same line #0, offset 1. Index 00 again, tag 00 again. Row 00 is valid and its tag matches. Hit. 4 cycles. Nothing moved, nothing was fetched; the work was done by load 1.

Loads 3 and 4 — w2, w3. Identical story, 4 cycles each. The crate paid for on load 1 had four screws in it and you have now used all four.

Load 5 — w4. Line #1 now, and index 01 — a different row, which is exactly why consecutive lines do not fight each other. Row 01 is empty, so: miss, compulsory, 256 cycles, and w4–w7 arrive.

Loads 6–8 hit that new line at 4 cycles each. Load 9 (w8) opens line #2 for another 256, and loads 10–12 hit it.

Three misses in twelve loads. Not two, not four — three, because there are four words in a line and twelve divided by four is three. This sequential run gets four loads per miss, so its miss rate is one quarter, or 25%. Total: 3 × 256 + 9 × 4 = 804 cycles.

The final beat draws the comparison for you: under the cost ribbon sits a second, ghosted bar, and it is the twelve-load run with a stride of one line instead of one word. Switch the access pattern to stride 4 to watch it happen. Same code, same cache, twelve loads again — but the addresses are w0, w4, w8, … w44, one word taken from each of twelve different lines instead of all four words of three. Every one is a compulsory miss, and the run costs 12 × 256 = 3072 cycles. Twelve loads either way; 3.8× the bill.

That is the column walk from the top of this page, in miniature — with one difference worth naming out loud. In real code the order is what creates the damage: the column walk asks for exactly the same addresses as the row walk, just spread so thin that nothing is still resident by the time it comes back. The model here cannot show you that, because its L3 holds all 64 words, so a fixed set of addresses costs the same number of DRAM trips in any order. It changes the addresses instead. What both versions share is the thing that actually decides the bill — the footprint: how many distinct lines the loads spread across before any of them is reused. Three lines, and the cache holds them all. Twelve, and it holds none of them long enough to matter.

Why a Miss Is Not One Price

Lumping every miss together is the most common way to reason wrongly about cache behaviour, so the model here keeps three levels specifically to break that habit.

Run the conflict pattern: ten loads alternating between w0 and w16, forever. Line #0 has index 00. Line #4 also has index 00, because 4 % 4 is 0. They are the only two lines in play, L1 has four rows, and three of those rows sit empty for the entire run — and yet not one load after the first two is an L1 hit, because both lines are only permitted in row 00 and they evict each other on every single access.

But look at what those misses cost: 16 cycles, not 256. The line was thrown out of L1; it was not thrown out of the machine. L2 still had it, one level down and 16 cycles away. This is half of why a cache hierarchy has more than one level. The other half is plain capacity — the working-set run below spills out of L1 and L2 and lands on L3 — but this half is the one people forget, because it is invisible in a hit-rate number: the common kind of miss never reaches DRAM at all.

Misses come in three flavours, and the animation labels each one on its ledger chip:

• Compulsory — the line has never been touched. Nothing but prefetching avoids these.
• Conflict — the line was evicted by another line that maps to the same set, and a fully associative cache of the same size would have kept it.
• Capacity — there is genuinely not enough room, and a fully associative cache would have missed too.

Those labels are earned, not asserted: the simulation runs a fully associative twin of L1 alongside the real one and classifies each miss by what the twin would have done.

Conflict misses have a direct fix. Switch the mapping to 2-way, and L1's four lines become two sets of two ways. The index shrinks to one bit, the tag grows to three, and a line now has two places it is allowed to live. Run the conflict pattern again: same ten loads, same four lines of capacity, and the L1 hit rate goes from 0/10 to 8/10. Nothing got bigger. The address just gained a second option.

Which is a good place to say what you actually control. Associativity, line size and level count are the hardware's choices, not yours. Yours are the layout — what sits next to what — and the order you walk it in, and those two decide the footprint that everything above turns into cycles.

The working set pattern shows the failure the second way cannot fix: ten lines cycled twice through caches that hold four and eight. Every revisit in the second pass misses at L1 and at L2, and lands on L3 at 56 cycles — because LRU, faced with a loop longer than the cache, evicts each line before the loop comes back to it. That is not a bug in LRU. It is LRU behaving as designed on the one access pattern it is worst at, which is a good reason real caches often use something closer to random replacement.

Edge Cases

• The first demand for a line is a compulsory miss unless something fetched it first. Touching w1 for the first time can hit because an earlier load of w0 brought in their shared line; hardware prefetching can do the same before either address is requested. A benchmark that forgets to warm up often measures these cold-line effects instead of the steady state it meant to measure.
• The same address twice avoids another lower-level fetch. Load w5 eight times and you pay 256 once and 4 seven times. Repetition is the cheapest locality there is.
• A set can be full while the cache is nearly empty. The conflict run keeps three of four L1 rows unoccupied and still thrashes. Free capacity is not availability.
• Even a slightly oversized cyclic working set loses all reuse. Ten lines through an eight-line cache under LRU miss on every revisit, because each line is evicted before the loop comes back to it. Two lines too many does no better than twenty.
• Not every miss reaches DRAM. In this model L3 holds the whole 64-word memory, so once a line has been touched, DRAM is never paid for it again. In a real machine the same holds only while your working set fits in L3; past that, the compulsory-looking 250-cycle misses come back.

Common Mistakes

• Assuming capacity alone describes conflict behavior. More capacity can change the index mapping and remove a particular conflict, but free rows do not help two lines restricted to the same set. In this lesson, switching to two ways fixes the conflict without increasing total capacity.
• Believing a miss costs the DRAM latency. It costs the DRAM latency plus every level you searched on the way — 256, not 200, in this model. Real hardware can overlap work and reports latency using different boundaries, so these additive numbers must not be assumed to describe every processor.
• Counting loads instead of lines. The performance question is never "how many array elements did I read", it is "how many distinct lines did I touch, and how much of each one did I use". Two loops with identical iteration counts can differ by an order of magnitude on that second question.
• Thinking the index should be the high bits of the address. This model uses the middle bits; real caches may use hashed or other indexing schemes. In this conventional layout, the index's job is to spread neighbouring lines across different sets, and neighbouring lines are precisely what a program touches together. Index on the high bits and lines #0 through #3 all land in set 0, so a loop over those four lines thrashes in set 0 while the other sets sit idle.
• Treating the line as an implementation detail. It is the mechanism by which nearby addresses become speed. A cache that fetched single words, with the same data capacity, would miss on all twelve distinct words of the default run instead of three; repeated words could still hit while resident.
• Reading a struct field and assuming you paid for a field. You paid for the line it sits in. That is why packing hot fields together, and keeping a lock on its own line away from the data it protects, are real optimisations rather than superstition.

A Note on Simplification

This is a teaching model, not a simulator, and it leaves out machinery that matters in production. Real lines are 64 bytes on x86 and most ARM cores and 128 on Apple silicon, not 4 words; real tags are around 40 bits, not 2. Real caches probe tag and data arrays in parallel, overlap misses through miss-status registers instead of stalling, and prefetch aggressively enough that a clean sequential stride often misses far less than the model here suggests. Nothing on this page models writes at all — no dirty bits, no write-back versus write-through, no write allocation — and nothing models virtual addressing, the TLB, or the coherence traffic that appears the moment a second core touches the same line. L2 and L3 are modelled as fully associative with LRU, which real ones are not.

Use this to build the mental model, then measure your own machine before you trust any number to two significant figures. The smallest useful experiment is the one from the top of this page — write the row walk and the column walk over the same array, then run each under a counter:

perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk row
perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk col

Same load count on both lines, and a miss count that is not close. On macOS, xctrace record --template 'CPU Counters' gets you there; valgrind --tool=cachegrind --cache-sim=yes provides a simulated cache profile on supported platforms without hardware counters, with substantial execution overhead. Tool and event availability depends on the operating system and processor.