Principle of Locality

When a program executes on a computer, most of the memory references are not made uniformly to a small number of locations. Here the Locality of the reference does matter.

Locality of Reference, also known as the Principle of Locality, the phenomenon of the same value or related storage locations being frequently accessed. Locality occurs in time(temporal locality) and in space (spatial 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, eg, traversing the elements in a one-dimensional array.

To be very simple when exhibiting spatial locality, a program accesses consecutive memory locations and during temporal locality of reference a program repeatedly accesses the same memory location during a short time period. Both forms of locality occur in the following Pascal code segment:

  for i := 0 to 10 do
   A [i] := 0;

In the above Pascal code, the variable 'i' is referenced several times in for loop where 'i' is compared against 10 to see if the loop is complete and also incremented by one at the end of the loop. This shows temporal locality of reference in action since the CPU accesses 'i' at different points in a short time period.

This program also exhibits spatial locality of reference. The loop itself zeros out the elements of array A by writing a zero to the first location in A, then to the second location in A, and so on. Assume Pascal stores elements of A into consecutive memory locations then on each loop iteration it accesses adjacent memory locations.