Locality of reference: Difference between revisions

Revision as of 03:53, 18 December 2022

Latest revision as of 02:47, 21 July 2025

(6 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Tendency of a processor to access nearby memory locations in space or time}}

{{more citations needed|date=July 2008}}

In [[computer science]], '''locality of reference''', also known as the '''principle of locality''',<ref>Not to be confused with the [[principle of locality]] o=s*v=411##sts in physics.</ref> is the tendency of a processor to access the same set of memory locations repetitively over a short period of time.<ref>{{Cite book|title=Computer organization and architecture : designing for performance|last=William.|first=Stallings|date=2010|publisher=Prentice Hall|isbn=9780136073734|edition= 8th|___location=Upper Saddle River, NJ|oclc=268788976}}</ref> There are two basic types of reference locality {{sndNdash}} temporal and spatial locality. Temporal locality refers to the reuse of specific data and/or resources within a relatively small time duration. Spatial locality (also termed ''data locality'')<ref name="NistBig1">"NIST Big Data Interoperability Framework: Volume 1", [https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2</ref>) 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, such as traversing the elements in a one-dimensional [[Array data structure|array]].

Locality is a type of [[predictability|predictable]] behavior that occurs in computer systems. Systems thatwhich exhibit strong ''locality of reference'' are greatgood candidates for performance optimization through the use of techniques such as the [[CPU cache|caching]], [[prefetch instruction|prefetching]] for memory and advanced [[branch predictor]]s at the [[Pipeline (computing)|pipelining]] stage of a processor core.

== Types of locality ==

Line 125:

* [[Working set]]

* [[Heuristic]]

* [[Locality-sensitive hashing]]

== References ==

Line 131 ⟶ 132:

== Bibliography ==

* [[Peter J. Denning]], [http://denninginstitute.com/pjd/PUBS/CACMcols/cacmJul05.pdf "The Locality Principle"], ''Communications of the ACM'', Volume 48, Issue 7, (2005), Pages 19–24

* Peter J. Denning, Stuart C. Schwartz, [http://denninginstitute.com/pjd/PUBS/WSProp_1972.pdf "Properties of the Working-Set Model"], ''Communications of the ACM'', Volume 15, Issue 3 (March 1972), Pages 191-198191–198

{{DEFAULTSORT:Locality Of Reference}}