Locality of reference: Difference between revisions

Revision as of 18:03, 27 March 2021

Revision as of 00:46, 18 April 2021

Line 16:

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.

== Relevance ==

There are several reasons for locality. These reasons are either goals to achieve or circumstances to accept, depending on the aspect. The reasons below are not [[Disjoint sets|disjoint]]; in fact, the list below goes from the most general case to special cases:

Line 22:

* '''Structure of the program''': Locality occurs often because of the way in which computer programs are created, for handling decidable problems. Generally, related data is stored in nearby locations in storage. One common pattern in computing involves the processing of several items, one at a time. This means that if a lot of processing is done, the single item will be accessed more than once, thus leading to temporal locality of reference. Furthermore, moving to the next item implies that the next item will be read, hence spatial locality of reference, since memory locations are typically read in batches.

* '''Linear data structures''': Locality often occurs because code contains loops that tend to reference arrays or other data structures by indices. Sequential locality, a special case of spatial locality, occurs when relevant data elements are arranged and accessed linearly. For example, the simple traversal of elements in a one-dimensional array, from the base address to the highest element would exploit the sequential locality of the array in memory.<ref>Aho, Lam, Sethi, and Ullman. "Compilers: Principles, Techniques & Tools" 2nd ed. Pearson Education, Inc. 2007</ref> Equidistant locality occurs when the linear traversal is over a longer area of adjacent [[data structure]]s with identical structure and size, accessing mutually corresponding elements of each structure rather than each entire structure. This is the case when a [[Matrix (mathematics)|matrix]] is represented as a sequential matrix of rows and the requirement is to access a single column of the matrix.

* '''Efficiency of memory hierarchy use''': Although [[random -access memory]] presents the programmer with the ability to read or write anywhere at any time, in practice [[latency (engineering)|latency]] and throughput are affected by the efficiency of the [[Cache (computing)|cache]], which is improved by increasing the locality of reference. Poor locality of reference results in cache [[Thrashing (computer science)|thrashing]] and [[cache pollution]] and to avoid it, data elements with poor locality can be bypassed from cache.<ref>"[https://www.academia.edu/24842555/A_Survey_of_Cache_Bypassing_Techniques A Survey Of Cache Bypassing Techniques]", JLPEA, vol. 6, no. 2, 2016</ref>

== General usage ==