Locality of Reference - English explanation for equidistant locality

Question

I am reading the Wikipedia article on Locality of Reference, and I cannot help but find the explanation given for Equidistant Locality to be rather cryptic.

I cannot really make much sense of it, and I wondered if anyone could make an attempt to explain it in plain English?

Equidistant locality: it is halfway between the spatial locality and the branch locality. Consider a loop accessing locations in an equidistant pattern, i.e. the path in the spatial-temporal coordinate space is a dotted line. In this case, a simple linear function can predict which location will be accessed in the near future.

What does it mean with "a loop accessing locations in an equidistant pattern"? Are the locations just an equal distance from each other?

What's all this garbage about "the spatial-temporal coordinate space is a dotted line."? That makes no sense to me.

If anyone could give some clarification on what Equidistant locality is supposed mean, that would be great!

Answer 1

I think this is best explained with examples. These principles of locality are often used to optimize things. A possible component in a modern CPU is a memory prefetcher, which will try to guess which memory you'll use and get it in cache by the time you need it. This relies heavily on the locality principle.

Take an array for example, if you do something like this (c++ example):

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test = { 1, 2, 3, 4, 5};
    for(int& i: test)
    {
        std::cout << i << std::endl;
    }
}

In a vector (or array in other languages) elements are packed in a contiguous block with fixed strides. So if the first element of test is at address X, then the second element will be at X+Y, the third at X+2Y, .... A vector itself is therefore a very basic example of spatial locality, and even better the locality is very predictable. Next to that the elements are accessed in a tight loop, so we have good temporal spatiality also. Because the elements are also sequentially accessed, we have an equidistant spatiality in 'spacetime'. This means that as soon the CPU recognizes the X+Y, X+2Y, X+3Y pattern int he lookup it can start pulling in future elements in the cache.

You can contrast this with for example:

#include <iostream>
#include <list>

int main()
{
    std::list<int> test = { 1, 2, 3, 4, 5};
    for(int& i: test)
    {
        std::cout << i << std::endl;
    }
}

In a linked list, elements refer to eachother, and individual elements can be at any place in the memory so you lose your spatial locality. You access the elements in a loop however, so you still have your temporal spatiality. Something like this is much harder to detect and optimize for prefetching (not impossible however).

Finally, as an indicator why combined spacetime spatiality is important, consider this (little bit contrived) example:

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iterator>

int main()
{
    std::vector<int> test = { 1, 2, 3, 4, 5 };
    std::vector<unsigned int> indices = { 0, 1, 2, 3, 4 };
    std::random_device rd;
    std::shuffle(std::begin(indices), std::end(indices), std::mt19937 { rd() });
    for (unsigned int& i : indices)
    {
        std::cout << test[i] << std::endl;
    }
}

If you purely look at the test container it had again good spatial locality (strided as in the first example). If you look at the test access in the loop, you see there is a temporal locality in lookups. However, in "timespace" the lookups are not equidistant as you jump from one part of the array to the other, the access is not sequential, so there is no equidistant spatiality in both space and time. This is almost impossible to optimize.

Answer 2

a loop accessing locations in an equidistant pattern

That is pretty cryptic, but if I had to guess, it means that all iterations of the loop have the same level of spatial/temporal locality: if the loop is simply iterating through an array, then in each iteration, we access the element located next to the previous element(so the spatial locality is the same as in the last iteration), and it's just as "recent" as it was in the last iteration (so temporal locality is unchanged as well).

So the equidistant locality is the same for every iteration.