CPU Cache Locality
CPU cache locality arranges data access so the working set fits in cache and access is sequential, turning a 100x cache-miss penalty into a 1x cache-hit on the hot path.
Definition
CPU cache locality is the property that the data accessed on the hot path is already in the CPU cache — temporal locality reuses recently accessed data, spatial locality accesses nearby data that shares a cache line — so that the access is served from cache rather than main memory, avoiding the 100-cycle miss penalty.
Context and scope
Applied in numerical kernels, data structure layout, and any performance-sensitive loop where the memory access pattern dominates the cost.
Common misconceptions
- Cache locality is just array traversal order — traversal order is one axis; data layout (AoS vs SoA) and the working set size matter equally
- The hardware prefetcher handles locality — it handles sequential access; for strided and random access the prefetcher cannot predict and locality must be designed
Anti-patterns
- Iterating a column-major matrix in row order, missing every cache line and running 10x slower than the transposed traversal
- Laying out an array of large structs when only one field is hot, wasting cache on the cold fields and missing on every access
Related concepts
Authoritative source
What it is
CPU cache locality is the property that the data accessed on the hot path is already in the CPU cache — temporal locality reuses recently accessed data, spatial locality accesses nearby data that shares a cache line — so that the access is served from cache rather than main memory, avoiding the 100-cycle miss penalty. Applied in numerical kernels, data structure layout, and any performance-sensitive loop where the memory access pattern dominates the cost. Performance is a distribution, not a number: the tail determines user experience, and the mean hides the outliers that cause abandonment.
How it works
Measurement targets percentiles at the workload’s actual concurrency, not a single sequential run. The fast path is kept fast by deferring work that is not on it — lazy initialization, coalescing writes, avoiding allocation in hot loops. Profiling finds the bottleneck; micro-optimization without a profile optimizes the wrong thing. Constant factors matter, but algorithmic complexity dominates as scale grows.
When to optimize and pitfalls
Optimize when a measurement shows a concrete cost — latency budget burn, compute spend, user-visible jank. The pitfall is optimizing for the benchmark rather than the workload: a synthetic test that does not reproduce the production access pattern produces a local maximum that hurts globally. Another is trading memory for speed without accounting for the GC or eviction cost the extra allocation introduces.