The CPU Cache Hierarchy

Module 1 made one claim on faith. It said a std::vector scan is fast because the next MarketUpdate is already close, and a std::list walk is slow because each node forces a fresh fetch. It never said how far away "close" and "far" really are, or what a fetch costs. This module opens the machine and puts numbers on the claim, and the first number is the one the rest of the module leans on: the distance, measured in time, between the CPU and the data it wants.

That distance is not a single value. What a program calls "memory" is really a stack of levels, each one bigger and slower than the level above it. Understanding the shape of that stack is what turns Module 1's locality rules from folklore into arithmetic you can do in an interview.

The hierarchy

The CPU can only do arithmetic on data sitting in a register, one of the few dozen tiny on-chip slots you met when threads shared a counter. Registers are as fast as the machine gets and there are almost none of them, far too few to hold a market-data feed. Everything else lives further away, and the hardware bridges the gap with a series of caches: small, fast copies of memory that sit between the registers and main memory.

There are three of them on a typical CPU. L1 is tiny and almost as fast as a register. L2 is larger and a few times slower. L3 is larger still, shared across cores, and slower again. Below all of them is DRAM, the main memory the allocator hands out, measured in gigabytes and slower than L1 by roughly two orders of magnitude. The rule that makes it a hierarchy is simple: each level down holds more and answers slower.

Real figures depend on the chip, but the ratios are stable enough to reason with. Counting in cycles, where one cycle is a single tick of the CPU clock and well under a nanosecond on a modern part, an L1 hit costs a handful of cycles, L2 a few times that, L3 several times more, and a trip to DRAM runs into the hundreds. The runner below measures these on real hardware; the point to carry is the shape, not the exact numbers.

A load checks each level top to bottom. Every miss falls to the next, slower level, and the deepest fall is the most expensive.

What a cache miss actually costs

When the CPU needs a value, it asks L1 first. If the line is there, that is a cache hit, and the value is back in a few cycles. If it is not, that is a cache miss, and the request drops to L2, then to L3, then to DRAM, stopping at the first level that has it. A miss is not a small penalty added to a hit. It is a walk down the levels, and each level it has to visit adds that level's latency to the bill. A load that misses everything and goes all the way to DRAM pays the full main-memory price.

What actually moves between the levels is the cache line from Module 1: a 64-byte block, never a single byte. When you touch one MarketUpdate, the hardware pulls the whole 64-byte line containing it up through the levels, which is exactly why the neighbor sitting in the same line is nearly free to read next. Module 1's "fetch cost" now has a precise meaning. It was the cost of a miss, and how much it cost depended on how far down the hierarchy the miss had to travel.

This is why one bad access pattern can wreck a loop whose Big-O looks fine. An O(n) walk over data that lives in L1 and an O(n) walk over data scattered across DRAM do the same number of steps and cost wildly different amounts, because one pays L1 latency per line and the other pays DRAM latency per line. The asymptotics are identical. The wall-clock is not close.

The program below measures the hierarchy directly. It chases a pointer through a randomly shuffled cycle, so each read depends on the one before it and the hardware cannot guess ahead, then it grows the working set from a few kilobytes to tens of megabytes. Run it and watch the time per access climb in steps: each step is the moment the data outgrew one level and fell into the next.

Keeping the working set in a fast level

Caches exist because of a gap that opened up over decades: CPUs got dramatically faster while main memory barely budged, so a modern core can execute hundreds of instructions in the time one DRAM access takes. The whole point of the hierarchy is to hide that gap by keeping the data you are about to touch in a level close to the core. When the data you reuse fits in L1 or L2, the gap disappears and the core runs flat out. When your working set, the memory a loop actively touches, spills past L3 into DRAM, the core spends most of its time waiting.

That single idea reframes the whole of Module 1. A std::vector<MarketUpdate> wins because its elements share 64-byte lines that stream up into L1 as you scan, so most reads are hits and the working set stays compact. A std::list<MarketUpdate> loses because its nodes are scattered across the heap, so each step risks a fresh miss down to DRAM, and a million nodes never fit in a fast level. Two MarketUpdate structs to a line, an array of them streaming through L1: that is what "designed for locality" cashes out to. The container was never the point. Where its bytes land in the hierarchy was.

The interview move is to stop treating memory as one flat thing. When you read a hot loop, ask which level its working set lives in. A few kilobytes of hot state reused every iteration lives in L1 and is effectively free to reach. A scan over hundreds of megabytes pays DRAM latency on nearly every line and no cleverness in the loop body will hide it. Same Big-O, different hierarchy level, and the hierarchy level is what you feel.

In interviews

• "Why does a cache miss cost so much more than a hit?" → "A hit is a few cycles in L1. A miss walks down to L2, L3, then DRAM, paying each level it visits. A full trip to main memory runs on the order of a hundred times an L1 hit."
• "What's the memory hierarchy?" → "Registers, then L1, L2, L3 caches, then DRAM. Each level down is bigger and slower. The CPU computes on registers and the caches hold hot copies to hide main-memory latency."
• "How do you make a hot loop cache-friendly?" → "Keep the working set small enough to live in a fast level, and lay data out contiguously so each 64-byte line carries the next thing you'll use. That's why a vector scan beats a list walk with the same Big-O."
• "What is the working set?" → "The memory a loop actively touches. If it fits in L1 or L2, the core runs flat out; if it spills to DRAM, the core spends most of its time waiting on memory."

Next: what happens when two cores each keep a copy of the same cache line and one of them writes to it. That is the cache-coherency problem, and it is the machinery behind the contended-atomic cost Module 4 kept pointing at.