Locality and the Memory Wall

A modern processor core can retire several instructions per nanosecond. A read from main memory —DRAM— takes something like 60 to 100 nanoseconds. Put those two numbers side by side and the horror becomes clear: while the CPU waits for a single memory access, it could have executed hundreds of instructions. If every load and store paid full DRAM latency, your multi-gigahertz chip would crawl along at the speed of the memory bus, and all the cleverness of the pipeline would be wasted staring at a wall.

This is the memory wall: the ever-widening gap between how fast processors can compute and how fast memory can feed them. The entire memory hierarchy — registers, caches, DRAM, disk — exists to hide that gap. And the reason a hierarchy can work at all comes down to one lucky property of real programs: locality.

Two flavours of locality

Programs do not touch memory at random. They touch it in patterns, and there are two patterns that matter so much they have names:

Temporal locality says keep recently-used data close. Spatial locality says when you fetch one byte, fetch its neighbours too — which is exactly why caches move data in blocks of 64 bytes rather than one byte at a time. Almost every trick in this module is, at heart, a bet that one of these two localities holds.

Why the gap keeps growing

For decades processor performance improved at roughly 50\% per year while DRAM latency improved by only about 7\% per year. Two exponentials with very different exponents diverge fast — the gap between them widened by orders of magnitude. That divergence is the memory wall, and the chart below lets you feel it: nudge the processor's annual improvement rate and watch how quickly the "performance gap" curve rockets away from the memory curve.

The absolute numbers do not matter; the shape does. One curve pulls away from the other and never comes back. If nothing intervened, programs would spend nearly all of their time waiting on memory. The hierarchy is what intervenes.

The hierarchy: a stack of white lies

No single memory technology is both large and fast — SRAM is fast but tiny and power-hungry, DRAM is roomy but slow, flash is enormous but glacial. So we stack them, small-and-fast on top, large-and-slow at the bottom, and let each level cache the most-used data of the level below it. Locality is what makes the illusion hold: because accesses cluster, a small fast level captures the vast majority of them, and the big slow level is only rarely disturbed.

The magic is that the whole tower appears to run at nearly the speed of the top and at nearly the capacity of the bottom. To the programmer it looks like one flat, fast, gigantic memory — a comfortable fiction assembled from half a dozen honest, limited devices.

Average access time: the arithmetic of the illusion

How fast does the illusion actually run? For a single level backed by a slower one, the average memory access time (AMAT) is the hit time you always pay, plus the miss penalty you pay only on the fraction of accesses that miss:

\text{AMAT} = t_{\text{hit}} \;+\; (\text{miss rate}) \times t_{\text{penalty}}.

Suppose the L1 cache answers in 1\ \text{ns}, DRAM takes 100\ \text{ns} on a miss, and thanks to locality only 3\% of accesses miss. Then

\text{AMAT} = 1 + 0.03 \times 100 = 4\ \text{ns}.

Four nanoseconds — barely more than the 1 ns cache, nowhere near the 100 ns DRAM. That factor-of-25 improvement over "always hit DRAM" is bought entirely with a 97\% hit rate, which is bought entirely with locality. Run the code and watch how brutally AMAT punishes a rising miss rate: because the penalty is so large, even a few extra percent of misses dominates the whole average.

// Average Memory Access Time for a fast level backed by slow DRAM. function amat(hitNs: number, missRate: number, penaltyNs: number): number { return hitNs + missRate * penaltyNs; } const hit = 1; // ns, an L1 hit const penalty = 100; // ns, the cost of going to DRAM on a miss console.log("miss% AMAT(ns) vs. always-DRAM"); for (const pct of [0, 1, 3, 5, 10, 20, 50, 100]) { const a = amat(hit, pct / 100, penalty); const speedup = penalty / a; console.log(`${String(pct).padStart(4)}% ${a.toFixed(2).padStart(7)} ${speedup.toFixed(1)}x faster`); }

You could — and it would be gloriously fast — but an SRAM cell needs six transistors to a DRAM cell's one (a single transistor plus a tiny capacitor). That makes SRAM roughly an order of magnitude less dense and far more expensive and power-hungry per bit. A 16 GB SRAM main memory would be enormous, cost a fortune, and cook itself. The hierarchy is an economic compromise as much as a performance one: we spend our precious fast SRAM only where locality guarantees it will be reused constantly, and let cheap dense DRAM hold the long tail. Fast, big, cheap — pick two, then hide the seam.

Beginners sometimes talk as if the cache "creates" locality. It does not. The cache exploits locality that the program already has (or lacks). A cache-friendly loop that walks an array in order gets near-perfect spatial locality; the same loop striding backwards by 4096 bytes, or chasing pointers through a linked list scattered across the heap, may get almost none — and no cache can save it. This is why how you write your loops and lay out your data can change performance by 10× on identical hardware. The hierarchy rewards locality; it cannot manufacture it.

Where this module goes

Everything that follows is a way of making the illusion faster or wider. Next we open up the cache itself — how an address is chopped into a tag, an index and an offset, and how blocks map to slots. From there we quantify misses with the three C's, argue about write policies, and eventually descend all the way to the DRAM chips at the bottom of the wall. Keep the two localities in your pocket — you will meet them on every page.