Concepts and theorems · Intermediate

Locality of reference: closeness in time and space

Distinguish reuse of the same data from access to nearby data, and predict when a cache can help.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Temporal and spatial locality
  2. Reasoning with cache lines
  3. A worked traversal example
  4. Limits of the explanation
  5. Trace reuse distance by hand
  6. Ask Logeia about this articleCheck your understanding

Temporal and spatial locality

Locality describes concentration in an access pattern rather than a guarantee provided by an instruction. Temporal locality means that a location is likely to be reused relatively soon. Spatial locality means that addresses near a recently accessed location are likely to be accessed. A repeatedly read loop coefficient illustrates temporal locality, while a sequential array traversal illustrates spatial locality. These properties explain why a comparatively small fast store can serve many accesses even when the complete dataset is much larger than that store.

Reasoning with cache lines

Consider an illustrative machine with 64-byte lines and four-byte integers. Sixteen suitably aligned consecutive integers fit in one line. Fetching the line for the first integer can therefore supply the following fifteen reads without another line fill. The relevant unit is the transferred line, not the number of variable names in the source code. Alignment can make an interval span two lines, and a different processor can use different sizes. Hardware prefetching may also fetch the next line before an explicit demand arrives.

A worked traversal example

For a row-major matrix, advancing across a row visits consecutive elements. Holding the column fixed and advancing between rows instead introduces a stride determined by row width. Both traversals still visit the same number of elements, so their asymptotic operation counts can agree while their memory behavior differs. A meaningful experiment keeps layout and element size fixed, varies the working-set size deliberately, and examines cache-miss measurements alongside elapsed time. Column-major storage reverses which loop ordering is naturally contiguous; the language or library layout must be checked.

Limits of the explanation

Locality is useful evidence, not a complete performance model. A working set can exceed cache capacity, unrelated addresses can compete for limited placement options, and other cores can force coherence traffic for a shared line. Memory-level parallelism may hide some misses, while bandwidth saturation can dominate a streaming workload. Consequently, a lower-level access explanation should be tested rather than converted directly into a promised speedup. Preserve program semantics when changing loop order, and separate the cost of arithmetic, synchronization, and memory traffic when interpreting results.

Trace reuse distance by hand

Assume a fully associative cache holding two lines, initially empty, with least-recently-used replacement. For A, B, A, C, A, the first A and B miss, the next A hits, C replaces B, and the final A hits. The trace has three misses and two hits. For A, B, C, A, B, all five references miss because each requested line has been displaced. This hand calculation isolates reuse distance under explicit placement and replacement assumptions. It is not a prediction of measured timing on a processor with prefetching, different associativity or several cache levels. It explains why counting references without preserving their order loses useful information.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 8

Prepare for AI systems · STEP 5

Choose a learning path