15

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

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] 十次时，内部循环将调用相同的内存地址，所以我猜这是时间局部性的一个例子。但是在上面的循环中也有空间局部性吗？”

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

4

4 回答 4

28

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

现在，关于你的问题。

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

  2. 空间局部性原则指出两条指令引用连续的内存位置。引用a[i]就是一个很好的例子，因为人们可以假设（大部分时间）a[0]并且a[1]将在内存中彼此相邻。

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

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

于 2011-10-18T18:33:55.943 回答
5

写下这个答案，因为即使在阅读了关于这个问题的其他答案、其他一些问题和维基百科之后我也没有得到它（这更令人困惑。）

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

让我们从基础开始。

让我们试着了解一下缓存是什么——一个比主存访问速度更快的地方。这很酷。但是这个地方有限且昂贵，所以应该明智地使用它。但是您（或操作系统）将如何决定将什么放入缓存以及不放入什么？应该有某种方法可以知道我们将来需要什么……啊，未来的预测！（少数派报告！敲响一些钟声？）。

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

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

局部性的概念基本上是识别数据和指令以引入缓存，以便我们可以减少缓存未命中并有效利用这个特殊位置。

于 2018-07-21T14:39:14.037 回答
2

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

内部循环展示了时间局部性。完全相同的内存地址连续访问十次，每次都乘以 j。

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

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

于 2011-10-18T18:28:19.147 回答
2

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

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

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

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

现在看这个例子，这里变量 sum 被一次又一次地使用，它显示了时间局部性，然后数组 arr 的值被按顺序访问，即 arr[0], arr[1], arr[2] ,...依此类推，它显示空间局部性，因为数组是连续（相邻）内存块，因此正在获取靠近当前内存位置的数据。

现在看这个例子

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

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

于 2019-02-15T10:26:24.960 回答