Worked examples — Principle of locality (temporal - spatial)

This page is the hands-on companion to the parent note on locality. There we defined the two localities. Here we compute them, one worked example per "flavour of situation" a program can throw at a cache — including the weird degenerate ones (zero reuse distance, infinite stride, random access) that the parent only mentioned in passing.

Before any numbers, let us agree on the two rulers we measure locality with. Both were introduced in the parent, but let us re-anchor them so nothing is assumed.

We will also use one derived quantity all through:

---

The scenario matrix

Every locality problem this chapter can ask is one of these cells. Each worked example below is tagged with the cell(s) it covers, so together they blanket the table.

Cell	Access pattern	Stride	Reuse distance	What it stresses
A	Sequential sweep, stride 1	$=1$ word	$=\infty$ (never reused)	Pure spatial
B	Same address repeated	$=0$	$=0$	Pure temporal
C	Loop over array plus an accumulator	mixed	mixed	Both together
D	Column walk of row-major matrix	$=N$ words (huge)	large	Spatial broken
E	Reuse distance vs cache size boundary	$=1$	$d$ near $C$	Hit ↔ miss threshold
F	Big block, but random / large stride	large	large	Block-size backfire
G	Degenerate: single access, empty loop	undefined	undefined	Edge / limiting case
H	Real-world word problem (image blur)	2-D	mixed	Applied synthesis
I	Exam twist: block size doubles	$=1$	fixed	Trade-off reasoning

---

Example 1 — Cell A: pure spatial locality

Forecast: Guess now — is the hit rate closer to $50\%$ or $90\%$?

1. Convert the block to words. Block $B=64$ bytes, word $W=4$ bytes, so $b=64/4=16$ words per block. Why this step? Locality lives at the granularity of a block: one miss drags in a whole block, so counting in words tells us how many free hits ride along.
2. Count total accesses. $k=64$ words touched, each exactly once (see the sweep in the figure — one blue dot per access, marching right). Why this step? We need the denominator of the hit rate.
3. Apply the sweep formula. $\text{misses}=\lceil 64/16\rceil =4$. Why this step? Every 16th access lands in a fresh block (a miss); the other 15 were already dragged in.

4. Hit rate. $1-4/64=60/64=0.9375=93.75\%$.

Verify: $4$ blocks $\times 16$ words $=64$ words — exactly the array, no under/over-count. Hit rate $15/16$ per block matches the parent's $1-W/B=1-4/64=15/16$. ✓

---

Example 2 — Cell B: pure temporal locality

Forecast: Will sum cause $1000$ misses, or $1$?

1. Reuse distance. Between consecutive sum accesses, zero distinct other addresses appear. So $d=0$. Why this step? $d=0$ is the strongest possible temporal locality — the parent's rule "$d<C\Rightarrow$ hit" is satisfied for any cache with $C\ge 1$.
2. Stride. $|A_{i+1}-A_i|=0$ (same address every time). This is the "stride $=0$ ⇒ pure temporal" cell from the parent. Why this step? Confirms there is no spatial component to explain — it is 100% temporal.
3. Miss count. First access misses (cold), the other $999$ hit. Misses $=1$. Why this step? A block, once loaded, is never evicted because nothing competes for its slot.

Verify: Hit rate $=999/1000=99.9\%$. As accesses $\to \infty$, hit rate $\to 100\%$ — the limiting behaviour of perfect temporal locality. ✓

---

Example 3 — Cell C: both localities at once

Forecast: More or fewer than $100$ misses?

1. Words per block. $b=64/4=16$ words. (Why: same granularity argument as Ex 1.)
2. Spatial part — array. Stride $=4$ bytes $=1$ word ⇒ sequential. Misses $=\lceil 1000/16\rceil =63$. Why this step? $1000/16=62.5$, and we round up — that last half-block still costs a whole miss.
3. Temporal part — sum, i. Reuse distance $\approx 0$ (registers, no eviction) ⇒ $\approx 0$ misses. Why this step? The parent's combo example: temporal keeps hot scalars, spatial streams the array.
4. Overall array hit rate. $1-63/1000=93.7\%$.

Verify: $\lceil 1000/16\rceil =63$; matches the parent's stated $93.7\%$ exactly. ✓

---

Example 4 — Cell D: spatial locality broken (column walk)

Forecast: Is the hit rate here closer to $93\%$ (like Ex 3) or near $0\%$?

1. Address gap between rows. B[k][j] sits at &B + (k·1000 + j)·4 bytes. Stepping k → k+1 jumps $1000\times 4=4000$ bytes. Why this step? Stride is the whole diagnostic here — see the figure: consecutive accesses (red arrows) leap across entire rows.

2. Stride vs block. Stride $=4000$ bytes $\gg 64$-byte block. Each access lands in a different block. Why this step? If the jump exceeds one block, none of the neighbours we fetched will be reused.
3. Utilisation of a fetched block. Of the 16 ints dragged in, we use $1$: $1/16=6.25\%$. Why this step? Quantifies "wasted bandwidth" — the parent's terrible-spatial-locality case.
4. Misses. Effectively one miss per access ⇒ $1000$ misses for $1000$ column reads.

Verify: Utilisation $1/16=0.0625=6.25\%$, wasted $=93.75\%$ — the mirror image of Ex 1's hit rate. See Loop blocking and tiling for the fix. ✓

---

Example 5 — Cell E: the reuse-distance / cache-size threshold

Forecast: Which of $d=7$ or $d=8$ still hits?

1. Recall the rule. From the parent: $d<C\Rightarrow$ hit, $d\ge C\Rightarrow$ miss (LRU cache). Why this step? The whole point of Cell E is to sit exactly on this inequality.
2. Case $d=7$. $7<8$ ⇒ hit. The 7 intervening blocks plus $X$ = 8 blocks, all fit. Why this step? $X$ is the least-recently-used but has not been pushed out yet.
3. Case $d=8$. $8\nless 8$ ⇒ miss. Eight other blocks arrived, filling all 8 slots and evicting $X$. Why this step? Shows the razor edge: adding one more intervening block flips hit to miss.

Verify: Boolean check: $(7<8)=\text{True}$ (hit), $(8<8)=\text{False}$ (miss). The threshold is strict inequality. See Working set model. ✓

---

Example 6 — Cell F: bigger block backfires

Forecast: Which block size holds the whole working set?

1. Blocks that fit — 16 B block. $32,768/16=2048$ slots. Working set $=500$ blocks $<2048$ ⇒ all fit, near-zero capacity misses. Why this step? Temporal locality only pays off if the reused blocks stay resident.
2. Blocks that fit — 256 B block. $32,768/256=128$ slots. Working set (500 items, each in its own 256 B block because access is scattered) $>128$ ⇒ constant eviction. Why this step? Fewer, fatter blocks means fewer distinct items resident — the parent's warning made numeric.
3. Wasted bytes with 256 B block. Each fetch drags 256 B but only 16 B is wanted: $16/256=6.25\%$ used. Why this step? Random access gives no spatial payoff to offset the lost temporal capacity.

Verify: $2048>500$ (16 B fits), $128<500$ (256 B thrashes). Bigger is worse here. See Cache organization fundamentals. ✓

---

Example 7 — Cell G: degenerate / limiting inputs

Forecast: Does a $0$-iteration loop cause $0$ misses or $1$?

1. (a) Empty loop. $k=0$ accesses ⇒ $\lceil 0/b\rceil =0$ misses. Hit rate is undefined ($0/0$), not $0\%$. Why this step? Division by zero total accesses — you must say "undefined", not silently print $0$.
2. (b) Single access. $k=1$: $\lceil 1/16\rceil =1$ miss, hit rate $=1-1/1=0\%$. Reuse distance undefined (no second access). Why this step? A lone cold miss is the floor of locality — nothing to exploit yet.
3. (c) Exact multiple, $k=32,b=16$. $\lceil 32/16\rceil =2$ — no rounding penalty because $32/16=2$ is already an integer. Why this step? Shows the ceiling only bites when there is a remainder; here it is a clean $2$.

Verify: $\lceil 0/16\rceil =0$; $\lceil 1/16\rceil =1$; $\lceil 32/16\rceil =2$. All three edge values confirmed. ✓

---

Example 8 — Cell H: real-world word problem (image blur)

Forecast: Good or bad locality for a horizontal sweep of the centre row?

1. Stride along the row. Moving j → j+1 steps $1$ byte (chars are contiguous). Stride $=1$ B $\ll 64$ B block. Why this step? Horizontal moves within a row are the good direction in row-major storage.
2. Misses for one row. $k=1920$ bytes, $b=64$ bytes: $\lceil 1920/64\rceil =30$ misses. Why this step? $1920/64=30$ exactly — sweeping the row costs 30 cold block loads.
3. Neighbour rows. Row above and below are $1920$ bytes away — a different block, but each is itself swept sequentially, so they too get $30$ misses each, then reused. Why this step? The three rows of the stencil each stream well individually; the vertical gap is paid once, not per pixel.
4. Row hit rate. $1-30/1920=98.4\%$.

Verify: $\lceil 1920/64\rceil =30$; hit rate $1-30/1920=0.984375=98.4375\%$. Row-major + horizontal sweep = strong spatial locality. ✓

---

Example 9 — Cell I: exam twist (double the block)

Forecast: Do misses halve to ~$31$?

1. New sweep misses. $b=32$: $\lceil 1000/32\rceil =32$ misses. Why this step? Directly apply the sweep formula with the bigger $b$ — spatial locality improves.
2. Compare. $63\to 32$ misses, roughly halved — good for this pure-sequential pattern. Why this step? Confirms the naive "bigger block = fewer misses" intuition when stride is 1.
3. The hidden cost. For fixed cache size, doubling block halves the number of blocks (Ex 6's lesson) and doubles the miss penalty (twice the bytes per transfer). Why this step? The exam trap: report the win and the two costs, or you only earn half marks.

Verify: $\lceil 1000/32\rceil =32$ vs previous $63$ — nearly halved, exactly as claimed. ✓

---

Recall Quick self-test

A stride-0 access pattern has which locality? ::: Pure temporal (same address repeatedly, reuse distance 0). Reuse distance $d=C$ on an LRU cache with $C$ blocks — hit or miss? ::: Miss (rule is $d<C$ strict). Why can a bigger cache block lower the hit rate? ::: Fewer blocks fit ⇒ worse temporal capacity, plus wasted bytes when stride is large. A $0$-iteration loop: how many misses and what hit rate? ::: $0$ misses; hit rate undefined ($0/0$), not $0\%$.

Related deeper dives: Cache mapping strategies · Virtual memory · Working set model · Loop blocking and tiling.