Locality of Reference: Short Notes for Memory Hierarchies and Cache Performance

In computer systems, the CPU accesses memory through a hierarchy (registers, caches, main memory). A key reason caches improve performance is locality of reference: once a program accesses a memory location, it is likely to access the same location (or nearby locations) in the near future. This idea is commonly decomposed into temporal locality and spatial locality.2

At a high level, locality explains why caching works: when the CPU requests data, the cache can also bring in (with the request) other data likely to be needed soon, reducing expensive trips to main memory.2

Key mechanisms enabled by locality include:

• cache block (cache line) transfers that exploit spatial locality.
• re-use within a cache’s effective lifetime, exploiting temporal locality.2

Learning target: You should be able to define locality of reference, distinguish temporal vs. spatial locality, and explain how each improves cache hit rates and performance.

Footnotes

1. Locality of reference - Defines temporal vs spatial locality and explains how it applies to cache performance. ↩ ↩² ↩³ ↩⁴

2. Cache (computing) - Background on cache behavior, cache lines, hits/misses, and why program locality matters. ↩ ↩² ↩³

1) Temporal and Spatial Locality (Core Ideas)

Temporal locality occurs when data or instructions are accessed again within a short time window. Typical sources:

• Looping over the same variable(s).
• Repeated function calls that re-use the same instructions.
• Small working sets where recently used data remains in cache.2

Spatial locality occurs when, after accessing one memory address, the program will likely access nearby addresses. Typical sources:

• Sequential array traversal (e.g., scanning an array from index 0 upward).
• Accessing fields in a struct that are stored near each other in memory.
• Iterating through contiguous memory blocks.2

A concise memory model:

• Spatial locality improves the effectiveness of cache line fetching because a miss brings in a block, not just one word.
• Temporal locality improves the chance that once fetched, the same block (or same data within it) will be reused before it gets evicted.2

Footnotes

1. Locality of reference - Defines temporal vs spatial locality and explains how it applies to cache performance. ↩ ↩² ↩³ ↩⁴

2. Cache (computing) - Background on cache behavior, cache lines, hits/misses, and why program locality matters. ↩ ↩² ↩³

2) Locality and Cache Performance (Why It Matters)

Caches reduce average memory access time by turning many expensive memory accesses into fast cache hits. Locality directly influences:

• Hit rate: more re-use of cached blocks (temporal locality) and better use of fetched cache lines (spatial locality).2
• Miss penalty frequency: fewer cache misses if data stays in the cache long enough to be re-used.
• Block utilization: when programs touch multiple elements within the same cache block, spatial locality increases “usefulness” of each fetched block.

This is why “cache-friendly” programming patterns often use:

• Contiguous memory access (arrays, sequential buffers).
• Blocking/tiling techniques in matrix computations (to keep a sub-problem’s data in cache longer, improving temporal locality).

Footnotes

1. Locality of reference - Defines temporal vs spatial locality and explains how it applies to cache performance. ↩ ↩²

2. Cache (computing) - Background on cache behavior, cache lines, hits/misses, and why program locality matters. ↩ ↩²

3) Working Set View (Intuition for Temporal Locality)

A helpful conceptual framework is that programs have a working set—the subset of memory that is referenced “recently enough” to be relevant. Temporal locality implies that the working set doesn’t change too rapidly; if it fits in the cache, many accesses hit.2

When the working set is larger than what the cache can hold, temporal locality weakens because data used earlier gets evicted before it is re-accessed, increasing miss rates.2

Footnotes

1. Cache (computing) - Background on cache behavior, cache lines, hits/misses, and why program locality matters. ↩ ↩²

2. Working set - Working set concept used to reason about memory reference patterns over time and reuse/eviction effects. ↩ ↩²

4) Mini-Comparisons (What to Write vs. What Not to Write)

supports the conceptual link between working-set behavior and locality effects.

Footnotes

1. Cache (computing) - Background on cache behavior, cache lines, hits/misses, and why program locality matters. ↩