Temporal vs Spatial Locality with arrays

65,741

Solution 1

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]

Solution 2

In simple words,

Temporal locality: The concept that a resource that is referenced at one point in time will be referenced again sometime in the near future.

Spatial locality: The concept that likelihood of referencing a resource is higher if a resource near it was just referenced.

Source(s): Wikipedia

Solution 3

Here is an example of code with locality:

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;
  • There exists temporal locality because sum is accessed frequently in the loop. Temporal locality is exploited by keeping recently used instruction and data values in cache memory and by exploiting a cache hierarchy. Or even in a register, not in memory at all.

  • There exists spatial locality because we have an array 'a' and we access each element of the array in order. Spatial locality is generally exploited by using larger cache blocks and by incorporating prefetching mechanisms (fetching items of anticipated use) into the cache control logic.

Share:
65,741
Eric Smith
Author by

Eric Smith

Updated on August 20, 2020

Comments

  • Eric Smith
    Eric Smith over 3 years

    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.

  • Peter Cordes
    Peter Cordes over 5 years
    That's sort of true, and an interesting observation, for a cache based on lines / blocks of data, like a CPU cache. (Rather than a list of recent search queries or something, where spatial locality isn't even well defined. But this is a computer-architecture question where caches are pretty much always of some kind of address space, whether it's a TLB, decoded-uop cache, or a data cache). But often spatial locality means the nearby accesses are very nearly simultaneous, and basically part of one larger access. Temporal typically means soon but not necessarily right away.
  • Peter Cordes
    Peter Cordes over 5 years
    i.e. you need both spatial and temporal locality to get cache hits, otherwise the line containing the item will have been evicted. But yeah, the case of accessing the same item again is kind of a special case of spatial locality. I'd like to upvote this answer if it said that, please consider an edit :)
  • Peter Cordes
    Peter Cordes over 5 years
    I think you reversed the 2nd sentence of each bullet point. And BTW, compilers will keep sum in a register, not memory at all, to get the maximum benefit of repeated access.
  • superrcoop
    superrcoop over 5 years
    yeah your right @peterCordes , I will make that adjustment
  • Peter Cordes
    Peter Cordes over 4 years
    The terms are based on the standard English meaning of the words. Spatial = in space / position. Temporal = relation in time. Locality = nearness. (Links are to google dictionary). "Temporary" has the same root word as "temporal", Latin "tempus" = time. But other than that, temporary and temporal are different concepts. If that connection / mnemonic trick helps you remember what "temporal" means, then great.
  • conditionalMethod
    conditionalMethod about 4 years
    For future readers, spacial locality occurs here only under the assumption that a is stored in row-major order: a[0][0], a[0][1],...,a[0][m],a[1][0], a[1][1],... Some languages don't specify that their two-dimensional arrays are stored in this way. Fortran, for example, doesn't. In that case to get space locality one needs to exchange the loops.
  • Sagar Shah
    Sagar Shah about 3 years
    Why the downvotes? It's correct and also given on en.wikipedia.org/wiki/….