在嵌套循环中访问数组时缓存未命中

Question

所以我的教授向我提出了这个问题，我无法弄清楚为什么 vector2 比 vector1 更快并且缓存未命中更少。

假设下面的代码是有效的可编译 C 代码。

vector 2:

void incrementVector2(INT4* v, int n) {
     for (int k = 0; k < 100; ++k) {
          for (int i = 0; i < n; ++i) {
               v[i] = v[i] + 1;
          }
     }
}

vector 1:

void incrementVector1(INT4* v, int n) {
     for (int i = 0; i < n; ++i) {
          for (int k = 0; k < 100; ++k) {
               v[i] = v[i] + 1;
          }
     }
}

注意: INT4 表示整数大小为 4 字节。

就 CPU 规范而言:缓存大小 = 12288KB，行大小 = 64B，并且仅考虑与主内存交互的单个缓存。

问题

为什么 vector2 的运行时间比 vector1 更快？为什么 vector1 的缓存未命中次数比 vector2 多？

我和几个同学为此研究了一段时间，但无法弄清楚。我们认为这可能是由于 vector2 具有更好的空间位置性，因为内部循环不断地访问数组，而在 vector1 中，只有一个元素一次访问？我们不确定这是否正确，也不确定如何将缓存行引入其中。

Answer 1

We thought it could be due to the fact that vector2 has better spatiallocatlity, since the array is been accessed by the inner loopconstantly, while in vector1, only one element is accessed at a time?

嗯，两个代码具有相同的访问模式，以步长 1 迭代数组 v。缓存空间局部性方面两个代码是相同的。然而，第二个代码:

void incrementVector1(INT4* v, int n) {
     for (int i = 0; i < n; ++i) {
          for (int k = 0; k < 100; ++k) {
               v[i] = v[i] + 1;
          }
     }
}

具有更好的时间局部性，因为您访问同一元素 100 次，而在:

void incrementVector2(INT4* v, int n) {
     for (int k = 0; k < 100; ++k) {
          for (int i = 0; i < n; ++i) {
               v[i] = v[i] + 1;
          }
     }
}

在每“n”次迭代中您只能访问一次。

所以要么你犯了一个错误，你的老师正在玩某种奇怪的游戏，要么我错过了一些明显的东西。