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

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]。它将是循环内使用的单个指令，使用每次计算的内存地址。正如我在上面解释的那样，优点是缓存不需要为下一次迭代获取数据，因为它很可能作为循环中早期迭代的一部分获取。