Cache Hierarchy
Memory Fundamentals · Memory & Systems track
6 min read
In this module
The Speed Problem
Modern CPUs run billions of operations a second; main memory (DRAM) can't keep up. A single RAM access takes somewhere between 50 and 100 nanoseconds, and a 3 GHz processor could have ripped through 150 to 300 useful cycles in that gap. If the CPU had to wait on RAM for every memory reference it would spend most of its life twiddling its thumbs.
Cache is the answer. You park small amounts of very fast memory between the CPU and main RAM, and the CPU can usually find what it needs there.
L1, L2, and L3
Cache is organised in levels, each one trading capacity against speed:
| Level | Typical Size | Latency | Location |
|---|---|---|---|
| L1 | 32-64 KB per core | ~1 ns | Inside each CPU core |
| L2 | 256 KB-1 MB per core | ~3-5 ns | Per core, on chip |
| L3 | 4-64 MB shared | ~10-20 ns | Shared across all cores |
When the CPU needs data it checks L1 first, then L2, then L3, then ultimately main memory. Finding what you wanted in cache is a cache hit. Striking out across every level and falling through to RAM is a cache miss.
Cache is a small, fast memory that sits between the CPU and RAM. It is organised in levels (L1, L2, L3) where each level is larger but slower. A cache hit finds data in cache; a cache miss forces a slower trip to main memory.
Why Caching Works: Locality
Cache works because real programmes touch memory in predictable patterns, not at random:
- Temporal locality: if you used a piece of data recently, odds are good you'll use it again soon. The loop counter you read every iteration is the canonical example.
- Spatial locality: if you touched one address, you'll probably touch nearby addresses next. Iterating an array one element at a time is the obvious case.
On a cache miss the system doesn't just grab the byte you asked for. It loads an entire cache line, usually 64 bytes, scooping up the neighbours along the way. That's spatial locality being cashed in: the next several accesses tend to hit data that's already in the cache.
Worked Example: Counting Misses
Take an array of one million ints, 4 bytes each, so 4 MB in total. Assume none of it is cached yet and lines are 64 bytes. Every line holds 16 ints.
Loop 1: sum every element in order. The first access to each line misses and drags in all 16 of its ints, then the next 15 accesses hit. One million accesses, roughly 62,500 misses: one in sixteen.
Loop 2: sum every sixteenth element (i += 16). Now every access lands in a different line, and nothing you load gets reused. 62,500 accesses, roughly 62,500 misses: every single one.
Loop 2 does one sixteenth of the arithmetic and makes the same number of trips to RAM. On real hardware it doesn't come close to running sixteen times faster, because those trips to memory were most of the cost all along. Hardware prefetchers soften this for simple, predictable strides, but the principle holds: you pay per line, not per byte.
You can run a shrunk-down copy of both loops on the simulators below. To keep the display readable, this cache has 16-byte lines instead of 64, so each line holds four ints and the ratios become one in four rather than one in sixteen. The first simulator reads 16 ints in order (byte addresses 0, 4, 8 and so on). Press Run and count: 4 misses, 12 hits.
Cache Contents(Direct-Mapped, 8 lines, 16B/line)
| Index | V | Tag | Data |
|---|---|---|---|
| 0 | 0 | - | - |
| 1 | 0 | - | - |
| 2 | 0 | - | - |
| 3 | 0 | - | - |
| 4 | 0 | - | - |
| 5 | 0 | - | - |
| 6 | 0 | - | - |
| 7 | 0 | - | - |
The second reads every fourth int, so each address is 16 bytes past the last and lands in a fresh line. Same 16 reads, 16 misses.
Cache Contents(Direct-Mapped, 8 lines, 16B/line)
| Index | V | Tag | Data |
|---|---|---|---|
| 0 | 0 | - | - |
| 1 | 0 | - | - |
| 2 | 0 | - | - |
| 3 | 0 | - | - |
| 4 | 0 | - | - |
| 5 | 0 | - | - |
| 6 | 0 | - | - |
| 7 | 0 | - | - |
The same effect bites two-dimensional arrays. C stores int grid[1024][1024] row by row, so grid[r][c] and grid[r][c+1] are neighbours, but grid[r][c] and grid[r+1][c] are 4 KB apart. Walk it row by row and you get the one-in-sixteen pattern. Walk it column by column and every access can miss.
Predict: an array of 16-byte structs, read in order from start to finish. Roughly what fraction of accesses miss?
About one in four. A 64-byte line holds four 16-byte structs, so each miss brings in that struct and the next three. Bigger elements mean fewer per line and more misses, which is why shrinking a hot struct can speed up code that never changed its algorithm.
Cache Performance Matters
The gap between cache-friendly and cache-hostile code is enormous. Walking an array in order (good spatial locality) can run 10 to 100 times faster than the same logic with random memory access patterns. That's why an intuition for cache behaviour pays off even when you never deal with cache hardware directly.
You can watch the worked example happen. This program sums a 32 MB array three ways: every element in order, every sixteenth element, and the same number of reads at random positions.
Read the last column. The runner compiles without optimisation, so most of the sequential loop's cost is loop overhead, and the stride-16 loop should still take well over a sixteenth of its time, because it pulls in every cache line the sequential loop did. The random reads cost the most per access, since the prefetcher can't guess where the next one lands. Exact figures depend on whichever machine picks up the job and wobble from run to run; the ratios are the part to look at.
It also matters for security, in a way that surprised the industry. Whether a load hits or misses is visible in its timing, and timing can be measured. Spectre and Meltdown both use cache hits and misses as a side channel to read memory they had no right to see. You'll get there in CPU Pipeline & Microarchitecture and Side-Channel Attacks.
Curious what the machine running your code actually has? On Linux, glibc will tell you through sysconf:
Inside a virtual machine some of these can come back as zero or "not reported", because the hypervisor decides what the guest is told about its CPU. And if the L3 turns out to be 32 MB or more, part of the benchmark's array fits in it, which flatters the random reads.