Locality

The last lesson ended on a promise: stacking fast small storage on slow large storage works only if accesses cluster, so that the data the processor needs is usually already in the fast level. If a program touched memory uniformly at random, no cache could help — every reference would miss. Real programs are not random. They exhibit locality, a tendency to reference storage near where they have referenced recently, both in time and in space. Locality is not a hardware feature; it is a property of programs, and it is the single assumption every level of the hierarchy is betting on.

Two flavors of locality

Locality comes in two forms, and a well-behaved program has both.

The hierarchy exploits each with a different mechanism. Temporal locality is captured by keeping a recently-used item in the fast level: once it has been fetched, leave it there and the reuse is free. Spatial locality is captured by fetching in blocks: when the processor asks for one byte, the level below hands up a whole cache block (typically 64 bytes) of neighbors, so the next few nearby references are already present. The block, in turn, matches the shape the technologies discount: a contiguous run served from one DRAM row, one disk track, one flash page.

The two mechanisms exploit two different predictions: that the same address will be referenced again (so keep it resident), and that a nearby address will be referenced next (so fetch the neighbors while the slow level is already open). A program with strong locality of both kinds is one where almost every reference is either a repeat of a recent address or a step to an adjacent one — and that is precisely the program a cache serves nearly for free.

Locality, read off a reference stream

Before any array, the plainest way to see both kinds of locality is to examine a short reference stream — the sequence of addresses a fragment of code touches, in order. Consider a loop that keeps a running maximum over an array a:

int m = a[0];              /* m: one location, revisited every pass */
for (int i = 1; i < 8; i++)
  if (a[i] > m) m = a[i];  /* a[i]: consecutive addresses, one step apart */

Assume a starts at address 0 and ints are 4 bytes, and abbreviate m's home as $m$. The stream of memory addresses, in issue order, is

Two patterns jump out. The location $m$ recurs every other reference: pure temporal locality, a fixed address hit again and again inside a tiny window. And the array addresses $0,4,8,\dots$ march upward by exactly one element: pure spatial locality, each reference one step past the last. Nearly every program's reference stream combines these two patterns: a few hot locations revisited constantly, plus runs of neighbors swept once.

Loops, arrays, and stride

The richest source of locality is the loop over an array, because the access pattern is regular enough to reason about exactly. Consider summing the elements of an array a of length n. The data references walk the array in order, one element after another; the loop variable i and the accumulator sum are touched on every iteration.

int sumvec(int a[], int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)   /* i, sum: strong temporal locality */
    sum += a[i];                /* a[i]: stride-1 — strong spatial locality */
  return sum;
}

The accumulator sum and the index i enjoy temporal locality: each lives in a register and is reused every pass. The array reference a[i] enjoys spatial locality: consecutive iterations read addresses &a[0], &a[1], … — adjacent in memory. We call this a stride-1 reference pattern: each step advances by one element.

Stride-1 is the best case, and we can say exactly how good. The intuition first: a miss brings in a whole block of neighbors, and a stride-1 walk then spends the next several references inside that block before it needs another one. The wider the block relative to the element, the longer the run of hits, and the fewer misses per element. The arithmetic just makes the next several exact.

Suppose blocks hold $B=16$ bytes, so each block holds four 4-byte ints. The reference to a[0] misses and fetches the block containing a[0] through a[3]; the next three references hit; a[4] misses and fetches the next block; and so on. One miss per four references: a miss rate of $1/4$, no matter how long the array is. In general, a stride-1 walk over elements of size $w$ misses at rate $w/B$: with 64-byte blocks and 4-byte ints, one miss in sixteen.

The same arithmetic extends to any stride. A stride-$k$ walk over $w$-byte elements uses only every $k$-th element, so each fetched $B$-byte block contributes $B/(kw)$ useful references (at least one), and the miss rate is

For $B=16$ and int elements, the decay is quick: stride 1 misses at $1/4$, stride 2 at $1/2$, and stride 4 or more at $1$: every single reference misses, because consecutive references land in different blocks. Past that point a larger stride cannot make the rate worse; it just leaves ever more of each fetched block untouched.

Row-major versus column-major

Locality matters most in nested loops over a two-dimensional array, because the language has already decided the memory layout. In C, a 2-D array is stored row-major: the entire first row sits in memory, then the entire second row, and so on. Element A[i][j] lives at offset i*N + j from the base. So fixing the row and walking j is stride-1; fixing the column and walking i jumps by a whole row, stride N, each step.

The two traversals below compute the identical sum and differ only in loop order. On a large matrix the first can run several times faster than the second, purely because of which references hit in cache.

/* Row-major friendly: inner loop varies j → stride-1 over memory. */
int sum_rows(int A[N][N]) {
  int sum = 0;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      sum += A[i][j];          /* A[i][0], A[i][1], ... — contiguous */
  return sum;
}

/* Cache-hostile: inner loop varies i → stride-N, jumps a full row each step. */
int sum_cols(int A[N][N]) {
  int sum = 0;
  for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
      sum += A[i][j];          /* A[0][j], A[1][j], ... — N ints apart */
  return sum;
}

sum_rows sweeps along each row, using every element of each fetched block before moving on. sum_cols reads one element from a block, then leaps N elements away, likely a different block, and by the time it comes back to that row's neighbors, the block may have been evicted, so the same blocks are fetched over and over.

Counting the misses

Put numbers on it. Let A be int A[8][8] (256 bytes: 16 blocks of $B=16$ bytes, four ints each), and let the cache be far smaller than the matrix, so a block fetched early in the traversal is gone by the time the loop comes back near it.

Rowwise, the traversal is one long stride-1 walk over all 64 elements: a miss on A[0][0] brings in A[0][0..3], the next three references hit, and the pattern repeats. One miss per block, 16 blocks: 16 misses in 64 accesses, a miss rate of $1/4$.

Columnwise, consecutive references A[0][j] and A[1][j] are $8\times 4=32$ bytes apart, two blocks, so every reference lands in a different block from the last. Walking column $j$ touches eight different blocks, one per row. By the time the loop returns to column $j+1$, those blocks have been evicted, and the same misses repeat. 64 misses in 64 accesses, a miss rate of $1$: four times the misses, from reordering two for lines.

The lesson is not that one loop order is right; it is that the layout and the access order must agree. With a row-major language, vary the rightmost index in the innermost loop. The same sum, the same arithmetic, the same number of instructions — only the locality changes, and locality determines the cost. (Fortran stores arrays column-major, so there the advice inverts: vary the leftmost index innermost. The principle is the same; only the layout differs.)

The working set

Locality has a size as well as a shape. At any moment a running program is actively touching some collection of blocks — the loop it is in, the arrays it is sweeping, the stack frames near the top. That collection is the program's working set, and its size relative to a cache level determines whether the program's temporal reuse is actually captured.

The working set is why the same code can be fast on small inputs and slow on large ones with no change in instruction count. Summing an array of 1,000 ints (4 KB) that fits in a 32 KB L1 pays cold misses once and then reuses freely; summing 10 million ints (40 MB) overflows even a large L3, so each block is fetched, used, and evicted before the loop returns to it. The stride-1 spatial locality is identical in both — one miss per block — but the second has no temporal locality left to capture, because nothing revisits a block before it is gone. Reading the working set of a loop, and asking which level of the hierarchy it fits in, is the first question of every performance analysis in the last lesson.

Layout is locality: two ways to store the same records

Locality is not only about how you loop; it is about how you lay data out, and the classic illustration is a collection of records. Suppose a particle simulation keeps, for each of $n$ particles, a position and a mass, and a step touches only the positions. Two layouts store the identical data:

/* Array of structs (AoS): each particle's fields are contiguous. */
struct { double x, y, z, mass; } aos[N];   /* pos and mass interleaved */

/* Struct of arrays (SoA): each field is its own contiguous array. */
struct { double x[N], y[N], z[N], mass[N]; } soa;  /* pos separate from mass */

Walk the positions with 64-byte blocks (eight doubles per block). Under AoS, each particle's four doubles — three of position, one of mass — sit together, so a block holds two whole particles: reading x, y, z drags in the mass you never use, and only $6$ of every $8$ doubles fetched are wanted. Under SoA, the x array is one contiguous run, so a block holds eight consecutive x values, all used — perfect spatial locality, and mass is never fetched at all. Same data, same positions read; the layout alone changes the fraction of each fetched block that is actually used.

The rule generalizes past this example: store together what you access together. If a sweep touches only some fields, splitting those fields into their own arrays keeps the blocks full of wanted data. (If instead every step touches all of a record's fields, AoS is the better layout, for the same reason — locality follows access.) This is one more instance of the module's constant: the arithmetic of the computation is fixed, and only the locality of the data movement is in play.

Instructions have locality too

Everything so far concerned data, but the processor also fetches a stream of instructions, and that stream has locality of its own. Straight-line code is a stride-1 walk through instruction memory: perfect spatial locality. A loop is temporal locality in its purest form: the same handful of instructions fetched over and over for the life of the loop. This is why instruction caches work so well, and it adds one more reason small, tight loop bodies are fast: the entire loop fits in a few blocks and never misses after the first pass.

Reading locality off a program becomes a quick mental checklist:

• References to the same variable repeatedly: temporal locality (good).
• Stride-1 reference patterns: spatial locality (good); the smaller the stride, the better.
• Loops: both kinds at once for instructions; the smaller the body and the higher the trip count, the better.

Locality as a performance discipline

CS:APP presents locality as a property to recognize; the wider systems literature treats it as a resource to measure and engineer, and two ideas are worth carrying forward.

Locality has a quantitative theory. The notion that a program touches a bounded set of pages in any interval was formalized by Peter Denning as the working-set model (Denning, The Working Set Model for Program Behavior, CACM 1968), the same idea used above to size a cache level against a loop. Denning's model was built for virtual-memory paging — the subject of the next module — but it is the same principle one level down: a program has a footprint, and performance falls sharply when that footprint outgrows the fast store. A related, more predictive tool is the stack distance (or reuse distance): the number of distinct blocks referenced between two accesses to the same block (Mattson et al., Evaluation techniques for storage hierarchies, IBM Systems Journal 1970).¹ A reference hits in a fully-associative LRU cache of $C$ blocks exactly when its reuse distance is less than $C$, so the histogram of reuse distances predicts the miss rate at every cache size from a single trace — the foundation of modern cache-behavior modeling.

Prefetching turns predicted spatial locality into fetched blocks. Fetching a whole block already bets one step ahead; hardware prefetchers bet several. A stride prefetcher watches the address stream, detects a regular stride (exactly the stride-$k$ pattern of this lesson), and issues loads for blocks the program has not asked for yet, so they arrive before the demand miss (Chen & Baer, Effective hardware-based data prefetching for high-performance processors, IEEE Trans. Computers 1995).² This is why a stride-1 sweep of DRAM can approach the bus's peak bandwidth despite paying a miss per block: the prefetcher hides the latency by running ahead of the loop. This sharpens the lesson's advice: regular, small-stride access is cheaper per block and is also the pattern the prefetcher can predict; irregular access defeats both the block and the prefetcher at once.

Locality is the property; the next lesson builds the device that exploits it — the cache memory, and the addressing scheme that decides where each block of memory may live.