现实生活代码中时空局部性的混淆

Question

我读了这个question，我想问更多关于他展示的代码，比如

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

问题是，

1. I理解时态局部性，我认为对i和j的引用应该是时态局部性。我说的对吗？
2. I也理解空间局部性，因为我所联系的问题回答了对ai的引用应该是空间局部性。我说得对吗?那个人说，
3. ，

“当访问ai 10次时，内环将调用相同的内存地址，所以我想这是一个时间局部性的例子。但是上面的循环中也有空间局部性吗？”。

我不同意他的猜测。因为ai生成的引用应该是空间局部性(它们将引用块中的下一个元素)。我说的对吗？

Answer 1

写这个答案，因为我没有得到它，甚至在阅读了这个问题的其他答案，一些其他问题和维基百科(这更令人困惑)。

我认为我们花费了大量的时间和精力来理解这个术语，在这种情况下，这个术语有点混乱/复杂。当我不注意“空间”和“时间”这两个词时，我发现更容易理解。

让我们从基础开始。

让我们试着理解缓存是什么--一个比主内存更快访问的地方。这很酷。但是这个地方是有限和昂贵的，所以我们应该明智地使用它。但是，您(或OS)如何决定在缓存中放什么，不放什么呢？应该有办法知道我们将来需要什么。啊，未来的预言！(少数派报告！敲响警钟吗？)

应该有一些方法来确定程序将来需要什么。使用常识和代码，我们可以说代码的某些部分在本质上是重复的--示例循环！如果循环中有一个变量i，你知道它将在不久的将来一次又一次地被访问。这就是时间局部性背后的原则。我可以进入缓存，因为它是临时本地的。

在另一个区域，如果代码使用的是任何线性数据结构(例如:数组)，并且在索引增加的循环中也使用这种结构，那么很容易看到，尽管当前的需求仅为该数据结构的第三个位置(例如)，但很快也需要下一个位置，因为该线性数据结构的索引增加了1。所以，如果我们也能在接下来的几个地点输入数据，那就太好了。这就是空间局部性背后的原则。接下来的几个位置可以进入缓存，因为它们是空间本地的。

局部性的基本概念是识别引入缓存的数据和指令，从而减少缓存丢失，有效地利用这个特殊的位置。

Answer 2

外环是空间局部性的一个例子。它依次递增内部for-循环调用的地址。

内部循环演示时间局部性。完全相同的内存地址在一行中被访问十次，每次乘以j。

对于前两个问题，i和j(循环计数器)都是时间局部性的很好的例子。

局部性是缓存为最小化对内存的调用而应用的一种度量。如果指令需要知道未在缓存中的内存地址的值，则它将访问该内存并将所有周围的内存位置存储在高速缓存中。

Answer 3

让我们首先定义时间和空间的局部性。

时态局部性-时态局部性是指正在获取的当前数据或指令可能很快就需要了。因此，我们应该将数据或指令存储在缓存内存中，以避免再次在主内存中搜索相同的数据，从而节省时间。

空间局部性-空间局部性是指正在获取的当前内存位置附近的指令或数据，在不久的将来可能需要。

sum = 0;
for (i = 0; i < arr.length; i++)
  sum += arr[i];
return sum;

现在看看这个例子，变量和被一次又一次地使用，它显示了的时态局部性，然后数组arr的值是按顺序访问的，即arr，arr1，arr2，.以此类推，显示为Contiguous(adjacent)存储块的空间局部性作为数组，因此正在获取接近当前内存位置的数据。

现在来看看这个例子

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

在这里，我们看到了时态局部性，因为在第二个循环中，ai被一次又一次地使用，然后变量j被按顺序访问，这显示了空间局部性。