A modern CPU core can execute four or more instructions per cycle, and a cycle is about a quarter of a nanosecond. Main memory answers in roughly 100 nanoseconds. Do the arithmetic: one DRAM access costs the same as ~1,500 instruction slots. If every load actually went to DRAM, your 4 GHz machine would compute like a 10 MHz one. It doesn’t, because of three levels of cache — and because most code accidentally cooperates with them. The interesting cases are when it doesn’t.

The Hierarchy

text
   Core ──▶ L1d  32-48 KB    ~4 cycles     per-core
        ──▶ L2   512KB-2MB   ~12 cycles    per-core
        ──▶ L3   8-96 MB     ~40 cycles    shared
        ──▶ DRAM             ~200+ cycles

Each level is bigger and slower. A load checks L1; on a miss it checks L2, then L3, then DRAM, paying each latency along the way. The design bet is locality: data you touched recently (temporal) and data near it (spatial) are likely to be touched next.

Cache Lines: The Unit of Everything

Caches don’t move bytes; they move 64-byte lines. Load one int and the CPU fetches the surrounding 64 bytes. This is the single most consequential fact in performance work:

  • Walk an array of 4-byte ints sequentially and you pay one memory access per 16 elements — the other 15 are free.
  • Walk a linked list whose nodes are scattered across the heap and you pay a full miss per element, using 8 bytes of each 64-byte fetch.

Same O(n) traversal, ~10–30× difference in wall time. This is also why the classic matrix-traversal demo works:

c
/* fast: walks memory in layout order */
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

/* slow: jumps N*4 bytes every step, one line fetched per element */
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += a[i][j];

On a 4096×4096 matrix the column-major loop is routinely 5–10× slower. Nothing about the algorithm changed — only the order in which lines are touched.

Associativity and Ugly Strides

A cache isn’t a free-for-all: each memory address can live in only a small set of slots (typically 8-way or 12-way associative). The set is chosen from the address’s middle bits, which produces one famous trap: power-of-two strides. Walk memory in steps of exactly 4096 bytes and every access maps to the same set; you get conflict misses in a nearly empty cache. Matrix dimensions like 1024 and image strides like 2048 hit this constantly. The fix is embarrassing: pad the row to 1040 and the problem evaporates.

Writes, and the Cost of Sharing

Caches also absorb writes (write-back: the line is dirtied in cache and flushed later). But a written line must be owned by exactly one core. When two cores write to the same line — even to different variables in it — ownership ping-pongs between them over the coherence protocol, hundreds of cycles per bounce. That’s false sharing; I’ve written about it separately. The relevance here: the 64-byte line is the unit of coherence too, so layout decisions become concurrency decisions.

Seeing It

Don’t guess which loop is cache-hostile — the hardware counts misses for you:

bash
perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./a.out

A healthy sequential workload shows L1 miss rates of a few percent. If you see 30–50%, your data structure or traversal order is fighting the machine. perf record with the mem-loads event will point at the exact instructions.

What This Means for Design

The practical rules fall out directly: prefer arrays and vectors over node-based structures for hot paths; keep hot fields together and cold fields elsewhere (struct-of-arrays when you only touch one field per pass); process data in passes that fit in L2; avoid power-of-two strides. None of this is exotic — it’s why std::vector is the default answer, why databases store rows in pages and columns in column stores, and why “rewrote it to be cache-friendly” so often produces the kind of speedup that people mistake for a different algorithm.

Takeaways

  • The hierarchy exists because DRAM latency is ~100 ns and cores execute in ~0.25 ns.
  • Everything moves in 64-byte lines: layout and traversal order dominate.
  • Sequential access is nearly free per element; scattered pointer-chasing pays full latency every hop.
  • Power-of-two strides cause conflict misses; pad your rows.
  • perf stat measures cache behavior directly — never argue about it, count it.