Principle of locality (temporal - spatial): Visual walkthrough

This page builds ONE result from nothing: why does a program that reuses memory and reads it in order get so many cache hits? We will earn every symbol with a picture, then combine them into a single formula. If you have never seen a cache before, start here — we define it in Step 1.

Parent: Principle of locality (temporal - spatial). Related: Cache organization fundamentals, Cache mapping strategies, Working set model, Loop blocking and tiling.

Step 1 — What a cache actually is (the drawer picture)

WHAT. Main memory is huge and slow. A cache is a tiny, fast copy of some of it, sitting close to the CPU. Think of memory as a giant warehouse of numbered boxes, and the cache as a small desk that holds only a handful of those boxes at a time.

WHY. Every symbol below refers to this desk. Before we talk about "hits" and "misses" we must fix what the desk holds. We call each box a block (a fixed chunk of bytes fetched together), and we say the desk holds $C$ blocks.

PICTURE. The red desk on the right holds only $C = 4$ blocks. The black warehouse on the left has thousands.

Cache capacity

C

= the number of blocks the desk can hold at once.

Step 2 — The access stream (turning a program into a list)

WHAT. A running program is, from memory's point of view, just a list of addresses it asks for, in order. Call the $i$ -th address $A_{i}$ .

$A_{1}, A_{2}, A_{3}, \dots, A_{i}, \dots$

$A_{i}$ :: the address requested at the $i$ -th step in time — one dot on a timeline.
The subscript $i$ :: the clock tick, not the address itself. Two different ticks can ask for the same address.

WHY. We cannot reason about "loops" or "arrays" directly — they are too varied. But every program collapses to this stream, so if we prove something about streams we prove it about all programs. This is the trick that makes the whole theory possible.

PICTURE. Time runs left to right; each mark is one access. The red marks below are two accesses to the same address — that repeat is the seed of temporal locality.

Step 3 — Temporal locality: the reuse-distance ruler

WHAT. Take one address that appears twice, at ticks $i$ and $j$ (with $i < j$ ). Count how many distinct addresses were touched strictly between them. That count is the reuse distance $d$ .

$d = {distinct addresses in A_{i + 1}, \dots, A_{j - 1}}$

The bars $∣ {\dots} ∣$ :: "how many items are in this set" — a plain count.
distinct :: we count each different address once, even if it repeated. This is what fills the desk.
Small $d$ :: the repeat came back soon → strong temporal locality.

WHY count distinct, not total? Because the desk is evicted by variety, not by volume. If between your two visits you touched the same 3 addresses 100 times, only 3 desk-slots got used. What kicks your block off the desk is 3 new things, not 300 repeats.

PICTURE. The red span is the reuse distance — the ruler between the two red marks of Step 2, counting the distinct black marks it crosses.

Step 4 — The hit/miss cut: comparing $d$ against $C$

WHAT. Here is the hinge of the whole page. In a fully-associative LRU desk (our assumption up top), your block survives only if fewer than $C$ distinct other blocks arrived while you were away. So, for a re-access (not a first reference):

re-access is a {hit miss if d < C if d \geq C

$d < C$ :: fewer newcomers than desk-slots → your block never got pushed off → hit.
$d \geq C$ :: at least $C$ newcomers → they filled every slot and evicted you → miss.

WHY this exact comparison? Because a desk of $C$ slots can hold at most $C$ blocks, and LRU only throws out the oldest-used one. If $C$ or more different blocks visit while you are gone, one of them takes your slot. The number " $C$ " is literally the number of things you can survive alongside.

PICTURE. Two reuse arcs over the same stream: the short red arc ( $d < C$ ) lands on a hit; the long grey arc ( $d \geq C$ ) lands on a miss because too many distinct blocks filled the desk in between.

Step 5 — Turning the cut into a hit rate

WHAT. Every access is exactly one of three things: a compulsory miss (first-ever reference, Step 3), a capacity/temporal hit ( $d < C$ ), or a capacity miss ( $d \geq C$ ). Group them:

$total = d < C hits H + d \geq C M_{cap} + first refs M_{cold}$

$H$ :: number of re-accesses that hit.
$M_{cap}$ :: re-accesses that missed because the desk was too small.
$M_{cold}$ :: first references, which must miss no matter how big the desk is.

The exact hit rate is therefore

$P (hit) = \frac{H}{H + M _{cap} + M _{cold}} .$

WHY the earlier version had a " $\approx$ ". People often quote

$P (hit) \approx \frac{# { accesses with d < C }}{total accesses},$

which silently lumps the cold misses in with the total but not the numerator, and (in a real cache) ignores conflict misses too. That is why it is only an approximation: it is a lower-bound sketch that becomes exact for a fully-associative LRU cache once you subtract the compulsory misses, since then $M_{cold} = 0$ inside the reuse-only stream.

$# {\dots}$ :: "the number of accesses for which the condition holds".
the fraction :: a probability between $0$ and $1$ ; multiply by $100$ to read it as a percent ( $%$ ).

WHY a fraction at all? A hardware designer cannot fix one access; they design for the typical one. The fraction is the chance a random access hits — the number that decides whether a program feels fast or slow.

PICTURE. A tall bar of all accesses split into three bands: the red band ( $d < C$ hits), a grey capacity-miss band, and a thin cold-miss band that no cache can remove.

Step 6 — Spatial locality: one miss pays for many hits

WHAT. So far a block was one address. But a real block holds $B$ bytes. Memory is addressed in fixed chunks called words; let $W$ be the bytes per word (e.g. $W = 4$ for a 32-bit integer). A block therefore holds

$k = \frac{B}{W} words,$

$B$ :: bytes per block — the width of one desk-slot.
$W$ :: bytes per word — the size of one element the program actually reads.
$k = B / W$ :: how many words ride in one block. For $B = 64, W = 4$ : $k = 16$ .

When you miss on address $X$ , the desk grabs the whole block $X, X + W, \dots, X + (k - 1) W$ for free in the same trip. If your next accesses are the neighbours — a stride of one word — they are already there.

$stride = ∣ A_{i + 1} - A_{i} ∣, stride = W \Rightarrow sequential$

stride :: the jump between consecutive addresses. One word = walk next door; large = teleport across town.

WHY does this give hits for free? Because the slow part of a memory trip is the trip itself, not the size of what you carry back. Carrying $k$ neighbours costs almost the same as carrying $1$ , so the memory system carries them all and bets you will want them.

PICTURE. One red miss fetches a whole block ( $k = 16$ words shown); the next $k - 1 = 15$ sequential accesses land inside it as hits.

The spatial hit rate. If you sequentially touch all $k$ words of the fetched block:

$P (hit)_{spatial} = \frac{k - 1}{k}$

$k - 1$ :: the neighbours already on the desk (hits).
$k$ :: total accesses in the run (the one miss $+$ the $k - 1$ hits).

From $\frac{k - 1}{k}$ to $1 - \frac{W}{B}$ — the missing algebra. Split the fraction:

$\frac{k - 1}{k} = \frac{k}{k} - \frac{1}{k} = 1 - \frac{1}{k} .$

Now substitute $k = B / W$ , so $\frac{1}{k} = \frac{1}{B / W} = \frac{W}{B}$ . Hence

$P (hit)_{spatial} = 1 - \frac{1}{k} = 1 - \frac{W}{B} .$

That is why the single-word share $\frac{1}{k}$ equals $\frac{W}{B}$ : one word out of $k$ is the one word ( $W$ bytes) out of the whole block ( $B$ bytes). Worked numbers: $B = 64, W = 4 \Rightarrow k = 16$ , so $1 - \frac{W}{B} = 1 - \frac{4}{64} = \frac{15}{16} = 0.9375 = 93.75%.$

Step 7 — The degenerate cases (one figure each, never let the reader hit an unshown scenario)

Three corners where the formulas above bend. Each gets its own picture.

The one-picture summary

Everything above is a single chain: a program becomes a stream (Step 2); a first reference is always a cold miss (Step 3); repeats measured by reuse distance $d$ hit when $d < C$ in a fully-associative LRU cache (Step 4); neighbours measured by stride ride along for free when stride is one word (Step 6); counting hits against all three miss types gives $P (hit)$ (Step 5); and the corners (Step 7) show where each mechanism dies.

Recall Feynman retelling — say it like you'd explain to a friend

Picture a tiny desk next to your chair and a huge warehouse down the hall. Working from the warehouse is slow, so you keep the boxes you're using on the desk. A program is just a list of "fetch box #…" requests. The first time you ask for any box it can't already be on the desk — that's a cold miss, unavoidable. Temporal locality says: you'll probably ask for a box again soon — and in a desk that lets any box sit anywhere and throws out the box used longest ago, as long as fewer different boxes than your desk holds ( $C$ ) showed up in between, yours is still there: a hit. (If the desk forces each box into a fixed spot, two boxes fighting over that spot can knock each other off even when the count says they shouldn't — that's a conflict miss.) Spatial locality says: boxes ship in bundles of $k = B / W$ words, so grabbing one hands you its neighbours free — and since programs read in order, those neighbours are what you want next, giving $\frac{k - 1}{k} = 1 - \frac{W}{B}$ hits per miss. Both break the same way: too small a desk, or teleporting to far boxes (big stride). That's the whole theory of why caches work.

Which condition makes a temporal re-access a hit, and under what cache assumption?

d < C

, assuming a fully-associative cache with LRU replacement; direct-mapped/set-associative designs add conflict misses.

Why count distinct addresses for reuse distance?

Only distinct blocks consume desk slots and cause eviction; repeats don't fill the cache.

How is the block word-count

k

related to

B

and

W

k = B / W

(bytes per block divided by bytes per word).

Why does

\frac{1}{k}

equal

\frac{W}{B}

in the spatial formula?

Because

k = B / W

, so

1/ k = W / B

— one word of

W

bytes out of a block of

B

bytes.

What is a compulsory (cold) miss and why can't a bigger cache remove it?

The first-ever reference to a block; it was never fetched before, so no cache size could have held it.

When does a large block hurt?

It reduces the block count for a fixed cache size, shrinking effective capacity and weakening temporal locality, and raises conflict pressure.