Temporal Locality
If you touched something recently, you will probably touch it again. That assumption is what makes keeping copies worthwhile at all — and it is why the size of the data you revisit, rather than the size of the data you own, determines whether a program is fast.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Reuse distance decides residency
The useful quantity is not time but reuse distance: how many distinct lines you touch between two accesses to the same line. If that number is comfortably below what the cache holds, the second access hits. If it exceeds capacity, the line was evicted and you pay a full miss — even though your code "just used it".
This is why total data size is the wrong metric. A program with a gigabyte of data that repeatedly sweeps a small hot region has excellent temporal locality; a program with a few megabytes that touches all of it between reuses has none. The predictive quantity is the Working Set: Why Performance Falls Off a Cliff, and it is a property of the access pattern rather than of the allocation.
It also explains a genuinely counter-intuitive result: fusing two loops into one is not always faster. Fusing halves the number of passes, but if the fused body touches two large arrays it may double the reuse distance for both, converting hits into misses. Whether fusion wins depends on whether the combined footprint still fits — which is measurable and not guessable.
1// Naive: full pass over B for every element of A2for (i in 0..N)3 for (j in 0..N)4 c[i] += a[i] * b[j];5 6// Reuse distance for b[j] is the whole of b.7// If b exceeds the cache, every pass re-fetches all of it.1// Blocked: work on a tile of b that stays resident2for (jj in 0..N step BLOCK)3 for (i in 0..N)4 for (j in jj..jj+BLOCK)5 c[i] += a[i] * b[j];6 7// Reuse distance for the tile is BLOCK, not N.8// Choose BLOCK so the tile stays in cache.Identical operations in a different order. Blocking does not reduce arithmetic at all — it reduces reuse distance so that data is still resident when it is needed again. This is the core idea behind Matrix Tiling: Same Arithmetic, Ten Times Faster and behind cache-oblivious algorithm design.
What "still there" actually depends on
Capacity is the obvious factor, but it is not the only one. A line can be evicted while the cache is far from full if too many of the addresses you are using map to the same set — a conflict, not a capacity problem, and one that depends on associativity and on the exact addresses involved (Set-Associative Caches: The Compromise That Won).
Residency is also shared. On a machine with a shared last-level cache, another core's traffic evicts your lines; with simultaneous multithreading, a sibling thread competes for L1 and L2 as well (SMT: Two Contexts, One Core). And any context switch or migration can leave your data behind on the core you came from (Cache Warmth and the Real Cost of Migration). None of these appear in your source, and all of them change whether "recently used" means "still resident".
Finally, the replacement policy decides which line goes. It is worth being precise here: vendors do not document these policies, and real ones are approximations of recency rather than textbook LRU, sometimes with adaptive or scan-resistant behaviour. Reasoning that assumes strict LRU will occasionally be wrong, which is why Cache Replacement: LRU Is the Idea, Not the Implementation treats it as a model rather than a specification.
| Cause | What happened | What to change |
|---|---|---|
| Capacity | You touched more distinct lines than fit before coming back | Shrink the working set, or block the computation |
| Conflict | Too many hot addresses mapped to the same set | Change alignment, padding or the stride (Tag, Index and Offset: How an Address Finds Its Line) |
| Sharing | Another core or sibling thread evicted it from a shared level | Placement, affinity, or reducing the shared footprint |
| Migration | The thread moved to a different core with a cold cache | Pin the thread if the workload justifies it (Thread Affinity: Pinning and Its Price) |
| Policy | The replacement approximation chose your line | Not directly controllable; reduce pressure instead |
Designing for reuse rather than hoping for it
The practical technique is to organise computation so that whatever you bring in is used as much as possible before it leaves. Blocking is the general form: partition the problem so that each partition fits a level, do all the work touching that partition, then move on. It is the same idea whether the level is L1, L3 or a database buffer pool holding Pages: The Unit of Everything — the arithmetic changes, the principle does not.
A second technique is loop ordering: when several loops touch the same arrays, the order in which you run them changes reuse distance. A third is simply doing more work per visit — computing several outputs from one input while it is resident rather than making separate passes.
The measurement that guides all of this is a size sweep. Time per element as a function of working-set size shows plateaus where the set fits a level and steps where it does not. Those steps are your machine's real cache boundaries, and they are far more useful than any published capacity figure, because they include the competition your program is actually experiencing.
Key points
- What matters is reuse distance — the number of distinct lines touched between two uses — not elapsed time or total data size.
- Blocking works by bounding reuse distance so data is still resident when it is needed again; it changes order, not arithmetic.
- Residency is shared: other cores, sibling threads, migrations and conflicts can evict your data while the cache is not full.
- Real replacement policies are undocumented recency approximations, so LRU reasoning is a model rather than a guarantee.
- A size sweep reveals your machine's actual cache boundaries under real competition, which published capacities do not.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1First access → install: the line is fetched and placed, with recency state updated to mark it as freshly used.
- 2Intervening accesses → pressure: every distinct line touched afterwards competes for capacity in the same sets.
- 3Reuse distance exceeds capacity → eviction: the replacement approximation selects a victim, possibly the line you will want.
- 4Second access → hit or miss: whether it hits depends entirely on what happened in between, not on how much time passed.
- 5Miss → refetch: the line is fetched again, so the program pays twice for data it "already had".
- • Assuming loop fusion is always a win because it reduces the number of passes.
- • Reasoning with strict LRU and being surprised when a scan-resistant or adaptive policy behaves differently.
- • Blaming a slowdown on the code that changed, when the change was elsewhere and merely increased cache pressure.
- • Reading a published cache size and assuming your program gets all of it, on a machine where it is shared.
Consequences, controls and cost
- • Loop fusion can be slower than separate passes when it increases the combined footprint past a cache level.
- • Adding an unrelated data structure to a hot path degrades it by increasing pressure, with no change to its own code.
- • Performance is sensitive to what else is running on the machine, because shared levels are genuinely shared.
- • Benchmarks that repeat a small kernel report best-case residency the real workload will never enjoy.
- • Block or tile the computation so each partition fits a cache level and is fully used before moving on.
- • Reduce the working set — fewer fields, smaller types, dropping data you do not need in the hot path.
- • Reorder or split loops to shorten reuse distance for the arrays that matter most.
- • Do more work per visit, computing several results from one resident input rather than making repeated passes.
- • Reduce competition where you control it: fewer concurrent hot structures, and affinity if the workload justifies it.
- • Run a size sweep and plot time per element; the steps mark the effective capacity available to your program.
- • Compare fused and unfused loop variants directly — the answer is workload- and machine-specific.
- • Track miss rate rather than miss count while varying working-set size, so the metric is not confounded by total work.
- • Re-run a hot benchmark while a competing workload occupies other cores, to see how much of the last level you actually get.
- • Blocking adds a tuning parameter tied to cache size, so it is machine-specific and needs re-measuring on new targets.
- • Restructured loops are harder to read and can obscure the mathematical form of the computation.
- • Reducing the working set often means giving something up — precision, generality, or a convenient field kept "just in case".
Scope
§224 — what these claims are specific to.
- GENERALReuse-distance reasoning applies to any capacity-limited cache, including database buffer pools and OS page caches; only the capacities and units differ
- MICROARCH-SPECIFICReplacement behaviour, cache inclusivity and how much of a shared level a single thread can retain vary by vendor and generation and are largely undocumented