在现实代码中混淆时间和空间位置

问题描述 投票:11回答:4

我正在读这个question,我想更多地询问他所展示的代码,即

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

问题是,

  1. 我理解时间局部性,我认为对i和j的引用应该是时间局部性。我对吗?
  2. 我也理解空间局部性,因为我链接答案的问题是对[i]的引用应该是空间局部性。我对吗?
  3. 那个人说, “内部循环在访问[i]十次时会调用相同的内存地址,这是我猜的时间局部性的一个例子。但是在上面的循环中是否还有空间局部性?” 我不同意他的猜测。由[a]生成的引用应该是空间局部性(它们将引用块中的下一个元素)。我对吗?
computer-science spatial computer-architecture temporal
4个回答
25
投票

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

现在,回答你的问题。

  1. 时间局部性的原理指出两个指令在相对短的时间范围内引用相同的位置。例如,在给定的代码中,经常引用a[i],其中a[i] = a[i] * 2a[i] = a[i] * 3等指令的执行非常接近。如果我们正在研究这个范围,我们可以说对ja[i]的引用在时间上是局部的。对i的引用也暂时是局部的,因为每次i都引用a[i]。但是,如果给定代码的最后一行读取类似a[j] = a[j] * j的内容,那么对i的引用将不会在时间上是局部的,至少在内部循环[1]的范围内。
  2. 空间局部性的原理指出两个指令引用连续的存储器位置。参考a[i]就是一个很好的例子,因为人们可以假设(大部分时间)a[0]a[1]在记忆中彼此相邻。
  3. 前两个基本上涵盖了这个,但引用的文本是正确的,代码也演示了空间局部性。

[1] - 通常,当您谈论局部性时,它将位于内存层次结构中给定级别的上下文中,无论是RAM还是L1缓存,还是您拥有的内容。除了最有限的意义外,对ij的引用在时间上是局部的。


3
投票

写下这个答案,因为即使在阅读了这个问题的其他答案之后我还没有得到它,还有一些其他问题和维基百科(这更令人困惑。)

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

让我们从基础开始。

让我们试着了解缓存是什么 - 一个比主内存更快访问的地方。这很酷。但这个地方有限而且价格昂贵,所以应该明智地使用它。但是你(或OS)将如何决定放入缓存以及不放入什么?应该有一些方法可以知道将来我们需要什么......未来的预测啊! (少数派报告!敲响一些钟声?)。

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

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

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


2
投票

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

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

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

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


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;

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

© www.soinside.com 2019 - 2024. All rights reserved.