Define Locality of Reference

In computer systems, locality of reference (also called the principle of locality), is the observed behavior that a processor is more likely to access certain memory locations again soon or access nearby locations after an access. This matters because caches and other performance optimizations rely on predicting which data/instructions will be needed next. A standard split is into temporal locality and spatial locality.2

Core definition (what it means)

Locality of reference is the tendency of a program (during execution) to reference the same memory locations repeatedly over a short period, rather than accessing memory uniformly at random. Informally:

• If you access address $x$ at time $t$, then you’re likely to access $x$ again at a later time soon (temporal reuse).
• If you access address $x$ at time $t$, you’re likely to access addresses near $x$ soon (spatial reuse), since neighboring elements are often fetched together into cache line/block structures.

Because caches move data/instructions from slower main memory into faster storage in blocks, spatial locality implies that once one element is fetched, nearby elements are also likely to be available without additional long-latency memory accesses.

Types you should be able to state precisely

1. Temporal locality
   Reuse of the same data/instructions within a relatively small time window (e.g., loop variables repeatedly used across iterations).2

2. Spatial locality
   Use of data elements in relatively close memory locations (e.g., array traversal).2

3. Sequential locality
   A special case of spatial locality: linear/stride-1 access patterns like walking an array from index 0 to $n-1$.

4. Locality principle
   Designers exploit locality to make the memory hierarchy efficient: upper levels of the hierarchy are smaller/faster, so good locality keeps relevant blocks there longer and avoids evicting useful data too soon.

Why locality is central to memory performance

Caches work because locality makes it likely that data requested now will be requested again soon (temporal) and that nearby data will already be present after a fill (spatial). In the memory hierarchy, upper levels (caches, registers) are faster but smaller; good locality helps ensure the needed working data stays in those small fast levels rather than being constantly evicted.

Key takeaway: locality of reference is not just a definition—it is an empirical property that allows systems to predict and reduce average memory access time.2