The Memory Hierarchy — Fast Is Small, Big Is Slow
In one line
Since you cannot build memory that is fast, large, and cheap all at once, you stack it in layers from small and fast to large and slow, and pull frequently used data up to the upper layers.
Why this was needed
Registers run at the same speed as the CPU, but there are only a few dozen of them. DRAM can hold tens of gigabytes, but an access takes hundreds of cycles. This gap, far from narrowing, has widened with each generation. Increasing execution units is a matter of putting in more transistors, but the ability to carry data in and out of the chip is tied to the physical limits of pin counts and wiring.
This accumulated gap is called the memory wall. A hierarchy is the only realistic way around this wall.
How it works
The typical hierarchy and its approximate latencies are as follows. The numbers differ with each generation, but the difference in orders of magnitude is the point.
| Level | Size | Access latency (approximate) |
|---|---|---|
| Registers | Hundreds of bytes | Less than 1 cycle |
| L1 cache | 32–64KB | 4–5 cycles |
| L2 cache | 0.5–2MB | 12–20 cycles |
| L3 cache | Tens of MB | 40–70 cycles |
| DRAM | Tens of GB | 200–300 cycles |
| NVMe SSD | Several TB | Tens of thousands of cycles |
The reason this structure actually works is that programs have locality.
- Temporal locality — data that was used once is likely to be used again soon. Loop variables are like this.
- Spatial locality — if one address is used, the addresses near it are likely to be used soon. Array traversal is like this.
The cache exploits exactly these two properties. It does not fetch data one byte at a time but fetches a whole cache line, normally 64 bytes. Even if you read one 4-byte integer, the 15 neighbors come up with it. This is why code that walks an array in order is fast.
If you divide cache misses into three kinds, the responses differ.
- Compulsory miss — data accessed for the first time. Only prefetching mitigates it.
- Capacity miss — the working set is larger than the cache and gets pushed out. You have to change the algorithm or data structure.
- Conflict miss — entries crowd into the same set and get pushed out. It happens easily when the array stride is a multiple of the cache size.
What you see in the field
If you traverse a two-dimensional array stored in row-major order in column-major order, the same operation becomes several to dozens of times slower. This is because every access fetches a new cache line, uses only 4 bytes of it, and discards the rest. The reason tiling (blocking) is used in matrix multiplication is the same. It cuts the working set down to a size that fits in the cache to increase reuse.
In AI workloads the problem shows up even more plainly. The decoding stage of LLM inference reads a huge set of weights once, multiplies them by a small input, and discards them. The arithmetic intensity (operations performed per byte fetched) is extremely low, so the compute units are mostly idle and memory bandwidth determines performance. This is what lies behind the common complaint that GPU utilization never exceeds 30 percent. Buying a more expensive compute chip here only spends money; the answer is to reduce the bytes you read (quantization) or to increase reuse.
What to check in the quiz that follows
Check whether you can explain why the cache line moves 64 bytes at a time, and why the same algorithm becomes several times slower when only the access order changes.