Principle of locality (temporal - spatial)

Overview

The principle of locality is the fundamental observation that programs access a relatively small portion of their address space at any given time. This predictable access pattern is the entire reason cache hierarchies work — without locality, caching would be useless.

If programs accessed memory randomly, every access would be equally likely. But real programs have structure, and structure creates predictability.

Two Flavors of Locality

Temporal Locality

Why this happens:

1. Loop counters: for(int i=0; i<n; i++) — variable i accessed every iteration
2. Function calls: The same function code executes multiple times
3. Frequently-used variables: Accumulators, status flags, pointers

Time scale: Milliseconds to seconds in human terms, thousands to millions of cycles in CPU terms.

$\text{Reuse Distance} = \text{count of unique addresses accessed between } A_i \text{ and } A_j$

where $A_i$ and $A_j$ are accesses to the same address.

Short reuse distance = strong temporal locality.

Derivation of why this matters for caching:

Let's say a cache holds $C$ blocks. If the reuse distance for address $X$ is $d$:

• If $d < C$: $X$ is still in cache when re-referenced → cache hit
• If $d \geq C$: $X$ was evicted → cache miss

The hit rate for temporal locality is:

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

This is why larger caches capture more temporal locality — they can hold blocks with longer reuse distances.

Spatial Locality

Why this happens:

1. Sequential instruction execution: Instruction at address 0x1000 is followed by 0x1004
2. Array traversal: a[0], a[1], a[2], ... are contiguous in memory
3. Struct field access: Fields of a struct are adjacent
4. Stack operations: Push/pop access nearby stack addresses

$\text{Stride} = |A_{i+1} - A_i|$

where $A_i$ is the $i$-th memory address accessed.

Stride = 1 word → perfect spatial locality (sequential access) Stride = 0 → pure temporal locality (same location) Large stride → poor spatial locality (jumping around)

Derivation of cache block benefit:

A cache block holds $B$ bytes. When we fetch address $X$, we get $X, X+1, \ldots, X+(B-1)$.

If the program accesses $k$ consecutive addresses starting at $X$ (stride 1), we pay one miss but get $k-1$ hits:

$\text{Hit rate from spatial locality} = \frac{k-1}{k}$

As $k \to B/W$ (where $W$ is word size), hit rate $\to 1 - \frac{W}{B}$.

Example: 64-byte cache block, accessing 16 consecutive words (4 bytes each):

• $k = 16$ words, $B = 64$ bytes = 16 words
• Hit rate = $\frac{15}{16} = 93.75\%$

This is why larger cache blocks exploit spatial locality better — but only up to a point (if stride is large, we fetch useless data).

Working Together: The Locality Combo

int sum = 0;                // sum in register
for (int i = 0; i < 1000; i++) {
    sum += array[i];
}

Temporal locality:

• Variable sum: accessed 1000 times (read it, add to it, store it)
• Variable i: accessed 1000 times
• The loop instructions themselves: executed 1000 times

Spatial locality:

• array[0], array[1], array[2], ... are contiguous in memory
• Fetching array[0] brings array[1..15] into cache block (if 64-byte blocks, 4-byte ints)
• Stride = 4 bytes (one integer)

Why each step matters:

1. First iteration: Cache miss on array[0], loads block containing array[0..15]
2. Next 15 iterations: Cache hits on array[1..15] — spatial locality pays off
3. 16th iteration: Cache miss on array[16], loads array[16..31]
4. Pattern repeats

Total misses = $\lceil 1000 / 16 \rceil = 63$ misses for 1000 accesses → hit rate $= 1 - 63/1000 =$ 93.7% from spatial locality alone.

Add temporal locality: sum, i, and loop code stay in cache (or registers) → hit rate for those is ~100%.

// Row-major storage: A[i][j] at memory address &A + (i*N + j)*sizeof(int)
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Access patterns:

• A[i][k]: Accesses row $i$ sequentially → good spatial locality (stride = 1 element)
• B[k][j]: Accesses column $j$ → stride = $N$ elements (jumps across rows)
  • If $N = 1000$, stride = 4000 bytes (assuming 4-byte ints)
  • Cache block is 64 bytes → only 1 element used per block fetched
  • Terrible spatial locality: 1/16 = 6.25% utilization of fetched data

Why this step is terrible:

• Each B[k][j] access misses in cache
• We fetch 64 bytes but use only 4 bytes
• Bandwidth wasted, performance plummets

Fix: Transpose $B$ first, or use blocking (covered in cache optimization).

Quantifying Locality: The 90/10 Rule

This isn't a law of physics — it's a statistical observation across real workloads.

Why?

• Loops dominate execution time (inner loops executed millions of times)
• Hot functions called repeatedly
• Cold code (error handlers, initialization) rarely runs

Derivation:

Let's model a program with $N$ instructions, where $f$ fraction are "hot" (in loops/frequently called).

If hot instructions execute $R$ times on average, and cold instructions execute once:

$\text{Total execution time} = f \cdot N \cdot R \cdot T + (1-f) \cdot N \cdot T$

where $T$ is time per instruction.

Fraction of time in hot code:

$\frac{f \cdot N \cdot R}{f \cdot N \cdot R + (1-f) \cdot N} = \frac{f \cdot R}{f \cdot R + (1-f)}$

For 90/10 rule: $f = 0.1$, solve for $R$:

$0.9 = \frac{0.1 R}{0.1 R + 0.9}$ $0.09 R + 0.81 = 0.1 R$ $R = 81$

So if 10% of code executes ~81 times on average, you get the 90/10 rule.

Cache implication: If you can keep that 10% of code and its data in cache, you've optimized 90% of execution time.

Common Mistakes & Misconceptions

Why it's wrong: That's temporal locality! Spatial means accessing nearby addresses (different addresses, but close in the address space).

Steel-man: The confusion arises because both improve cache performance, and in practice they often occur together (e.g., looping over an array has both). But the mechanisms differ:

• Temporal: Keep the same block in cache for reuse
• Spatial: Prefetch adjacent blocks because they'll be needed soon

The fix: Remember the etymology: "Temporal" = time (same address over time), "Spatial" = space (nearby in address space).

Why it's wrong: If your stride is large or access pattern is random, you fetch useless data. Larger blocks also mean:

• Fewer blocks fit in cache (for fixed cache size) → worse temporal locality
• Higher miss penalty (more bytes to transfer)
• Conflict misses increase (fewer blocks = more collisions)

Example:

• Cache size = 32 KB
• Block size = 16 bytes → 2048 blocks
• Block size = 256 bytes → 128 blocks

If your working set has 500 distinct blocks with good temporal locality, the 16-byte blocks win (can hold all 500), but 256-byte blocks can only hold 128 → many evictions.

The fix: Optimal block size depends on stride distribution and working set size. Typical sweet spot: 32-128 bytes.

Why Locality Enables the Memory Hierarchy

If these bets pay off, you get:

• Fast memory (cache) holds frequently used data
• Slow memory (DRAM) holds everything else
• Average access time approaches cache speed, not DRAM speed

Derivation of average access time:

Let $h$ = hit rate (fraction of accesses in cache), $T_c$ = cache access time, $T_m$ = DRAM access time.

$T_{\text{avg}} = h \cdot T_c + (1-h) \cdot (T_c + T_m)$

Why both terms? Cache is checked first (always pay $T_c$), then on miss you also pay $T_m$.

Simplify:

$T_{\text{avg}} = T_c + (1-h) \cdot T_m$

Example: $T_c = 1$ ns, $T_m = 100$ ns, $h = 95\%$:

$T_{\text{avg}} = 1 + 0.05 \cdot 100 = 6\text{ ns}$

~17× faster than DRAM (which needs $T_c + T_m = 101$ ns per access) — all because locality makes $h = 0.95$.

If no locality ($h = 0$), $T_{\text{avg}} = 101$ ns → cache is useless overhead.

Connections

• Cache organization fundamentals — how caches exploit locality via blocks and replacement policies
• Cache mapping strategies — direct-mapped vs. set-associative, trading off temporal vs. spatial conflicts
• Working set model — the formalization of locality as "recently used pages"
• Loop blocking and tiling — compiler transformations to improve locality
• Virtual memory — locality across the entire address space enables demand paging

Temporal locality: You keep using the same pencil over and over. Instead of walking to the shelf to get it each time, you just leave it on your desk because you know you'll need it again in 30 seconds. That's temporal — "I just used this, I'll probably use it again soon."

Spatial locality: When you grab your math textbook from the shelf, you also grab your math notebook because it's right next to it, and you'll need it in a minute anyway. That's spatial — "If I need this thing, I probably need the things next to it too."

Caches work the same way. The computer keeps recently-used stuff close (temporal) and grabs nearby stuff together (spatial) because that's what programs do — they're not random, they follow patterns like you doing homework.

Space → Spatial is about SPACE and ADJACENCY (nearby addresses)

Simply: "Temporal = Time, Spatial = Space"

#flashcards/hardware

Concept Map

Hinglish (regional understanding)