Cache Performance and Cache-Friendly Code

We have a cache that exploits locality through set-associative placement and write policies. What we lack is a way to measure it: to say whether one cache, or one program, is faster than another. This final lesson reduces cache behavior to a single number, the average memory access time, shows how that number deteriorates as a program's access pattern degrades, and then returns to the module's opening question: writing code with locality the cache can exploit.

The three numbers and AMAT

Cache performance rests on three quantities, measured against a stream of references.

They combine into one figure of merit, the average memory access time, by weighting the penalty by how often it is actually paid:

The formula carries the whole intuition of the hierarchy. Because the miss penalty is enormous (DRAM is roughly two orders of magnitude slower than an L1 hit), even a small miss rate dominates the average. A cache with a 1 ns hit time, a 3 % miss rate, and a 100 ns miss penalty has $\text{AMAT}=1+0.03\times 100=4$ ns: the misses, though rare, contribute three-quarters of the time. This is why shaving the miss rate matters far more than shaving the hit time, and why the few misses you do take are the thing to attack.

A corollary: small changes in hit rate are large changes in speed. With a 1-cycle hit and a 100-cycle penalty, a 97 % hit rate gives $\text{AMAT}=1+0.03\times 100=4$ cycles while a 99 % hit rate gives $1+0.01\times 100=2$. Two percentage points of hit rate double the memory performance, so 99 % and 97 % hit rates describe machines of very different speed.

The arithmetic is unforgiving because AMAT is a weighted average of two numbers that differ by two orders of magnitude, and the weight on the large one is the miss rate. Halving the miss rate (3 % to 1.5 %) does far more than halving the hit time (1 cycle to 0.5), because the penalty is a hundred times the hit time. Every optimization in this lesson therefore aims at making misses rarer, not hits faster — the hardware already handles the latter.

Two levels: AMAT composes

Real hierarchies have several cache levels, and the formula nests naturally: the miss penalty of one level is the AMAT of the level below it. Work one example. L1 hits in 1 ns and misses 5 % of the time; L2 hits in 10 ns (beyond the L1 probe) and misses 25 % of its accesses; a DRAM access costs 100 ns beyond that.

Without the L2, the same L1 would give $1+0.05\times 100=6$ ns: the middle level more than halves the average, not by making hits faster but by making misses cheaper. That is the design logic of the whole pyramid: each level exists to shrink the penalty of the level above.

(The leaf latencies are cumulative: an L2 hit pays the L1 probe plus the L2 access, $1+10=11$ ns; a DRAM access pays all three, $111$ ns. Weighting each leaf by its path probability and summing gives $0.95\times 1+0.0375\times 11+0.0125\times 111=2.75$ ns.)

The knobs, and what they cost

A cache designer controls the three AMAT terms through the geometry of the last two lessons, and every knob that improves one term leans on another:

• Bigger cache ($C$). Lower miss rate (more of the working set fits), but a larger SRAM array is slower to search, so the hit time creeps up. This is why L1 stays small and fast while L2 and L3 grow large and slower.
• Bigger blocks ($B$). Better spatial locality per miss, but for fixed $C$ fewer lines, so more conflict and capacity evictions; and each miss now moves more data, raising the penalty. Block sizes settle in the middle: 32–64 bytes.
• More ways ($E$). Fewer conflict misses, but more comparators and muxing in the hit path: the hit time rises with associativity, which is why L1 caches are moderately associative rather than fully.
• Cheaper misses. Add a level below (the two-level computation above), or overlap the miss with useful work, which is the pipeline's stall game played against memory.

The programmer controls none of these. What the programmer controls is the miss rate term of their own program, the access pattern, and that is where the rest of the lesson lives.

The memory mountain

AMAT treats the miss rate as given, but the miss rate is not a constant: it depends on the program's access pattern, and that pattern has two knobs: the size of the data being swept (the working set, which decides which level of the hierarchy holds it) and the stride of the sweep (which decides how much of each fetched block is used). Plotting read throughput against both knobs produces the memory mountain: a surface high where data fits a fast level and is read stride-1, falling away into a slow plain as the working set spills to a lower level and the stride grows.

Read the mountain along each axis separately. Fix stride 1 and grow the working set: throughput descends a staircase of plateaus, one per level. A sweep that fits in L1 might stream at 12 GB/s; spill into L2 and it settles around 5; spill into L3, 2–3; spill into DRAM and it flattens below 1. The cliff edges are the cache capacities — you can read a machine's cache sizes off its mountain. Now fix a DRAM-sized working set and grow the stride: throughput slides downhill as each fetched block contributes fewer useful words, bottoming out when stride reaches the block size and every reference misses — the $\min (1,kw/B)$ law from the locality lesson, drawn as terrain. The mountain is the whole module in one picture: ascend it by shrinking the working set (temporal locality) and by shrinking the stride (spatial locality). Both are things the programmer controls.

For a numeric traverse of the mountain, fix stride 1 and read throughput as the working set grows past each level's capacity (the figures below are representative of a desktop core, not a specific chip):

Each row-to-row drop is a cache capacity being exceeded — the working set spilled out of one level into the next, slower one, and the miss rate for that level jumped from near zero to near one. The throughput does not decay smoothly; it steps, and the step edges sit exactly at 32 KB, 512 KB, and 8 MB, which is why a mountain measured on real silicon reports the cache sizes. Notice the throughput never falls as far as the raw latency ratio would suggest (DRAM's ~8 ns AMAT is 8x L1's, but the bandwidth only falls ~7x): the hardware prefetcher of the locality lesson is running ahead of the stride-1 sweep, hiding much of the DRAM latency behind streamed blocks. That prefetch help evaporates the moment the stride goes irregular — the mountain's other slope.

Cache-friendly code: stride-1

The first rule follows directly from spatial locality and the row-major layout: make the innermost loop stride-1. We saw this in the locality lesson; here is the payoff stated as a rule. When a cache miss brings in a block of, say, sixteen ints, a stride-1 inner loop uses all sixteen before triggering the next miss, so the miss rate is roughly $1/16$. A stride-16 inner loop uses one int per block and misses on nearly every access. Same data, same instruction count, a 16x difference in misses.

Case study: loop order in matrix multiply

Matrix multiplication is the classic example, because its triple loop can be permuted six ways that all compute the same $C=AB$, with wildly different miss counts. Take $N\times N$ matrices of doubles (8 bytes) and 32-byte blocks, so a block holds four doubles. The natural ijk order:

/* ijk: inner loop k sweeps a row of A (stride-1) and a column of B (stride-N). */
void matmul_ijk(double A[N][N], double B[N][N], double C[N][N]) {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      double sum = 0.0;
      for (int k = 0; k < N; k++)
        sum += A[i][k] * B[k][j];
      C[i][j] = sum;
    }
}

Count the memory behavior per innermost iteration, assuming the matrices are much larger than the cache. A[i][k] walks a row: stride-1, one miss per four iterations, $0.25$ misses. B[k][j] walks a column: stride-$N$, a different block every iteration, $1.0$ misses. sum lives in a register: $0$. Total: 1.25 misses per iteration. Now permute to kij, hoisting A[i][k] into a scalar:

/* kij: r = A[i][k] is loop-invariant; inner loop j streams rows of B and C. */
void matmul_kij(double A[N][N], double B[N][N], double C[N][N]) {
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++) {
      double r = A[i][k];
      for (int j = 0; j < N; j++)
        C[i][j] += r * B[k][j];
    }
}

Per inner iteration: r is a register, $0$ misses. B[k][j] walks a row: stride-1, $0.25$. C[i][j] walks a row: stride-1, $0.25$ (it is both loaded and stored, but the block is resident after the first touch). Total: 0.5 misses per iteration: a 2.5x reduction, even though kij executes more memory operations per iteration (an extra store to C). The third family, jki, is the worst case: its inner loop walks columns of both A and C for $2.0$ misses per iteration, four times worse than kij.

The same point again: all six orders run $2N^3$ floating-point operations; only the order of memory touches differs, and on large matrices kij outruns jki by roughly the ratio of their miss counts. Checking the loop order of a hot kernel is minutes of work for integer-factor speedups.

Cache-friendly code: blocking

Stride-1 fixes spatial locality, but some computations reuse data so heavily that the working set, not the stride, is the problem. Matrix multiply is again the case in point: the trouble is reuse across the whole matrix. By the time the loops come back to a row of A or a column of B, it has long since been evicted, because between two uses the loop streamed an entire $N\times N$ matrix through the cache: capacity misses, in the vocabulary of the direct-mapped lesson. When N is large enough that a row plus a column no longer fits, every reuse is a miss.

Blocking (also called tiling) restructures the computation to reuse data while it is still resident. Instead of computing whole rows and columns, it carves the matrices into small $\text{BLK}\times \text{BLK}$ tiles sized so that the tiles in flight fit in the cache, and multiplies tile by tile. Within a tile-pair, every loaded block is reused $\text{BLK}$ times before the tile moves on, so the misses are amortized.

/* Blocked C = A * B with BLK x BLK tiles sized to fit in cache. */
void matmul_blocked(double A[N][N], double B[N][N], double C[N][N]) {
  for (int ii = 0; ii < N; ii += BLK)
    for (int jj = 0; jj < N; jj += BLK)
      for (int kk = 0; kk < N; kk += BLK)
        /* multiply one BLK x BLK tile of A by one of B into C */
        for (int i = ii; i < ii + BLK; i++)
          for (int j = jj; j < jj + BLK; j++) {
            double sum = C[i][j];
            for (int k = kk; k < kk + BLK; k++)
              sum += A[i][k] * B[k][j];
            C[i][j] = sum;
          }
}

The working-set argument fixes the tile size: the inner three loops touch one tile of each matrix, $3\cdot {\text{BLK}}^2\cdot 8$ bytes of doubles, and that must fit comfortably in the cache being targeted. For a 32 KB L1, $3\cdot {\text{BLK}}^2\cdot 8\le 32768$ gives $\text{BLK}\le 36$, so tiles of 32 fit with room to spare, and every element loaded into the cache is used $\text{BLK}=32$ times before eviction instead of once.

Blocking does not change the arithmetic — the same $N^3$ multiply-adds run — but it changes the order, and order determines the miss count. On large matrices it turns a near-100 % miss rate back into something close to the tiny stride-1 rate, and the speedup is often several-fold. Production linear-algebra libraries are blocked for every level of the hierarchy at once, registers included.

The miss you cannot avoid, and the tile you need not tune

AMAT and blocking are the classical account. Two developments refine it — one in hardware that changes what a miss penalty even means, one in algorithms that removes the tile-tuning the blocked kernel above still requires.

Non-blocking caches make misses overlap. The AMAT formula assumes a miss stalls the processor for the full penalty. Modern cores do not stall: a non-blocking (lockup-free) cache, using miss-status holding registers (MSHRs), keeps serving hits and launching further misses while an earlier miss is outstanding (Kroft, Lockup-free instruction fetch/prefetch cache organization, ISCA 1981).¹ The consequence for code is memory-level parallelism: if several independent misses are in flight at once, their penalties overlap, and the effective cost is far below the sum. This reframes the programmer's job — it is not only about fewer misses but about misses that can proceed in parallel, which is why a scatter of independent loads can outrun a dependent chain that misses the same number of times. The AMAT number becomes a ceiling that overlap sits below, not an exact prediction.

Cache-oblivious algorithms block without knowing the cache. The blocked matrix multiply needed a tile size $\text{BLK}$ tuned to a specific cache — recompile for a new machine, retune. Cache-oblivious algorithms reach near-optimal miss counts at every level of the hierarchy at once, with no cache parameters in the code, by dividing the problem recursively until the subproblems are small enough to fit whatever cache they happen to land in (Frigo, Leiserson, Prokop & Ramachandran, Cache-oblivious algorithms, FOCS 1999).² Recursive matrix multiply, for instance, halves the matrices until a subproblem fits — and since the recursion passes through every size on the way down, it is automatically blocked for L1, L2, L3, and registers simultaneously, with a single portable implementation. It is the theoretical endpoint of this lesson's advice: locality engineered into the algorithm's structure rather than tuned into its constants.

This closes the Memory Hierarchy module. From the latency gap that motivates a hierarchy, through the locality that makes one work, to the cache organization that implements it — the payoff is code, and hardware, that keep the working set near the top of the pyramid.