C++代码的缓存优化

问题描述：

这似乎是一种开放式的，但我在为多个处理器和缓存优化一块C++代码时遇到了问题。C++代码的缓存优化

比多处理器更重要的是缓存：我遍历2嵌套循环

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是它们的大小。

有没有办法让这个缓存更友好？我已经开始使用链接列表，这对缓存来说很糟糕。我在某处读到我的访问命令[i] [j]也是缓存有效的。

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

我在想也许因为我的数组非常庞大（它们是整数btw数组），最好是将它们打散一点以便它们更好地适应缓存？但我不确定这是对的还是如果是，如何去做。

我也开始使用openmp。我一直在做的唯一事情是加入

#pragma omp parallel for

之前的权利for循环，我得到体面的利用。我想了解如何更好地使用并行性，但除了代码中的循环之外，我不确定我能做什么。而且一直都是这样：我试图保持缓存的友好。

究竟是什么你想在这里实现什么？我相当确信有一个比O（N²）更有效的解决方案。 – jwueller 2010-12-02 22:16:48

通常一个好的编译器（特别是当你明确地问他时）在循环中插入* precache *指令。 – ruslik 2010-12-02 22:17:35

@elusive道歉，它不是O（N^2），但O（N），因为我的内部循环不是N.我将解决这个问题... @ruslik我使用g ++，我该怎么做？ – Sam 2010-12-02 22:19:04

答

缓存使用改进的一种可能性是修改访问模式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][3]的旁边，其中阵列的3个平面各代表一个原始阵列。当然，这只有在索引订购权的时候才有用，所以给它比我更多的思考。

最后：

这可能会改变你的优雅程序转换成意大利面条烂摊子 - 但这是一个很小的代价为提高速度！
''我的意思是无论您的平台从内存加载到高速缓存一次去块。
谷歌周围循环平铺 和条带开采。编译器是不是很好，在这个还没有和任何帮助，你可以提供应该奖励改善执行速度。

答

有一个名为Cachegrind（Valgrind插件）的程序，可以帮助您分析代码对虚拟缓存的执行情况。我会和你一起看看你的代码如何处理你的CPU的缓存。（我已经使用它一段时间了，所以我不记得它是否可以自动检测你的CPU的缓存属性，你可能需要给它确切的CPU缓存参数。）

你也可以尝试一些优化，理想情况下，你的编译器或应该做的事情：

1）更换这行：

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

有：

2）创建的指针进入该阵列在外环：在循环的第一指针访问

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

和使用preincrements：

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

（是的，我知道这是丑陋的。 我知道编译器应该为你做这个。但是在几个月前，我发现这对Linux上的gcc 4.3（？）有所帮助。 YMMV）

3）如果有什么方法可以重构代码，以便一次循环遍历array，然后在第二遍循环遍历otherArray，然后尝试执行此操作。似乎不太可能在你的情况下，但我不知道。重点是，您希望一次将内存访问尽量集中到一个数组。

祝你好运。

答

阅读香草萨特这2篇文章特别是第一个

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

http://ddj.com/architect/208200273

C++代码的缓存优化

相关推荐