Locality of reference

related topics
{system, computer, user}
{math, number, function}
{area, part, region}
{rate, high, increase}
{math, energy, light}

In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, e.g., traversing the elements in a one-dimensional array.

Locality is merely one type of predictable behavior that occurs in computer systems. Systems which exhibit strong locality of reference phenomenon, are good candidates for performance optimization through the use of techniques, like the cache and prefetching[disambiguation needed] technology concerning the memory, or like the advanced branch predictor at the pipelining of processors.

Contents

Locality of reference

The locality of reference, also known as the locality principle, is the phenomenon, that the collection of the data locations referenced in a short period of time in a running computer, often consists of relatively well predictable clusters. Important special cases of locality are temporal, spatial, equidistant and branch locality.

  • Temporal locality: if at one point in time a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future. There is a temporal proximity between the 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 special memory storage, which can be accessed faster. Temporal locality is a very special case of the spatial locality, namely when the prospective location is identical to the present location.
  • Spatial locality: if a particular memory 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.
  • Equidistant locality: it is halfway between the spatial locality and the 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.

Full article ▸

related documents
Microsoft Access
Wikipedia:Free On-line Dictionary of Computing/L - N
Ext2
Parrot virtual machine
GNU Privacy Guard
ReiserFS
Wikipedia:Free On-line Dictionary of Computing/T - W
Rsync
REBOL
Byte
L4 microkernel family
Subversion (software)
Portable Executable
MMIX
DEFLATE
Shannon–Hartley theorem
Shareaza
BBC BASIC
Chmod
AltiVec
Talker
Amdahl's law
GNU Hurd
JPEG 2000
Zope
List of ad-hoc routing protocols
Qt (toolkit)
Intel i860
IPsec
Fourth-generation programming language