Cache Lab
Set the geometry, choose an access pattern, and watch the miss classification change. The interesting configurations are the ones where the data fits and it is still slow.
A set-associative cache model — not a model of any particular CPU. Real caches have multiple levels, undocumented replacement policies, hardware prefetchers and write-allocate behaviour this ignores. What it reproduces faithfully is the shape: lines as the unit of transfer, conflicts that depend on associativity, and the cliff when a working set stops fitting.
Almost all hits. Either the working set is resident or the pattern has enough spatial locality that each line pays for many accesses.
Address arithmetic
Where the index bits sit is why a power-of-two stride can be pathological.
The index bits sit in the middle of the address, which is why addresses exactly 1024 bytes apart all land in the same set. That number — line size times set count — is the stride that thrashes a cache, and it is why a power-of-two array dimension can be pathologically slow.
The patterns, and what each teaches
Walk an array from start to finish, one element at a time.
The best case. One miss per cache line pays for every element in it, and the prefetcher sees the pattern coming, so the miss rate falls to one over elements-per-line.
Spatial Locality →Touch every Nth element. Raise the stride and watch what happens at the line boundary.
Once the stride exceeds a line, every access pays a full miss and most of every fetched line is wasted. Raise it further, to a multiple of the set count, and a direct-mapped cache thrashes on a working set that would otherwise fit.
Cache Thrashing: Load, Evict, Reload, Repeat →Touch elements in a shuffled order within a region.
Spatial locality is gone and the prefetcher is useless, but the accesses are still independent, so misses can overlap. Shrink the region until it fits and the hit rate recovers — that is the working set effect.
Working Set: Why Performance Falls Off a Cliff →Follow a randomly permuted cycle, where each element holds the index of the next.
The worst case, and the reason a linked list loses to an array at the same complexity: each address depends on the previous load, so the misses cannot overlap and the prefetcher has nothing to predict.
Pointer Chasing: The Address You Do Not Have Yet →Traverse a row-major matrix down its columns.
The classic loop-order mistake. Every access lands on a different line, so a matrix that would stream perfectly by rows misses on essentially every element.
Temporal Locality →Traverse the same matrix in square tiles sized to stay resident.
The fix. Exactly the same arithmetic and the same number of elements, but each tile is reused while it is still in cache — which is why tiling wins without doing less work.
Matrix Tiling: Same Arithmetic, Ten Times Faster →