Caches and Cache Behavior
Caches hold recently and nearby-used data close to the processor; understanding lines, misses, and locality is central to fast code.
What a cache does
A cache is a small, fast memory that keeps copies of data the processor is likely to reuse, sparing it slow trips to main memory. Data moves in fixed-size cache lines (commonly 64 bytes), so accessing one byte pulls in its neighbors. A request found in cache is a hit; one that is not is a miss and stalls the processor while the line is fetched.
The three kinds of miss
- Compulsory: the first-ever access to a line
- Capacity: the working set is larger than the cache
- Conflict: too many active lines map to the same set
Locality, revisited
Because whole lines are loaded, contiguous (unit-stride) access uses every byte fetched, while large-stride or random access wastes most of each line. Reusing data soon after loading it keeps it resident. Writing algorithms with strong temporal and spatial locality is the single most reliable way to speed up memory-bound code.
Cache blocking
A canonical technique is tiling: restructure loops so the working set of each tile fits in cache, maximizing reuse before data is evicted. Matrix multiply is the textbook case, where blocking turns a bandwidth-bound loop into a compute-bound one that approaches peak.
Pitfalls in parallel code
False sharing occurs when threads modify different variables that share a cache line; the line ping-pongs between cores, destroying performance even though the data is logically independent. Padding shared structures to line boundaries avoids it. Cache coherence keeps multiple cores' views consistent, at a communication cost.