时间戳

首页 > 解决方案 > 在嵌套循环中访问数组时缓存未命中

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

问题描述

所以我从我的教授那里得到了这个问题，我不知道为什么vector2比vector1.

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

矢量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;
          }
     }
}

矢量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，一次只能访问一个元素？我们不确定这是否正确，也不确定如何将缓存行引入其中。

标签： cperformancecachingcpu-cachecache-locality

解决方案

我们认为这可能是因为vector2具有更好的空间定位性，因为内部循环不断访问数组，而在vector1中，一次只能访问一个元素？

好吧，两个代码具有相同的访问模式，以 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”次迭代时访问它一次。

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

推荐阅读