Locality of Reference: Meaning, Types, and Why It Matters in Computing
Locality of reference is the principle that, when a program accesses memory, it tends to reuse recently accessed data and to access data near previously accessed addresses. This behavior allows hardware (especially caches and TLBs) to predict what will be needed next, significantly improving performance by reducing expensive memory accesses.2
At a high level, locality is usually split into:
- Temporal locality
- Spatial locality
- Working set (often used in operating systems)
These ideas are central to how caches are designed and why memory hierarchies work.3
Footnotes
-
Computer Organization: Locality of Reference (Temporal and Spatial) - Explains temporal/spatial locality and how it supports caching. ↩ ↩2
-
Locality of Reference - Wikipedia - Overview of temporal and spatial locality with memory hierarchy relevance. ↩ ↩2
-
Working set model - Wikipedia - Defines working set and relates it to paging/thrashing concepts. ↩
Locality of Reference (Temporal vs Spatial) in Cache Performance
Key definitions and “locality of reference” in context
In memory hierarchies, the CPU typically accesses:
- Registers (fastest)
- Caches (small and fast)
- Main memory / DRAM (large and slow)
Locality of reference explains why the CPU often finds what it needs in caches: if accesses are “clustered” in time or space, then recently/frequently used cache lines are likely to be reused before they are evicted.2
Important related concepts
- Cache
- Cache miss
- Cache line
- Prefetching
Locality is the underlying reason caches use blocks (cache lines) and why prefetchers can be effective: contiguous code/data often maps naturally to the same cache line(s) being accessed soon.2
Footnotes
-
Computer Organization: Locality of Reference (Temporal and Spatial) - Explains temporal/spatial locality and how it supports caching. ↩ ↩2
-
Locality of Reference - Wikipedia - Overview of temporal and spatial locality with memory hierarchy relevance. ↩
-
Cache - Wikipedia - Describes cache lines/blocks and performance impact related to locality. ↩
How locality turns into fewer cache misses
- 1Step 1
When the CPU reads/writes an address, the cache checks whether the data is already present (a cache hit).
- 2Step 2
Caches fetch an entire cache line. If your program then accesses nearby addresses, those will often be hits.
- 3Step 3
If you access the same location again soon (loop variables, reused structures), the line is still likely to remain in cache, so the second access is a hit.
- 4Step 4
Fewer misses means fewer DRAM fetches, reducing average memory access time and improving throughput.
- 5Step 5
If access patterns have poor locality (e.g., random accesses over a huge working set), the cache can’t reuse data effectively, increasing miss rates.
Types of locality with concrete examples
1) Temporal locality
Temporal locality means the program reuses the same memory locations over a short time span.2
Common sources:
- Looping over data structures
- Repeated accesses to the same scalar variables
- Re-reading instructions/data within a short period
Example (conceptual): A loop updates sum, repeatedly reading and writing the same sum variable—so sum is accessed, then accessed again soon.2
2) Spatial locality
Spatial locality means if the program accesses a memory address, it is likely to access nearby addresses soon.3
Common sources:
- Sequential array traversal:
A[i],A[i+1],A[i+2], ... - Iterating through structures stored contiguously
- Code that performs linear scans
Because caches move data in contiguous blocks (cache lines), nearby accesses tend to land in the same loaded block.
Footnotes
-
Computer Organization: Locality of Reference (Temporal and Spatial) - Explains temporal/spatial locality and how it supports caching. ↩ ↩2 ↩3
-
Locality of Reference - Wikipedia - Overview of temporal and spatial locality with memory hierarchy relevance. ↩ ↩2 ↩3
-
Cache - Wikipedia - Describes cache lines/blocks and performance impact related to locality. ↩ ↩2
Pro Tip: Spot locality from code shape
Loops that reuse variables often show temporal locality. Loops that traverse arrays/contiguous buffers often show spatial locality.
Beware: locality can vanish
Large pointer-chasing through random locations, strided accesses with huge gaps, or frequent reinitialization of data sets larger than cache can reduce locality—raising cache miss rates.
Intuition: Locality improves effective memory access
This is conceptual: better locality typically increases cache hit rate and reduces average latency.
Where locality matters in the memory hierarchy
Cache line loaded
Access 1The first reference brings a cache line; subsequent nearby references may hit due to spatial locality."
Reuse and hits
Soon afterRepeated use of the same line/locations leads to hits due to temporal locality."
Misses increase
If evictedIf the working set exceeds cache capacity, lines may be replaced before reuse."
Working set drives paging behavior
System level (OS)Operating systems model the active set of pages; too-large working sets can cause thrashing."
Common questions about locality of reference
Relationship to performance metrics (high-level)
Locality primarily affects performance by changing how often the CPU must fetch from slower levels. When locality is strong, many accesses hit in cache; when locality is weak, cache misses rise, increasing average memory access time.2
A standard mental model is:
- Strong locality ⇒ higher hit rate ⇒ lower average latency
- Weak locality ⇒ lower hit rate ⇒ higher average latency
This is why researchers and practitioners emphasize locality when analyzing algorithms and designing systems.2
Footnotes
-
Computer Organization: Locality of Reference (Temporal and Spatial) - Explains temporal/spatial locality and how it supports caching. ↩
-
Locality of Reference - Wikipedia - Overview of temporal and spatial locality with memory hierarchy relevance. ↩ ↩2
-
Cache - Wikipedia - Describes cache lines/blocks and performance impact related to locality. ↩
Locality of Reference Quick Deck
Knowledge Check
Which option best describes temporal locality?