Editing Locality of reference (section)

== 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.
** '''Memory locality''' (or ''data locality''<ref name="NistBig1"/>):  Spatial locality explicitly relating to [[computer memory|memory]].
* '''[[Branch (computer science)|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 [[Computer data storage#Hierarchy of storage|hierarchical]]. Equidistant locality is usually supported by a processor's diverse nontrivial increment instructions. For branch locality, the 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.