Lably
Skip to content

Locality of reference

Tendency of a processor to access nearby memory locations in space or time

  • 15 min read
  • 4 chapters

Related on Lably

Through Computer science, Computer memory and Data structure

Lab · Class 10–11NLP PipelinesLab · Class 8–12Algorithms & Sorting

Locality is a type of predictable behavior that occurs in computer systems. Systems which exhibit strong locality of reference are good candidates for performance optimization through the use of techniques such as the caching, prefetching for memory and advanced branch predictors of a processor core.

Types of locality

There are several different types of locality of reference:

  • Temporal locality: If at one point a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future. There is temporal proximity between adjacent references to the same memory location. In this case it is common to make efforts to store a copy of the referenced data in faster memory storage, to reduce the latency of subsequent references. Temporal locality is a special case of spatial locality (see below), namely when the prospective location is identical to the present location.
  • Spatial locality: If a particular storage location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future. In this case it is common to attempt to guess the size and shape of the area around the current reference for which it is worthwhile to prepare faster access for subsequent reference.
  • Spatial locality in matrix traversal: In bidimensional structures such as matrices, spatial locality has a direct impact on computational performance. In programming languages such as C, matrices are stored in memory using row-major order, meaning that sequential access to contiguous elements improves cache utilization and reduces cache misses.

When the matrix size is small, performance differences between traversal methods may appear minimal because the entire dataset fits inside the processor cache. However, as matrix dimensions increase, the access pattern becomes a critical factor, since non-sequential traversals generate significantly more cache misses and RAM accesses, reducing overall computational efficiency.

  • Memory locality (or data locality): Spatial locality explicitly relating to memory.
  • Branch locality: If there are only a few possible alternatives for the prospective part of the path in the spatial-temporal coordinate space. This is the case when an instruction loop has a simple structure, or the possible outcome of a small system of conditional branching instructions is restricted to a small set of possibilities. Branch locality is typically not spatial locality since the few possibilities can be located far away from each other.
  • Equidistant locality: Halfway between spatial locality and branch locality. Consider a loop accessing locations in an equidistant pattern, i.e., the path in the spatial-temporal coordinate space is a dotted line. In this case, a simple linear function can predict which location will be accessed in the near future.

In order to benefit from temporal and spatial locality, which occur frequently, most of the information storage systems are hierarchical. Equidistant locality is usually supported by a processor's diverse nontrivial increment instructions. For branch locality, contemporary processors have sophisticated branch predictors, and on the basis of this prediction the memory manager of the processor tries to collect and preprocess the data of plausible alternatives.

Sign in to keep reading

3 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard