computer-science - Locality of Reference - 等距地点的英文解释

Question

我正在阅读有关 Locality of Reference 的维基百科文章，我不禁发现对等距局部性的解释相当含糊。

我不太明白它的意思，我想知道是否有人可以尝试用通俗易懂的英语解释一下？

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.

“以等距模式访问位置的循环”是什么意思？这些位置彼此之间的距离是否相等？

关于“空间-时间坐标空间是一条虚线。”的所有这些垃圾是什么？这对我来说毫无意义。

如果有人能解释一下等距局部 的含义，那就太好了!

Answer 1

我认为最好用示例来解释这一点。这些局部性原则通常用于优化事物。现代 CPU 中的一个可能组件是内存预取器，它会尝试猜测您将使用哪个内存，并在您需要时将其放入缓存中。这在很大程度上依赖于局部性原则。

以数组为例，如果你做这样的事情(c++ 例子):

#include <iostream>
#include <vector>

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

在向量(或其他语言中的数组)中，元素以固定的步幅打包在一个连续的 block 中。所以如果 test 的第一个元素在地址 X，那么第二个元素将在 X+Y，第三个在 X+2Y, ...。因此，矢量本身是空间局部性的一个非常基本的例子，而且更好的是，局部性是非常可预测的。其次，元素在一个紧密的循环中被访问，所以我们也有很好的时间空间性。因为元素也是顺序访问的，所以我们在“时空”中有一个等距的空间性。这意味着一旦 CPU 在查找过程中识别出 X+Y、X+2Y、X+3Y 模式，它就可以开始在缓存中提取 future 的元素。

您可以将其与例如:

#include <iostream>
#include <list>

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

在链表中，元素相互引用，单个元素可以位于内存中的任何位置，因此您失去了空间局部性。但是，您可以循环访问元素，因此您仍然拥有时间空间性。像这样的东西更难检测和优化预取(但并非不可能)。

最后，作为组合时空空间性为何重要的一个指标，考虑这个(有点做作的)例子:

#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;
    }
}

如果您纯粹查看 test 容器，它又具有良好的空间局部性(如第一个示例中那样跨步)。如果您查看循环中的 test 访问，您会发现查找中存在时间局部性。但是，在“时空”中，当您从数组的一部分跳到另一部分时，查找不是等距的，访问不是顺序的，因此在空间和时间上都没有等距空间性。这几乎是不可能优化的。