The cache hierarchy

A core reads data from a hierarchy of memories, each larger and slower than the one above:

• L1 data cache: per core, tens of KB, a few cycles. Separate L1 instruction cache of similar size.
• L2: per core on current server parts, around a megabyte or two, low tens of cycles.
• L3 (last-level cache): shared by the cores on a die or socket, tens of MB, a few tens of cycles, more on large chips where it is split into slices across a mesh.
• Main memory: on the order of 80 to 120 nanoseconds for a load that misses everything, which is several hundred cycles at server clock speeds. On a two-socket machine, memory attached to the other socket is slower again.

Treat these numbers as orders of magnitude. They change with each processor generation, and an interviewer will respect "roughly" followed by "I'd measure it on the target machine" more than false precision. The ratios are what matter: each step down costs several times more.

The question is about the working set: the data the hot path touches repeatedly. If it fits in L2, almost every access is a hit after warm-up. At 4 MB, the table does not fit in L2 and competes with everything else for L3; many lookups miss to L3, and some to memory, especially after other code has run and evicted parts of it. At 256 KB it fits in L2, and most lookups become an order of magnitude cheaper. The arithmetic per lookup is unchanged; the memory behind it is not.

This is the most important performance property of a data structure in a trading system: does what the hot path touches stay in cache between events? That is why the earlier modules kept saying "contiguous", "compact" and "hot fields together".

Caches hold whole 64-byte lines. Each cache is set-associative: the address picks a set, and the line can go in any of a small number of ways within that set, typically 8 to 16. When a set is full, a line is evicted, usually the least recently used one.

Two consequences:

• Conflict misses. Addresses that are a large power of two apart map to the same set. Walking a column of a matrix whose rows are 4 KB apart, or many arrays allocated at 4 KB-aligned addresses and accessed together, can thrash one set while the rest of the cache sits empty. Padding the stride by a line fixes it.
• Writes allocate. Writing to a line that is not in the cache normally fetches it first (a read for ownership), so writing a large buffer costs the reads as well. The prefetching lesson later in this module covers non-temporal stores that avoid this.

Whether L3 includes the contents of L1 and L2 (inclusive) or not (non-inclusive or exclusive) varies between designs and matters for some cross-core effects, but rarely for the code you write.

Code is data too. Hot code must fit in the L1 instruction cache and the decoded-micro-op cache for the core to run it at full speed. Large templates, aggressive inlining and rarely taken error paths mixed into hot functions all enlarge the instruction footprint. Marking error handlers cold, keeping them out of line, and using profile-guided optimisation to lay out hot code together are the instruction-side equivalents of packing data.

A pointer chase through a randomly permuted array of a chosen size measures load latency at each level: below 32 KB you see L1 latency, then a step at each cache size, then memory. It is a good experiment to have done, because it turns the table above into numbers for your own machine, and it is the kind of thing worth mentioning when asked how you know.

// next[i] holds the index of the following element in a random cycle through the array
std::size_t i = 0;
auto t0 = now();
for (std::size_t k = 0; k < steps; ++k) i = next[i];   // each load depends on the last
auto ns_per_load = (now() - t0) / steps;

On multi-socket servers, each socket has its own memory. A thread reading memory attached to the other socket pays an extra trip across the interconnect, and cache lines shared between sockets are expensive to keep coherent. Latency-sensitive processes are pinned to one socket, and their memory is allocated there (with numactl or by first touching it from a thread on that socket, since Linux places pages on the node that first writes them).