给定代码段中引用的时间和空间局部性的所有出现

Question

我读过关于空间和时态定位的文章。

用几句话。

时态局部性：程序经常重复访问相同的内存位置。

空间局部性：程序还经常重复访问相邻的内存位置。

现在，我将分析以下代码，以查找引用的时间和空间局部性。

for (int i = 0, j = 10; i < 100; i++)
    a[i] = j++;

我只想出了以下几点。

空间

• a[i] = j++;在引用a[i]之后，我们将引用a[i+1]。
• 所有这一切的指令都存储在内存中的彼此之间。

时态

• i与100比较。
• i由一个：i++递增。
• 赋值a[i] = j++使用i作为数组索引。
• 用于索引每个a的数组基a[i]。
• j由赋值a[i] = j++中的增量增加。

那么，我对所有这些都是正确的吗?我是不是错过了其他的东西？

Answer 1

定义正好相反。

空间局部性-空间中的局部性，访问附近的内存位置。

时态局部性-时间局部性，多次访问同一位置。

在设计缓存时，空间局部性的使用使得当程序需要a[i]时，缓存就不能从内存中获取a[i]。它获取的条目很少，a[i], a[i+1], a[i+2] ...的大小相当于一条直线的大小。通过这样做，缓存预期您可能很快就会访问a[i+1]。当您这样做时，缓存不需要从内存中获取它，由于空间局部性的使用，它已经存在了。

访问i和j时会出现时态局部性。每次您需要i和j时，都不需要从内存中提取它，因为它是缓存的。通过缓存、i和j，缓存认为您将再次访问它，从而节省了从内存中获取它的时间。

为了回答确切的问题，是的，你已经确定了空间和时间位置。唯一不正确的地方是，您的语句“--所有这些操作的指令都存储在内存中的彼此之间”。将不会有单独的指令访问a[i]，a[i+1]。它将是一个循环中使用的单个指令，使用每次计算的内存地址。正如我前面所解释的，它的优点是缓存不需要为下一次迭代获取数据，因为它很可能是循环中早期迭代的一部分。