---
title: Locality
module: The Memory Hierarchy
moduleNumber: 6
lessonNumber: 2
order: 602
summary: >
  A hierarchy only pays off because programs do not touch memory at random. They
  reuse recently-used data (temporal locality) and touch nearby data soon after
  (spatial locality). We make both precise and then quantitative: miss rates for
  stride-1 and stride-k traversals against a concrete block size, and the loop-order
  pair on a 2-D array where the same sum misses 16 times one way and 64 times the
  other — why row-major versus column-major order can change a program's speed by
  an order of magnitude.
topics: [The Memory Hierarchy]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §6 The Memory Hierarchy"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §7–9 The Memory Hierarchy / The Cache / Main Memory"
---

The [last lesson](/computer-architecture/memory-hierarchy/storage-technologies-and-the-latency-gap)
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.

> **Definition (Temporal locality).** A memory location that is referenced once is
> likely to be referenced again soon. The loop counter, the accumulator in a sum,
> the top of the stack — all are hit over and over within a short window.

> **Definition (Spatial locality).** If a location is referenced, locations with
> nearby addresses are likely to be referenced soon. Walking an array, executing
> straight-line code, reading the fields of a struct — each touches a contiguous
> run of addresses.

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](/computer-architecture/memory-hierarchy/storage-technologies-and-the-latency-gap)
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.

$$
% caption: Temporal locality reuses the same address over time; spatial locality
% caption: touches neighboring addresses in sequence. The hierarchy answers the
% caption: first by keeping items resident and the second by fetching whole blocks.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % temporal: one address hit at several times
  \draw[->] (0,0) -- (4.4,0) node[anchor=north] {time};
  \draw[->] (0,0) -- (0,2.3) node[anchor=east] {addr};
  \node[anchor=south east] at (4.4,2.3) {\textbf{temporal}};
  \foreach \t in {0.5,1.3,2.1,2.9,3.7}
    \fill[acc] (\t,1.2) circle (2.4pt);
  \node[anchor=east,text=acc] at (-0.05,1.2) {$a$};
  % spatial: rising staircase of neighbors
  \begin{scope}[xshift=6.4cm]
    \draw[->] (0,0) -- (4.4,0) node[anchor=north] {time};
    \draw[->] (0,0) -- (0,2.3) node[anchor=east] {addr};
    \node[anchor=south east] at (4.4,2.3) {\textbf{spatial}};
    \foreach \i in {0,1,2,3,4}
      \fill[acc] (0.6+\i*0.78,0.3+\i*0.38) circle (2.4pt);
  \end{scope}
\end{tikzpicture}
$$

### 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`:

```c [runmax.c]
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 `int`s are 4 bytes, and abbreviate `m`'s home
as $m$. The stream of memory addresses, in issue order, is

$$
m,\; 0,\; m,\; 4,\; m,\; 8,\; m,\; 12,\; m,\; 16,\; m,\; 20,\; m,\; 24,\; m,\; 28.
$$

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, \ldots$ 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.

$$
% caption: The reference stream of runmax, plotted as address against issue order.
% caption: The accumulator m is one address revisited every other step (a f\/lat run of
% caption: temporal reuse); the array addresses climb one element per step (a staircase
% caption: of spatial locality). Real programs braid the two.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (8.6,0) node[anchor=north] {issue order};
  \draw[->] (0,0) -- (0,3.0) node[anchor=east] {addr};
  % m at a low f\/ixed height, odd steps
  \foreach \t in {1,3,5,7,9,11,13,15}
    \fill[black] (\t*0.52,0.35) circle (2.2pt);
  \node[anchor=east,black] at (-0.05,0.35) {$m$};
  % array addresses climbing, even steps
  \foreach \t/\h in {2/0.6,4/0.9,6/1.2,8/1.5,10/1.8,12/2.1,14/2.4,16/2.7}
    \fill[acc] (\t*0.52-0.52,\h) circle (2.2pt);
  \node[anchor=south west,text=acc] at (7.4,2.55) {$a[i]$: spatial};
  \node[anchor=north west,black] at (7.4,0.5) {$m$: temporal};
\end{tikzpicture}
$$

## 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.

```c [sumvec.c]
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 `int`s. 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 `int`s, one miss in sixteen.

> **Definition (Stride).** The constant address gap between successive references
> of a pattern, measured in elements. A **stride-1** (unit-stride) pattern walks
> contiguous memory and has excellent spatial locality. A **stride-$k$** pattern
> skips $k-1$ elements each step; as $k$ grows, fewer of the elements in a fetched
> block are used, and spatial locality decays.

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

$$
\text{miss rate} = \min\!\left(1,\; \frac{k \cdot w}{B}\right).
$$

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.

$$
% caption: What a stride-k walk does to fetched blocks (B = 16 bytes, 4 ints per
% caption: block; shaded cells are the ints actually referenced, heavy rules are
% caption: block boundaries). Stride 1 uses all four ints per block and misses once
% caption: per four references; stride 2 uses two; stride 4 uses one, so every
% caption: reference misses.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % three rows: stride 1, 2, 4 over 16 int cells (4 blocks of 4)
  \foreach \r/\stride/\lab in {0/1/{miss rate 1{/}4}, 1/2/{miss rate 1{/}2}, 2/4/{miss rate 1}} {
    \pgfmathsetmacro{\y}{-\r*1.15}
    \node[anchor=east] at (-0.35,\y+0.275) {stride \stride};
    % cells
    \foreach \c in {0,...,15} {
      \pgfmathsetmacro{\touched}{Mod(\c,\stride)==0 ? 1 : 0}
      \ifdim \touched pt > 0.5pt
        \draw[fill=acc!25] (\c*0.55,\y) rectangle ++(0.55,0.55);
      \else
        \draw[black] (\c*0.55,\y) rectangle ++(0.55,0.55);
      \fi
    }
    % heavy block boundaries every 4 cells
    \foreach \b in {0,4,8,12,16}
      \draw[very thick] (\b*0.55,\y) -- (\b*0.55,\y+0.55);
    \draw[very thick] (0,\y) -- (8.8,\y);
    \draw[very thick] (0,\y+0.55) -- (8.8,\y+0.55);
    \node[anchor=west,text=acc] at (9.05,\y+0.275) {\lab};
  }
\end{tikzpicture}
$$

## 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.

```c [traverse.c]
/* 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.

$$
% caption: Two traversals of a row-major matrix. Row-major order (left) walks each
% caption: row contiguously — stride-1, every block fully used. Column-major order
% caption: (right) steps down a column, jumping one full row (stride-N) each access.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  cellbox/.style={draw, minimum width=7mm, minimum height=7mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % left grid: row-major, highlight a full row
  \foreach \r in {0,1,2,3}
    \foreach \c in {0,1,2,3} {
      \ifnum\r=1
        \node[cellbox, fill=acc!8] at (\c*0.8,-\r*0.8) {};
      \else
        \node[cellbox] at (\c*0.8,-\r*0.8) {};
      \fi
    }
  \draw[->,acc,thick] (-0.05,-0.8) -- (2.55,-0.8);
  \node[anchor=north,align=center] at (1.2,-3.4) {row-major: stride-1\\(scan a row)};
  % right grid: column-major, highlight a full column
  \begin{scope}[xshift=5.6cm]
    \foreach \r in {0,1,2,3}
      \foreach \c in {0,1,2,3} {
        \ifnum\c=1
          \node[cellbox, fill=acc!8] at (\c*0.8,-\r*0.8) {};
        \else
          \node[cellbox] at (\c*0.8,-\r*0.8) {};
        \fi
      }
    \draw[->,acc,thick] (0.8,0.05) -- (0.8,-2.55);
    \node[anchor=north,align=center] at (1.2,-3.4) {column-major: stride-N\\(scan a column)};
  \end{scope}
\end{tikzpicture}
$$

### Counting the misses

Put numbers on it. Let `A` be `int A[8][8]` (256 bytes: 16 blocks of $B = 16$
bytes, four `int`s 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.

$$
% caption: Miss maps for the two traversals of an 8x8 int matrix with 16-byte blocks
% caption: and a small cache (shaded cell = miss). Rowwise misses once per block: 16
% caption: of 64. Columnwise misses on every access: 64 of 64, because each step lands
% caption: in a different, since-evicted block.
\begin{tikzpicture}[font=\footnotesize,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % left: rowwise misses at j = 0 and 4
  \foreach \r in {0,...,7}
    \foreach \c in {0,...,7} {
      \pgfmathsetmacro{\m}{Mod(\c,4)==0 ? 1 : 0}
      \ifdim \m pt > 0.5pt
        \draw[fill=acc!25] (\c*0.44,-\r*0.44) rectangle ++(0.44,0.44);
      \else
        \draw[black] (\c*0.44,-\r*0.44) rectangle ++(0.44,0.44);
      \fi
    }
  \node[anchor=north,align=center] at (1.76,-3.4) {rowwise\\16 misses of 64};
  % right: columnwise misses everywhere
  \begin{scope}[xshift=6.2cm]
    \foreach \r in {0,...,7}
      \foreach \c in {0,...,7}
        \draw[fill=acc!25] (\c*0.44,-\r*0.44) rectangle ++(0.44,0.44);
    \node[anchor=north,align=center] at (1.76,-3.4) {columnwise\\64 misses of 64};
  \end{scope}
\end{tikzpicture}
$$

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.

> **Definition (Working set).** The set of blocks a program references within a
> given window of time. When the working set fits in a cache level, its temporal
> reuse is captured there and the miss rate is low; when the working set exceeds
> the level, blocks are evicted before they are reused, and reuse turns back into
> misses — a **capacity** limit, developed in the
> [direct-mapped lesson](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped).

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 `int`s (4 KB)
that fits in a 32 KB L1 pays cold misses once and then reuses freely; summing 10
million `int`s (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](/computer-architecture/memory-hierarchy/cache-performance-and-cache-friendly-code).

## 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:

```c [layouts.c]
/* 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 `double`s per block). Under **AoS**,
each particle's four `double`s — 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$ `double`s 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.

$$
% caption: Array-of-structs versus struct-of-arrays, reading only positions with a
% caption: block of eight doubles (shaded = fetched and used, hollow = fetched but
% caption: wasted). AoS interleaves the unused mass into every block; SoA packs the
% caption: swept f\/ield contiguously so every fetched double is used.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  d/.style={draw, minimum width=6mm, minimum height=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % AoS row: x y z m x y z m  (m hollow)
  \node[anchor=east] at (-0.3,0) {AoS block};
  \foreach \i/\lab/\use in {0/x/1,1/y/1,2/z/1,3/m/0,4/x/1,5/y/1,6/z/1,7/m/0} {
    \ifnum\use=1 \node[d, fill=acc!25] at (\i*0.66,0) {$\lab$};
    \else \node[d] at (\i*0.66,0) {$\lab$};\fi
  }
  \node[anchor=west,black] at (5.5,0) {6 of 8 used};
  % SoA row: x x x x x x x x (all used)
  \node[anchor=east] at (-0.3,-0.9) {SoA block};
  \foreach \i in {0,...,7}
    \node[d, fill=acc!25] at (\i*0.66,-0.9) {$x$};
  \node[anchor=west,text=acc] at (5.5,-0.9) {8 of 8 used};
\end{tikzpicture}
$$

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](/computer-architecture/virtual-memory/address-spaces-and-translation) —
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).[^mattson] 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).[^prefetch] 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.

> **Takeaway.** Programs reference memory non-randomly: **temporal** locality reuses
> recent addresses, **spatial** locality touches nearby ones. Loops over arrays are
> the prime example, and the arithmetic is exact: a stride-$k$ walk over $w$-byte
> elements misses at rate $\min(1, kw/B)$, so stride-1 with 16-byte blocks misses
> once in four while stride-4 misses always. Because C is row-major, looping with
> the rightmost index innermost keeps stride-1; on an 8x8 `int` matrix the wrong
> order turns 16 misses into 64. Same arithmetic, same instructions — only the
> locality differs, and locality sets the cost.

Locality is the property; the next lesson builds the device that exploits it — the
[cache memory](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped),
and the addressing scheme that decides where each block of memory may live.

[^mattson]: **R. L. Mattson, J. Gecsei, D. R. Slutz, I. L. Traiger**, "Evaluation techniques for storage hierarchies," _IBM Systems Journal_ 9(2), 1970 — introduces stack (reuse) distance and stack algorithms, letting a single trace yield the miss rate at every cache size at once.
[^prefetch]: **T.-F. Chen, J.-L. Baer**, "Effective hardware-based data prefetching for high-performance processors," _IEEE Transactions on Computers_ 44(5), 1995 — stride-detecting hardware prefetchers that issue loads ahead of demand misses for regular access patterns.