Menu
I am a little confused on the meanings of spatial and temporal locality. I'm hoping by looking at it with an array example it will help me understand it better.
In an example like this: A[0][1], A[0][2], A[0][3].... etc
Does this demonstrate temporal locality? I see the same row is accessed many times but at different offsets... does this mean a different address is accessed?
Also, am I correct in saying that an example like this: A[1], A[2], A[3]... etc
Demonstrates spatial locality?
Hopefully some clarification on how temporal and spatial locality work in real code will help me better understand them.
664
Spatial locality (also termed data 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, such as traversing the elements in a one-dimensional array.
Arrays have better cache locality that can make a pretty big difference in performance.
The outer loop is an example of spacial locality. It sequentially increments the address the inner for-loop calls. The inside loop demonstrates temporal locality. The exact same memory address is accessed ten times in a row, and multiplied by j each time.
In Spatial Locality, nearby instructions to recently executed instruction are likely to be executed soon. In Temporal Locality, a recently executed instruction is likely to be executed again very soon. 2. It refers to the tendency of execution which involve a number of memory locations .
Spatial and temporal locality describe two different characteristics of how programs access data (or instructions). Wikipedia has a good article on locality of reference.
A sequence of references is said to have spatial locality if things that are referenced close in time are also close in space (nearby memory addresses, nearby sectors on a disk, etc.). A sequence is said to have temporal locality if accesses to the same thing are clustered in time.
If a program accesses every element in a large array and reads it once and then moves on to the next element and does not repeat an access to any given location until it has touched every other location then it is a clear case of spatial locality but not temporal locality. On the other hand, if a program spends time repeatedly accessing a random subset of the locations on the array before moving on to another random subset it is said to have temporal locality but not spatial locality. A well written program will have data structures that group together things that are accessed together, thus ensuring spatial locality. If you program is likely to access B soon after it accesses A then both A and B should be allocated near each other.
Your first example
A[0][1], A[0][2], A[0][3] shows spatial locality, things that are accessed close in time are close in space. It does not show temporal locality because you have not accessed the same thing more than once.
Your second example
A[1], A[2], A[3] also shows spatial locality, but not temporal locality.
Here's an example that shows temporal locality
A[1], A[2000], A[1], A[1], A[2000], A[30], A[30], A[2000], A[30], A[2000], A[30], A[4], A[4] If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
