# CPU Caches: The Memory Hierarchy Your Code Lives In

> DRAM is ~100ns away; your CPU can do ~400 arithmetic operations in that time. Caches exist to hide that gap, and whether they succeed is decided by how your code lays out and walks its data.

URL: https://harshith.in/blog/cpu-caches-explained/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: performance, systems, hardware

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.