3

我正在阅读关于Locality of Reference的 Wikipedia 文章，我不禁发现对Equidistant Locality给出的解释相当神秘。

我真的无法理解它，我想知道是否有人可以尝试用简单的英语解释它？

等距局部性：在空间局部性和分支局部性之间。考虑以等距模式访问位置的循环，即时空坐标空间中的路径是虚线。在这种情况下，一个简单的线性函数可以预测在不久的将来会访问哪个位置。

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

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

如果有人可以对Equidistant locality应该是什么意思做出一些澄清，那就太好了！

4

2 回答 2

3

我认为这最好用例子来解释。这些局部性原则通常用于优化事物。现代 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;
    }
}

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

您可以将此与例如：

#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循环中的访问，您会发现查找中存在时间局部性。但是，在“时间空间”中，当您从数组的一部分跳到另一部分时，查找不是等距的，访问不是连续的，因此空间和时间都没有等距的空间性。这几乎是不可能优化的。

于 2012-03-20T11:24:06.640 回答
1

以等距模式访问位置的循环

这很神秘，但如果我不得不猜测，这意味着循环的所有迭代都具有相同级别的空间/时间局部性：如果循环只是简单地遍历一个数组，那么在每次迭代中，我们访问位于的元素在前一个元素旁边（因此空间局部性与上次迭代中的相同），并且它与上次迭代中一样“最近”（因此时间局部性也没有变化）。

因此，每次迭代的等距位置都是相同的。

于 2012-03-20T09:57:17.110 回答