现实代码中的时间和空间局部性混淆 [英] Confused between Temporal and Spatial locality in real life code

问题描述

我正在阅读此问题，我想问更多关于他显示的代码，即

I was reading this question, I wanted to ask more about the code that he showed i.e

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

问题是

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

3. 那个人说，

1. I understand temporal locality, I think that references to i and j should be temporal locality. Am I right?
2. I also understand spatial locality, as the question I linked answers that references to a[i] should be spatial locality. Am I right?

3. The person said,

内部循环在访问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]生成的参考 应该是局部性的(他们将参考下一个 块中的元素).我说的对吗?

I don't agree with his guess. As the references generated by a[i] should be spacial locality (They will be referencing the next element in the block). Am I right?

推荐答案

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

First off, references to var can be temporally local or spatially local not temporal locality, which is improper grammar. Minor point.

现在，继续您的问题.

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] 的范围内.

1. The principle of Temporal locality states that two instructions reference the same location within a relatively short timeframe. For example, in the code given, a[i] is referenced frequently, with instructions like a[i] = a[i] * 2 and a[i] = a[i] * 3 being executed very close together. If we are looking at this scope, we could say that references to j and a[i] are temporally local. References to i are also temporally local, because i is referenced every time a[i] is. However, if the last line of the given code read something like a[j] = a[j] * j, then references to i would not be temporally local, at least in the scope of the inner loop^[1].

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

The principle of Spatial locality states that two instructions reference contiguous memory locations. References to a[i] are a good example of this, as one can assume (most of the time) that a[0] and a[1] will be next to each other in memory.

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

The first two basically cover this, but the quoted text is correct, and the code also demonstrates spatial locality.

[1]-通常，当您谈论局部性时，它将处于内存层次结构中给定级别的上下文中，无论是RAM还是L1高速缓存或您拥有什么.在除了最有限的意义上的所有方面，对i和j的引用在时间上都是局部的.

[1] - Generally, when you are talking about locality, it will be in the context of a given level in the memory hierarchy, whether it be RAM or the L1 cache or what have you. In all but the most limited sense, references to both i and j are temporally local.

这篇关于现实代码中的时间和空间局部性混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！