computer-science - 在现实生活代码中混淆时间和空间局部性

Question

我正在读这个 question ，我想问更多关于他展示的代码，即

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

问题是，

我理解时间局部性，我认为对 i 和 j 的引用应该是时间局部性。我对吗？

我也理解空间局部性，因为我链接的问题是对 a[i] 的引用应该是空间局部性的答案。我对吗？

那人说，

"The inner loop will call same memory address when accessing a[i] ten times so that's an example for temporal locality I guess. But is there spatial locality also in the above loop?"

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

Answer 1

首先，引用 var可以是时间局部性或空间局部性而不是时​​间局部性，这是不正确的语法。小点。

现在，回答你的问题。

的原理时域指出两条指令在相对较短的时间范围内引用相同的位置。例如，在给出的代码中，a[i]经常被引用，指令如 a[i] = a[i] * 2和 a[i] = a[i] * 3被非常接近地处决。如果我们查看这个范围，我们可以说是对 j 的引用。和 a[i]是临时本地的。引用 i也是临时本地的，因为 i每次都被引用 a[i]是。但是，如果给定代码的最后一行读取类似 a[j] = a[j] * j 的内容，然后引用 i至少在内部循环 [1] 的范围内不会是时间局部的。

的原理空间局部性 声明两条指令引用连续的内存位置。引用 a[i]是一个很好的例子，因为人们可以假设(大部分时间)a[0]和 a[1]将在内存中彼此相邻。

前两个基本涵盖了这一点，但引用的文字是正确的，代码也展示了空间局部性。

[1] - 通常，当您谈论局部性时，它将在内存层次结构中的给定级别的上下文中，无论是 RAM 还是 L1 缓存或您拥有的东西。除了最有限的意义上，对两者的引用 i和 j是临时本地的。