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

Question

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

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

问题是，

1. 我理解时间局部性，我认为引用I和j应该是时间局部性。我说的对吗?
2. 我也理解空间局部性，因为我链接的问题的答案，引用a[I]应该是空间局部性。我说的对吗?

3. 那个人说，

   "当访问a[i] 10时，内循环将调用相同的内存地址我想这就是时间局部性的一个例子。但是有吗?空间局部性也在上面的循环中?"

   我不同意他的猜测。作为a[i]产生的参考应该是空间局部性(它们将引用下一个元素)。我说的对吗?

Answer 1

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

现在开始你的问题。

1. 时间局部性原则说明两个指令在相对较短的时间范围内引用相同的位置。例如，在给出的代码中，a[i]被频繁引用，而a[i] = a[i] * 2和a[i] = a[i] * 3这样的指令被非常紧密地执行。如果我们看一下这个作用域，我们可以说对j和a[i]的引用是暂时本地的。对i的引用也是暂时本地的，因为每次a[i]被引用时都会引用i。然而，如果给定代码的最后一行读的是类似a[j] = a[j] * j的东西，那么对i的引用就不是暂时本地的，至少在内循环^[1]的作用域中是这样。

2. 空间局域性原则说明两个指令引用连续的内存位置。引用a[i]就是一个很好的例子，因为可以假设(大多数时候)a[0]和a[1]将在内存中彼此相邻。

3. 前两个基本涵盖了这一点，但引用的文本是正确的，并且代码还演示了空间局部性。

[1] -一般来说，当你谈论局部性时，它将是在内存层次结构中给定级别的上下文中，无论是RAM还是L1缓存或其他什么。在大多数情况下，对i和j的引用都是暂时本地的。

Answer 2

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

我认为我们花了很多时间和精力来理解术语，在这种情况下有点混乱/复杂。当我不注意"空间"one_answers"时间"这两个术语时，我发现它更容易理解。

让我们从基础开始。

让我们试着理解缓存是什么——一个比主存访问速度更快的地方。那很酷。但是这个地方是有限的和昂贵的，所以应该明智地使用它。但是，您(或操作系统)如何决定在缓存中放入什么，不放入什么呢?应该有办法知道我们将来需要什么。啊，未来的预言!(少数派报告!)。

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

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

局域性的概念基本上是为了识别要带入缓存的数据和指令，以便我们可以减少缓存丢失并有效地利用这个特殊的位置。

Answer 3

外层循环是空间局部性的一个例子。它按顺序递增内部for循环调用的地址。

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

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

局部性是缓存用来最小化对内存调用的一种度量。如果一条指令需要知道一个不在缓存中的内存地址的值，它将访问内存并将所有周围的内存位置也存储在缓存中。

Answer 4

让我们从定义时间和空间局部性开始。

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

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

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

现在看看这个例子，这里变量sum被一次又一次地使用，它显示Temporal Locality，然后数组arr的值被按顺序访问，即arr[0]， arr[1]， arr[2]，…这显示空间位置，因为数组是连续的(相邻的)内存块，因此正在提取靠近当前内存位置的数据。

现在看看这个例子

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

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