Locality of reference: temporal and spatial locality in computing

Key types

There are two widely recognized forms of locality:

• Temporal locality: if a location is referenced, it is likely to be referenced again soon (e.g., loop counters, frequently used variables).
• Spatial locality: if a given memory location is referenced, nearby addresses are likely to be accessed in the near future (e.g., sequential array traversal).

History and theory

The idea of locality has guided computer architecture and operating systems for decades. Formal work on the working set model and on exploiting locality for virtual memory management was developed in the 1960s; these concepts helped explain why caches and paging policies could dramatically affect performance. For foundational material and formal models, consult sources such as further background.

Practical importance and examples

Locality influences many real-world behaviors: CPU caches keep recently used lines to exploit temporal locality, prefetchers read adjacent blocks to exploit spatial locality, and virtual memory managers keep a process's working set in RAM. Simple examples: iterating a large array sequentially uses spatial locality, while repeatedly accessing a variable inside a tight loop uses temporal locality.

Optimizations and techniques

Programmers and compilers improve locality by restructuring data and control flow. Common techniques include blocking (tiling) for matrices, contiguous data layouts, loop interchange to access arrays row-major or column-major in cache-friendly order, and software prefetching. These approaches aim to increase cache hits and reduce costly memory stalls.

Limitations and considerations

Not all workloads exhibit strong locality; irregular access patterns, large random data sets, and pointer-heavy structures can limit cache effectiveness. Understanding workload characteristics and the memory hierarchy is essential to choose suitable optimizations and to interpret performance measurements.