Caches, sets and prefetching

1.3 How a cache actually works

A cache stores fixed-size blocks called lines. On every x86 server you will meet, a line is 64 bytes, aligned to a 64-byte boundary. Loading one byte fetches the whole line that contains it.

There are two reasons for working in lines. Every cached block needs a tag saying which address it holds, and a tag per byte would cost more than the data. More importantly, most of a DRAM access is latency, not transfer. Once the request has crossed the chip and the DRAM row is open, moving 64 bytes instead of 8 adds only a nanosecond or two. Neighbouring bytes come nearly free, and programs usually want them soon.

A record of six u64 fields occupies 48 bytes. It fits in one line if suitably aligned; ordinary 8-byte alignment does not guarantee that. An aligned record of 72 bytes necessarily spans two lines, but an operation pays for both only if it touches fields on both.

Each core has private L1 caches for data and instructions, and a private L2. The L3 is shared. On Intel servers it is split into one slice per core on an on-chip mesh, and an L3 hit may come from the next slice or one across the die, which is why L3 latency is a range. Sharing matters: a logging thread streaming a large file on another core will evict your price levels from L3 without touching your code.

What a miss really is

Follow one load that misses L1. The L1 checks the tags in the set the address maps to and finds no match. It allocates one of its 10–16 fill buffers to track the request; the relevant resources limit how many outstanding requests the core can track, and their sizes vary by design. The request goes to L2, then across the mesh to the L3 slice that owns the address, then to the memory controller and DRAM. The 64 bytes come back, are installed in L2 and L1, and the load completes.

If the set is full, the cache’s replacement policy chooses a victim, often using an approximation to least-recently-used. It then stays until other traffic through that set pushes it out, or until another core writes to it (section 1.5). Prefetches, explicit cache flushes and other cache-management operations can also displace it. That is why a frequently touched value is likely to remain in L1 unless conflicting traffic displaces it, while a value touched once a second almost never does.

Stores miss too. A store to an uncached line first fetches it, because the cache holds only whole lines. A store buffer hides this for a while, but a loop writing a large buffer it never reads, such as a log ring, still pulls every line in before overwriting it.

Modern caches are write-back. A store changes the line in L1 and marks it dirty, and the data moves down only when the line is evicted. Write-through, the alternative, sends every store to the next level at once; a counter incremented a million times would cause a million writes instead of one. The price of write-back is that the only current copy of a line may sit in one core’s private cache, where other cores must find it. That is section 1.5.

Sets and associativity

If any line could go anywhere, every lookup would compare against every tag, which is far too slow for a 1 ns L1. If each address had one fixed slot, two hot addresses sharing a slot would evict each other forever. Real caches split the difference, and the easiest way to picture the compromise is a hotel. The L1 is a hotel with 64 floors, called sets, and 12 rooms on each floor, called ways. Each 64-byte line is a guest. A guest cannot pick any room: some digits of its address say which floor it must stay on, and on that floor it may take any free room, or evict the guest who has been idle longest. Lookup is cheap because the floor is known: walk to it and check 12 doors, not 768.

The address itself says which floor. Bits 0–5 (six bits, 64 values) say which byte within the 64-byte line; the cache ignores them when placing a line, because a line is always whole. Bits 6–11 (six bits, 64 values) name the set: the floor. The higher physical-address bits form the tag, written on the door, so a lookup compares its tag with the 12 doors on the floor and knows at once whether the line is in. The bit ranges follow from the sizes: 48 KB ÷ 64 B = 768 lines; 768 ÷ 12 ways = 64 sets; 64 sets need 6 bits, and a 64-byte line needs 6 offset bits, so the set index runs from bit 6 to bit 11.

The middle bits of the address pick the floor; the tag on the door says which of the many possible lines is in the room; the offset is ignored until the line is found.

Take the address 0x7f3a_1234_5680. Its low twelve bits are 0x680 = 1,664. Bits 0–5 are 0, so the line starts here. Bits 6–11 are 1,664 ÷ 64 = 26: floor 26. The remaining high part is 0x7f3a12345. For a virtual address, those are not yet the hardware tag: L1 uses the translated physical address for that comparison. Add 4,096 (0x1000) to get 0x7f3a_1234_6680: its page-offset bits are unchanged, so it still selects floor 26. Its actual tag depends on the physical page mapping. Any two addresses whose difference is a multiple of 64 sets × 64 bytes = 4,096 bytes share a floor, which is where the trouble below comes from.

The practical consequence is that addresses exactly 4,096 bytes apart land on the same floor, and only 12 of them fit in L1 at once. Suppose per-instrument state lives in a Vec of 4 KB structs, and you read best_bid at offset 0 for 40 instruments on every tick. All 40 lines want one floor with 12 rooms. The 13th evicts the first, the 14th evicts the second, and by the time the next tick comes back to instrument 1 its line is gone: every read misses, although the 40 lines total 2.5 KB in a 48 KB cache. Any power-of-two stride of 64 bytes or more uses only a fraction of the sets: a 1 KB stride uses 4 of the 64 floors. Break the power of two by padding each element with one extra line (4,160 bytes, so consecutive elements land on consecutive floors), or move the hot field into its own dense array.

Hardware prefetchers

The hardware also fetches lines before you ask. One prefetcher grabs the next line. Another watches each load instruction for a constant stride, forwards or backwards. A streamer in the L2 detects sequential runs and races a couple of dozen lines ahead. Intel parts also fetch the other half of each aligned 128-byte pair.

Prefetchers need a pattern. Pointer chasing defeats them, because the next address is unknown until the current load completes. Random access, the normal pattern of a hash table, defeats them. Large strides weaken them, because they will not cross a 4 KB page boundary.

The gotcha is benchmarks. A microbenchmark that walks a fresh array in order gets perfect prefetching; production touches it in whatever order the market dictates. If your benchmark is more regular than production, you are measuring the prefetcher. When you know an address a few hundred cycles early, core::arch::x86_64::_mm_prefetch requests it explicitly.