Caches and the memory hierarchy

A modern core can finish several instructions per nanosecond. Main memory needs something like 60 to 100 nanoseconds to answer a read. If every load went to DRAM, the pipeline would spend almost all its time stalled.

The fix is a cache: a small, fast memory next to the core that keeps copies of recently used data. It works because programs are predictable in one specific way — they reuse what they touched recently, and they touch things near what they touched recently.

The memory hierarchy

No single technology is both big and fast, so computers stack several:

These are orders of magnitude for a desktop or server CPU of the mid-2020s, not exact figures. Going down the table, each level is bigger, cheaper per byte and slower. Each one acts as a cache for the level below it.

Tanenbaum's hierarchy runs from registers down to tape and optical disks. The idea hasn't changed; the numbers have.

Locality

Caches rely on two habits of real programs:

• Temporal locality: data used now is likely to be used again soon — a loop counter, the top of the stack, the instructions of a loop body.
• Spatial locality: data near what was used is likely to be used soon — the next element of an array, the next field of a struct, the next instruction.

A cache exploits temporal locality by keeping recently used data, and spatial locality by loading more than was asked for.

Cache lines

Memory is divided into fixed-size blocks called lines — 64 bytes on every current x86 and most ARM cores. The cache never holds a single byte on its own. On a miss, it brings in the whole line that contains the address. On a hit, the data is already there.

The demo below runs a loop that sums 64 consecutive ints (256 bytes), and replays every data access through a cache with 64-byte lines:

Each square in the strip is one access. Only 4 of the 64 miss — one per line — and the other 60 hit: 93.75%. The first miss on each line is compulsory: nobody had touched that line yet, so no cache could have had it.

Now change line to 16 bytes: 16 misses. Change it to 4 bytes, one int per line, and every access misses. Spatial locality only pays off because the line is bigger than the thing you asked for.

Where does a line go?

A cache with S sets and W ways holds S × W lines. Every address is split into three fields:

With 64-byte lines, the offset is the low 6 bits. With 64 sets, the next 6 bits choose the set. The rest is the tag, stored next to the line so the cache can check which of the many possible lines it actually holds.

On an access, the cache takes the set index, compares the tag against the W lines of that set — all at once, in parallel — and reports a hit if one matches.

• Direct-mapped (W = 1): each line has exactly one possible slot. Lookup is fast and simple, but two lines that share a set index evict each other.
• W-way set-associative: each line can go in any of W slots of its set.
• Fully associative (S = 1): any line can go anywhere, at the cost of comparing against every tag.

A common L1 data cache is 64 sets × 8 ways × 64 bytes = 32 KB. Tanenbaum's book notes that associativity beyond four ways was unusual. That's no longer true: current L1 data caches are 8- to 12-way, and L3 caches 12- to 16-way or more.

Conflict misses

Here two arrays sit exactly 128 bytes apart, and the loop reads a[i] and b[i] alternately. The cache is direct-mapped: 8 sets × 1 way × 16 bytes = 128 bytes.

Every access misses. a[i] and b[i] are 128 bytes apart, the size of the whole cache, so they land in the same set and keep evicting each other. The program only uses 4 lines and the cache has 8 slots, so space isn't the problem; the mapping is. These are conflict misses, in red.

Change ways to 2. Now each set holds both lines, and after the four compulsory misses everything hits. This is what associativity buys.

Capacity misses and writes

When the data simply doesn't fit, even perfect placement can't help. This loop adds 1 to every element of a 256-byte array, twice, through a 128-byte cache:

add DWORD PTR [...], 1 reads the value and then writes it back, so each element costs two accesses: a read, then a write that always hits. By the time the second pass starts, the start of the array has long been evicted, so its misses are capacity misses, in blue: even a fully associative cache of 128 bytes would miss.

Look at write-backs too. This cache is write-back: a write only updates the cached line and marks it dirty (D in the table). The line goes back to memory when it's evicted. Every line is modified here, so every eviction is a write-back.

Set sets to 16. The cache is now 256 bytes, the whole array fits, and the second pass hits every time.

These three kinds of miss — compulsory, capacity, conflict — are the usual way to explain why a program misses. They also suggest the fixes: bigger lines or prefetching for compulsory misses, a bigger cache or a smaller working set for capacity misses, more ways or a different data layout for conflict misses.

Access order matters

Same data, same work, different order. A C array int m[8][8] is stored row after row. Summing it row by row walks memory in order. Summing it column by column jumps 32 bytes at every step.

The first version hits 75% of the time. The second misses every single time: each column touches 8 different lines, the cache holds 4, and by the time the next column comes back to a line, it's gone. On real hardware, with megabyte-sized arrays, the same difference makes the column-order loop several times slower. The instructions are identical; only the order of memory accesses changed.

Writes

Every write raises two questions:

• Write hit: update memory now (write-through), or only when the line is evicted (write-back)? Write-through is simpler and keeps memory up to date, but it sends every store to the next level. Current CPUs use write-back for their data caches.
• Write miss: bring the line into the cache first (write-allocate), or send the write straight to the next level? Write-back caches almost always allocate, as the demo does: the next access to that line is then likely to hit.

Replacement

When a set is full, a miss has to evict one of its lines. The ideal choice is the line that will be needed furthest in the future, but hardware can't see the future. LRU (least recently used) evicts the line that hasn't been touched for the longest time, betting on temporal locality. That's what the demos do.

True LRU gets expensive with many ways, because the order has to be updated on every access. Real caches use cheaper approximations, such as tree-based pseudo-LRU, or more adaptive policies that resist a single big scan flushing everything useful.

The effective access time

With a cache access time c, a memory access time m and a hit ratio h, the average access time is:

c + (1 − h) × m

With c = 4 cycles and m = 300 cycles:

• h = 95%: 4 + 0.05 × 300 = 19 cycles;
• h = 99%: 4 + 0.01 × 300 = 7 cycles.

Four points of hit rate make memory look almost three times faster. That's why a small change in access pattern, like the row/column example, can change a program's speed so much.

Real cache hierarchies

• Split L1. Each core has an L1 instruction cache and an L1 data cache, so a fetch and a load never compete. This is the split cache from the fetch–decode–execute chapter.
• Private L2 per core, unified (code and data).
• Shared L3 for all cores on the chip.
• Inclusion varies. Some designs keep a copy of every L1/L2 line in L3 (inclusive). Others don't: AMD's Zen L3 is filled mainly with lines evicted from L2 (a victim cache), and Intel's recent server chips use a non-inclusive L3.
• Hardware prefetchers watch the access stream and fetch lines before they're requested — the next line, or the next element of a regular stride. They turn many compulsory misses into hits.
• With several cores caching the same data, the caches must also stay coherent. That's a subject for the multicore chapter.

On Linux, lscpu --caches or getconf -a | grep CACHE lists your machine's cache sizes, associativity and line size, and perf stat -e cache-misses ./prog counts misses in a real run.

Takeaways

• The memory hierarchy trades size for speed: registers, L1, L2, L3, DRAM, storage.
• Caches work because of temporal and spatial locality, and they move data in lines, usually 64 bytes.
• An address splits into tag, set index and offset. Associativity decides how many places a line can go.
• Misses are compulsory, capacity or conflict. Access order and data layout can change hit rates dramatically.
• Data caches are write-back and write-allocate, and replace lines with LRU or an approximation of it.
• Average access time is c + (1 − h)m, so a few points of hit rate matter a lot.