C++码的缓存优化

Question

这似乎有点开放，但我在为多个处理器和缓存优化一段C++代码时遇到了困难。

比多个处理器更重要的是缓存:我正在迭代两个嵌套循环。

for(int i=0; i<n; i++){
  //do a little something here with a single array
  for(int j=0; j<whoaAnotherArray[n].size(); j++){
    * access array[i][j] and otherArray[i][j] and store in a variable
       - an example is: "int x = array[i][j] + otherArray[i][j]"
    * compare variable to some other array[index calculated from i and j]
       - an example is: "if (x < yetAnotherArray[i*n+j]){ //do something to yetAnotherArray }"
  }
}

我的数组(数组和otherArray)的大小非常大。N是他们的尺寸。

有什么方法可以让缓存更加友好吗？我已经不再使用链表了，这对缓存来说是很糟糕的。我在某个地方读到，我的访问命令也是高速缓存高效的。

FWIW，这是负重循环检测算法的一部分.

我在想，也许因为我的数组太大了(它们是整数数组，顺便说一句)，是否应该把它们分开一点，以便它们更适合缓存？但我不确定这是对的还是如果是的话，该怎么做呢？

我也开始使用openmp了。我做的唯一一件事就是增加

#pragma omp parallel for

在右循环之前，我得到了很好的利用。我想学习如何更好地使用并行性，但在代码中的循环之外，我不确定我能做什么。一直以来:我一直在努力使缓存变得友好。

Answer 1

改进缓存使用的一种可能是修改访问array和otherArray的模式。当然，当您阅读array[i][j]时，您的机器会将一行“内存”移动到缓存中。当然，当您阅读otherArray[i][j]时，您的机器会将一行“内存”移动到缓存中。有可能的是，要读取第二行，第一行必须从缓存刷新到RAM中。然后，通过从yetAnotherArray读取一个值，情况会变得更糟(可能)。

实际发生的事情在很大程度上取决于同时发生的其他事情、缓存中的其他内容以及正在执行的任何其他操作。这是很难搞清楚的。

如果您(主要的)数组访问模式要求同时来自两个(或所有3个)数组的element[i][j]，那么您想要安排一些事情，使它们处于读取的同一“内存行”中。一种方法是将这3个数组合并为一个m*n*3数组，其中superArray[i][j][1]位于superArray[i][j][2]旁边，superArray[i][j][2]位于superArray[i][j][3]旁边，数组的3个平面分别表示原始数组之一。当然，只有在索引排序正确的情况下，这才能起作用，所以要比我考虑得更多。

最后：

1. 这可能会把你优雅的程序变成一个意大利面的混乱--但这是为了提高速度而付出的一个小代价！
2. 我所说的“行”是指平台从RAM加载到高速缓存的任何块。
3. 谷歌周围的循环瓷砖和条状采矿。编译器在这方面还不是很擅长，您可以提供的任何帮助都应该得到提高执行速度的回报。

Answer 2

阅读这两篇赫伯萨特的文章，特别是第一篇

http://www.ddj.com/go-parallel/article/showArticle.jhtml?articleID=217500206

http://ddj.com/architect/208200273

Answer 3

有一个名为卡舍尔的程序(一个增值插件)可以帮助您分析代码在虚拟缓存中的表现。我会使用它来查看您的代码是如何与CPU缓存相对应的。(我已经有一段时间没有使用它了，所以我不记得它是否能够自动检测CPU的缓存属性。您可能需要为CPU提供确切的缓存参数。)

您还可以尝试一些优化，理想情况下，编译器正在或应该这样做：

1)将这一行改为：

for(int j=0; j<whoaAnotherArray[n].size(); j++){

通过以下方式：

  int len = whoaAnotherArray[n].size();
  for(int j=0; j<len; j++){

2)在外部循环中创建指向数组的指针：

int* pArray = array[i] - 1;
int* pOtherArray = pOtherArray[j] - 1;

并对循环中的第一个指针访问使用预增量：

int x = *(++pArray) + *(++pOtherArray);

(是的，，我认识，很丑。，我知道编译器应该为您做这件事。但就在几个月前，我发现这确实与gcc的4.3(?)在linux上。( YMMV.)

3)如果有任何方法重构代码，使您一次通过array循环，然后在第二次遍历otherArray，则尝试这样做。对你来说不太可能，但我不知道。关键是，您希望一次使内存访问尽可能集中在一个数组上。

祝好运。