Down to the Metal

Part III · Chapter 9

Caches: Keeping Data Close

Main memory is huge but far away: hundreds of clock ticks per trip. Yet most of the time, a modern processor gets its data in just a few ticks. The trick is a cache, a small, fast memory that keeps copies of what you're likely to need next. In this chapter we build one and watch it work.

At the end of the last chapter we hit the memory wall: a processor that can do several things per clock tick, connected to a memory that takes hundreds of ticks to answer. If every load really waited for main memory, a modern computer would spend nearly all its time waiting. The solution is one of the most important ideas in all of computing, and it's one you already use every day.

Think of a desk in a library. The books you're using right now sit on your desk. Ones you might need soon are on a nearby shelf. The rest of the library is a long walk away. You don't fetch every book from the far stacks each time you need a fact: you keep the useful ones close.

The memory hierarchy

Computers do exactly the same thing, with several layers of "desk". Each layer is smaller, faster and more expensive per byte than the one below it:

Switch to the second view to feel the differences. The bars are on a logarithmic scale, so each step to the right means ten times longer.

Registers and caches are built from the fast circuits of Chapter 3: flip-flops and six-transistor SRAM cells. Main memory is DRAM, from Chapter 8. Below that, storage (Part V) is slower still. The goal is to make the whole stack feel nearly as fast as the top, and as big as the bottom.

Why caches work: locality

A cache can only help if programs tend to reuse data, and nearby data, soon. Luckily, they overwhelmingly do. This property is called locality, and it comes in two flavors:

Caches exploit both. They keep recently used data (for temporal locality), and when they fetch something, they fetch its neighbors too (for spatial locality).

Cache lines

A cache never fetches just one byte. It fetches a whole block of neighboring bytes, called a cache line. On today's x86 and most RISC-V processors, a line is 64 bytes. Remember the DRAM row buffer and its burst of fast reads from an open row: fetching 64 neighbors costs barely more than fetching one.

To find something in the cache, the processor splits each address into three parts:

Each entry also has a valid bit, which says whether it holds anything at all.

A cache you can watch

Below is a toy cache: 8 lines of 8 bytes each, sitting in front of 128 bytes of memory. Start with the direct-mapped organization, the simplest kind: each line of memory has exactly one place it can go in the cache, chosen by the index bits.

Pick an access pattern and press Step to follow it one access at a time, or Run all. A green row is a hit; a red row is a miss. You can also type any address from 0 to 127 and press Access.

Try each pattern and notice what happens:

Associativity: more than one place to go

That ping-pong problem is called a conflict. The fix is to give each set more than one slot, or way. In a 2-way set-associative cache, every set holds two lines, so 0 and 64 can live side by side. Switch the simulator to 2-way and run the ping-pong again: two misses, then nothing but hits.

When a set is full and a new line arrives, the cache must pick a victim to throw out. Our toy cache throws out the least recently used line (LRU), betting that what you haven't touched in a while is what you need least.

Taken to the extreme, a fully associative cache lets any line go anywhere. That avoids conflicts entirely, but the cache has to compare the tag against every entry at once, which costs a lot of hardware. Real L1 caches are usually 8- to 12-way: a compromise.

What about writes?

When a program stores to memory, the cache has a choice. A write-through cache updates its copy and main memory at the same time: simple, but every store pays the slow trip. A write-back cache only updates its own copy and marks the line dirty. The data goes to memory later, only when the line is thrown out. If a program writes the same variable a million times, a write-back cache makes just one trip to memory. Modern CPU caches are write-back.

Levels of cache

There's a tension in cache design: a bigger cache holds more, but takes longer to search. So real processors stack several levels:

A load checks L1 first. On a miss it tries L2, then L3, and only then main memory. Thanks to locality, the great majority of loads in typical programs are satisfied by L1.

Why the order you read in matters

Here's where caches stop being an invisible hardware detail and start affecting how you should write programs. In C, a two-dimensional table is stored row after row: all of row 0, then all of row 1, and so on. Look at these two loops. They add up exactly the same numbers:

// Fast: walks memory in order
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += m[i][j];

// Slow: jumps a whole row ahead on every step
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += m[i][j];
Here the table is 8 × 8 numbers of 8 bytes each, so each row is exactly one 64-byte cache line, and the cache holds just 4 lines. Watch both orders. Green means hit, red means miss.

The column-by-column version misses every single time. By the time it comes back for the next number in a row, that row's line has already been thrown out. Real programs see exactly this effect, and on large tables the slowdown can be even bigger than in our tiny demo. Swapping two loops is one of the cheapest speed-ups in programming.

Meanwhile, inside a real CPU

Caches are normally invisible: the same mov or ld instruction simply runs faster or slower depending on whether the data was cached. But programs can see the line size, and can even give hints. On Linux, you can ask:

$ getconf LEVEL1_DCACHE_LINESIZE
64

And both ISAs have prefetch instructions, which tell the cache "I'll need this address soon, start fetching it now", without waiting for the answer:

; x86-64
prefetcht0  [rdi + 256]     ; start bringing the line 256 bytes ahead into the cache
# RISC-V (with the Zicbop extension)
prefetch.r  256(a0)         # the same hint: "I'm about to read this"

In practice they're rarely needed, because modern processors have hardware prefetchers: circuits that watch the stream of addresses, notice patterns like "reading every 64 bytes, going up", and fetch the next lines before the program asks. That's another reason why walking memory in order is so fast: it's the easiest pattern of all to predict.

Try it yourself

  1. With 64-byte cache lines, which line does address 0x1234 belong to, and which byte within it?
    Show answerThe lowest 6 bits are the offset: 0x1234 = 4660, and 4660 = 72 × 64 + 52. So it's byte 52 of line 72 (the line covering addresses 4608 to 4671).
  2. In the direct-mapped simulator, why do addresses 0 and 64 fight over the same slot?
    Show answerWith 8-byte lines, address 0 is in line 0 and address 64 is in line 8. The cache has 8 sets, and 0 mod 8 = 8 mod 8 = 0, so both lines map to set 0. With only one way per set, each one evicts the other.
  3. Reading bytes 0 to 63 in order gives a hit rate of 87.5%. Why exactly that number?
    Show answer64 bytes = 8 lines of 8 bytes. The first byte of each line misses and the other 7 hit: 56 hits out of 64 accesses, which is 7/8 = 87.5%.
  4. Which of the "three Cs" are the misses in the "every 8th byte" pattern?
    Show answerAll 16 are compulsory misses: each access touches a line for the very first time. A bigger or more associative cache wouldn't help; only reading the bytes we've already fetched (better spatial locality) or prefetching would.
  5. A programmer's image filter loops over the columns of each row in the inner loop, but over the rows of each column in the outer loop. What would you suggest?
    Show answerIf the image is stored row by row, make the inner loop walk along a row (consecutive addresses) and the outer loop move from row to row. That turns most accesses into cache hits.

What we learned

So far, every address a program uses has been a real location in memory. In the next chapter we'll break that rule. With virtual memory, each program gets its own private, imaginary address space, and the processor translates every single address on the fly. It's how your computer keeps programs from trampling on each other, and how it can pretend to have more memory than it really does.