Cache locality

Cache locality arises because many programs repeatedly access a limited region of memory. Temporal locality means that a location used recently is likely to be used again, as in a loop repeatedly reading a counter. Spatial locality means that locations near a recently used address are likely to be accessed soon, as in sequential traversal of an array. A cache transfers memory in fixed-size blocks called a cache line, so one access can bring neighboring bytes into fast storage.¹

On a hit, the processor obtains data from the cache; on a miss, it must fetch the line from a lower cache level or main memory. The resulting average access time depends on hit rates, miss penalties, and the latency of each level. Locality is therefore a property of an access sequence, not a guarantee attached to a particular data type or language.

Modern processors rely on several cache levels because small memories can be made faster and larger memories can provide greater capacity. L1 caches are usually closest to the execution cores, while L2 and sometimes shared L3 caches hold progressively more data at higher latency; main memory remains much slower.¹

Loop structure strongly affects locality. Traversing a row-major matrix by rows commonly gives better spatial locality than traversing it by columns, while blocking or tiling divides a large computation into pieces that fit in a chosen cache. Reusing data before it is displaced improves temporal locality. The working-set model describes the actively used portion of a program’s memory and helps explain why performance can decline sharply when that set exceeds cache capacity.²

Cache organization determines how locality translates into hits. In a direct-mapped cache, each memory block has one possible location, making lookup simple but allowing conflict misses when active addresses map to the same set. Set-associative caches permit several locations and reduce such conflicts, at the cost of more hardware, energy, and lookup complexity. Fully associative designs are flexible but generally expensive at larger capacities.

Misses are commonly classified as compulsory, capacity, or conflict misses. Hardware prefetching can anticipate regular spatial patterns, but an inaccurate prefetch consumes bandwidth and may evict useful lines. Measurements should therefore examine cache-miss rates together with bandwidth, branch behavior, concurrency, and the relevant cache level; a lower miss count does not automatically mean a faster program.¹

Locality can fail even when an algorithm has good asymptotic complexity. Pointer-heavy structures such as linked lists and trees may scatter logically related objects across memory, producing poor spatial locality; compact layouts, arrays, and structure-of-arrays designs can improve it. False sharing is another edge case: independent threads can repeatedly invalidate one another’s data when distinct variables occupy the same cache line.

Cache effects also extend beyond ordinary data arrays. Instruction caches benefit from compact hot code, translation-lookaside buffers preserve recent virtual-to-physical translations, and operating systems exploit related locality in virtual memory. On multisocket machines, NUMA placement adds a locality dimension in which a nearby memory bank can be faster than a remote one. These interactions make cache-aware optimization empirical: profiles and controlled benchmarks matter more than assumptions based solely on source-code appearance.³

Temporal locality

The tendency for a recently accessed memory location to be accessed again soon.

Spatial locality

The tendency for addresses near a recently accessed location to be accessed soon.

Cache line

The fixed-size block transferred between a cache and a lower memory level.

Cache miss

An access for which the requested data is absent from the examined cache level.

Working set

The set of memory locations actively used by a program during a defined interval.

False sharing

A multiprocessor performance problem in which threads modify different variables sharing one cache line.