c - 了解时空局部性

Question

我正在为我的架构期末考试而学习，并遇到了以下代码行：

for(i = 0; i <= N ;i++){
   a[i] = b[i] + c[i]; 
}

问题是：“此代码片段如何演示时间和空间局部性的示例？一定要考虑数据和指令的内存引用。”

就空间局部性而言，我相信代码通过访问连续的内存位置（a[0] 然后 a[i] 等）来演示它。然而，我的困惑来自时间局部性。我不确定这段代码如何在短时间内引用相同的位置？任何形式的帮助将不胜感激。

Answer 1

我不确定这段代码如何在短时间内引用相同的位置？

如前所述，该变量i的访问频率很高，请在您的示例中使用以下代码行：

a[i] = b[i] + c[i];

在这个例子中a，b和call 可能是指指向不同内存位置的数组类型（即使是连续的，仍然不同）；但是，每次引用该变量时都会读取该变量，然后确定要引用的数组的i位置。

这样想：

get i from memory and store value in register x.
get value of b + [value in register x] from memory, store in register b.
get i from memory and store value in register y
get value of c + [value in register y] from memory, store in register c.
get i from memory and store value in register z
add value of [register b] to value in [register c] and store in memory location a + [value in register z]

优化编译器可能会看到这个时间局部性，而是执行类似于以下的操作：

get i from memory and store value in register i.
get value of b + [value in register i] from memory, store in register b.
get value of c + [value in register i] from memory, store in register c.
add value of [register b] to value in [register c] and store in memory location a + [value in register i]

正是以这种方式，i在相邻参考之间具有时间上的接近性。

我希望这能有所帮助。

Answer 2

我不确定这段代码如何在短时间内引用相同的位置。

除了txtechhelp 的 answer之外，构成该 for 循环的指令也存储在内存中。这些指令每次执行时都会从内存/缓存中“获取”。由于这些指令中的每一个都在非常短的时间内执行 N+1 次，这证明了时间局部性。