5.4.1 · D5Memory Hierarchy & Caches
Question bank — Principle of locality (temporal - spatial)
This is a thinking gym for the principle of locality. Every item below hides a common trap or a boundary case. Read the prompt, answer out loud before you reveal, and check that your reasoning — not just your verdict — matches. A bare "true" or "false" is worth nothing here; the why is the whole point.
True or false — justify
Re-reading a variable inside a loop is temporal locality
True — the same address is touched again after a short time gap, which is exactly the "recently used → soon reused" pattern.
Walking array[0], array[1], array[2] is temporal locality
False — these are different, nearby addresses, so this is spatial locality; temporal would require revisiting the same address.
A program with zero locality could still benefit from a big cache
False — if accesses are truly uniform-random over a space far larger than the cache, every access is roughly equally likely to be evicted, so the cache is dead weight; locality is what makes caching pay off at all.
Spatial and temporal locality are mutually exclusive
False — most real loops (e.g. array sum) have both: array elements give spatial locality while the loop counter, accumulator, and instructions give temporal locality.
Stride-1 access has strong spatial locality
True — each next address is one word away, so it lands in the same cache block already fetched, turning one miss into many hits.
Stride-0 access is spatial locality
False — a stride of 0 means you keep hitting the same address, which is pure temporal locality; spatial requires movement to nearby-but-different addresses.
Larger cache blocks always raise the hit rate
False — bigger blocks help only when the stride is small; with large or random strides you fetch mostly useless bytes, and for a fixed cache size you also hold fewer blocks, hurting temporal locality.
The 90/10 rule is a law of physics
False — it is an empirical statistical observation across real workloads, arising because inner loops execute enormously more often than cold code, not from any fundamental principle.
Sequential instruction fetch is a source of spatial locality
True — the instruction after address
0x1000 is usually 0x1004, so fetching a block of instructions serves several upcoming fetches from one memory access.A cache miss on array[0] means array[1] will also miss
False — the miss on
array[0] loads the whole block containing several following elements, so array[1..15] (for 64-byte blocks, 4-byte ints) are then hits thanks to spatial locality.Spot the error
"Temporal locality means data stored close together in memory."
The error swaps the definitions: closeness in memory is spatial; temporal is closeness in time (the same address reused soon).
"To exploit temporal locality, prefetch the next few blocks."
Prefetching adjacent blocks exploits spatial locality; temporal locality is exploited by keeping the reused block resident long enough for its next reference.
"Column access of a row-major matrix has good spatial locality because we still touch the array."
Touching the array isn't enough — column access has stride = N elements, so each fetched block yields only one useful element and the rest is wasted, i.e. terrible spatial locality.
"If reuse distance is 5 and the cache holds 5 blocks, the re-reference is guaranteed a hit."
With reuse distance and capacity , the condition for a hit is ; here , so the block may have just been evicted — it is a (potential) miss, not a guaranteed hit.
"Bigger blocks are strictly better because miss penalty doesn't change."
Bigger blocks raise miss penalty — more bytes must be transferred per miss — and shrink the block count, so this is doubly wrong.
"Since the 90/10 rule says 10% of code runs 90% of the time, that 10% runs 9× more often per instruction."
The multiplier isn't 9; solving the model gives the hot code executing about 81 times on average, because you must account for the 10%/90% code-size split as well as the time split.
"Spatial locality helps only for data, not for instructions."
Instructions have strong spatial locality too — sequential execution marches through consecutive addresses, which is why instruction caches exploit block fetch heavily.
Why questions
Why does looping over an array give a ~93.7% hit rate even before any temporal reuse
Each 64-byte block holds 16 four-byte ints; one miss loads the block and the next 15 accesses hit, giving purely from spatial locality.
Why does transposing matrix fix the matrix-multiply slowdown
Transposing turns the strided column walk of
B[k][j] into a stride-1 row walk, so each fetched block is fully used instead of yielding one element out of sixteen.Why do larger caches capture more temporal locality
A larger cache holds more blocks , so addresses with longer reuse distances still satisfy and remain resident when re-referenced instead of being evicted.
Why can a large stride make big cache blocks actively harmful
With a big stride you use only one word of each fetched block, so a larger block wastes more bandwidth per useful byte and evicts other useful blocks to make room for junk.
Why is the loop counter i an example of temporal locality rather than spatial
i lives at one fixed address that is read and written every iteration — the same location reused over time — which is the definition of temporal, not spatial, locality.Why does the 90/10 rule matter for cache design
If just 10% of the code (and its data) captures 90% of execution time, keeping that hot fraction resident optimizes almost all of the program's running cost.
Why do spatial and temporal locality "often occur together but by different mechanisms"
They co-occur in loops over arrays, yet spatial is served by fetching adjacent blocks and temporal by retaining the same block — improving one does not automatically improve the other.
Edge cases
What is the locality of accessing a single hardware register in a tight loop
Pure temporal locality (stride 0) and no spatial locality — the same location is hammered, but no neighbouring addresses are touched.
What happens to the spatial hit rate as consecutive-access count grows toward one block's worth of words
The spatial hit rate approaches (word size over block size); it never reaches 100% because the very first access of each block is always a compulsory miss.
If reuse distance equals cache capacity () exactly, hit or miss
Boundary case — the strict condition for a hit is , so at the block has typically been evicted and the re-reference misses.
What is the locality of truly uniform-random memory access over a huge space
Effectively none — no address is more likely than another and the working set exceeds the cache, so caching gives negligible benefit and the hierarchy performs near main-memory speed.
Does a block size equal to the whole cache make sense
No — that leaves exactly one block, destroying temporal locality (any second working-set block evicts the first) and maximizing miss penalty; it only "works" for a single perfectly sequential stream.
What locality does the return-address stack exhibit during many nested calls
Both — pushes and pops touch nearby stack addresses (spatial) and the same stack slots are revisited as frames unwind (temporal).
Recall Quick self-test
Spatial vs temporal in one line each ::: Spatial = nearby-but-different addresses soon; temporal = same address soon. Hit condition in terms of reuse distance and capacity ::: Hit when reuse distance cache capacity ; miss when .