The principle of Locality states that well-written programs should reference data items that are near other recently referenced data items or that were recently referenced themselves. Here one differentiates between two forms:

  1. Spatial Locality: Here the program is likely to reference a nearby memory location in the future.
  2. Temporal Locality: A memory location that is referenced once is likely to be referenced again multiple times in the future.

In general one can say, that programs with good Locality run faster than programs with poor Locality. This is because of the Memory hierarchy in modern Computers, where it is ensured, that data that has been recently used or is close together is higher in their hierarchy.

Examples

  • Cache memories hold the most recently referenced instructions and data items for the CPU.
  • The Operating System uses the RAM as a Cache for the most recently used Virtual Address Space.
  • The Operating System uses the RAM as a Cache for the most recently used Disk blocks.
  • Web browser cache recently viewed documents on a local disk.
  • Web servers Cache recently requested documents.

References

  • Computer Systems A Programmer's Perspective