C - 缓存行和关联性

Question

背景

阅读有关缓存优化的论文（与循环中的缓存行相关等）。

这个问题与此上下文相关：拥有 1024 个整数的数组。

尺寸：CPU 缓存 64k，缓存行 32 字节，整数大小为 4 字节。

Intel Core 2 Duo 处理器。

问题

根据我的 CPU，8 个整数适合在一个缓存行中。

[0,1,2,3,4,5,6,7,8,9,10,...,1023]
         ^
If I want to access 4 and go downward, 3,2,1 and 0 will be loaded already. 5,6,7 are loaded uselessly.

[0,1,2,3,4,5,6,7,8,..,1023]
               ^
If I want to access 7 and go downward, all the next elements will be in cache already. if I want to go upward, according to my cpu I will have to load another cache line immediatly after the arr[7] read.

我是正确的吗？

更进一步

那么什么会告诉我arr [4]不是在地址上，会导致缓存行加载而不是arr [7]？ 如果我的陈述是正确的，我们不仅应该考虑数组对齐，还应该考虑整个程序的内存对齐以最小化缓存浪费，对吗？

- Larry

Answer 1

但是，如何知道arr [4]不在会导致缓存行加载的地址上，而不是在arr [7]处？

通常情况下，int数组在4字节边界上对齐（假设int为32位，byte为8位），因此您无法确定缓存行边界的位置。

需要学习的教训是，不应该担心浪费偶尔缓存的行（即使您需要的数据少于32字节也使用2个缓存行），因为在C编程时这主要是由系统控制的。

如果您遇到性能问题，可以担心的是选择减少缓存未命中次数的算法。

典型的例子是循环：

int array[N][M];  // Assume N * M * sizeof (int) is much larger than the cache.

// Example 1
for (i=0; i<N; i++) {
  for (j=0; j<M; j++) {
    <do something with array[i][j]>
  }
}

// Example 2
int array[N][M];
for (j=0; j<M; j++) {
  for (i=0; i<N; i++) {
    <do something with array[i][j]>
  }
}

其中一个示例会造成约8倍于另一个的缓存未命中，因为它以错误的顺序访问元素。

- Klas Lindbäck

---

谢谢。+1 为失控加油 - Larry

我想问一下，我的想法正确吗？ex 2会有更多的缓存未命中吗？ - Robert Houghton

Answer 2

就您的主要问题而言，两种情况下您都是正确的。

在第二种情况下，当加载 arr[7] 并可能想要继续向上时，您应该注意到编译器或某些预取机制可能考虑到这种数据的空间局部性，从而提高了性能。

进一步地，如果数组在内存中没有正确对齐，读取数组中的其他地址可能会导致缓存行加载，而不是 arr[7]。但在这种情况下，对齐不取决于您，而取决于编译器。

- chrk