为什么我的程序在循环8192个元素时很慢？
这是来自该程序的摘录。 矩阵img[][]的大小为SIZE×SIZE，初始化为：
img[j][i] = 2 * j + i
然后，你创建一个矩阵res[][] ，并且这里的每个字段都是img矩阵中围绕它的9个字段的平均值。 为简单起见，边框保留为0。
for(i=1;i<SIZE-1;i++)
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
for(k=-1;k<2;k++)
for(l=-1;l<2;l++)
res[j][i] += img[j+l][i+k];
res[j][i] /= 9;
}
这就是这个程序的全部内容。 为了完整起见，以下是以前的内容。 之后没有代码。 正如你所看到的，这只是初始化。
#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
img[j][i] = (2*j+i)%8196;
基本上，当SIZE是2048的倍数时，这个程序很慢，例如执行时间：
SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs
编译器是GCC。 据我所知，这是因为内存管理，但我对这个主题并不太了解，这就是我在这里问的原因。
如何解决这个问题会很好，但如果有人能解释这些执行时间，我已经够快乐了。
我已经知道malloc / free，但问题不在于使用的内存量，而仅仅是执行时间，所以我不知道这会有什么帮助。
这种差异是由以下相关问题中的同一个超级对齐问题引起的：
但那只是因为代码还有其他问题。
从原始循环开始：
for(i=1;i<SIZE-1;i++)
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
for(k=-1;k<2;k++)
for(l=-1;l<2;l++)
res[j][i] += img[j+l][i+k];
res[j][i] /= 9;
}
首先注意到两个内部循环是微不足道的。 他们可以展开如下：
for(i=1;i<SIZE-1;i++) {
for(j=1;j<SIZE-1;j++) {
res[j][i]=0;
res[j][i] += img[j-1][i-1];
res[j][i] += img[j ][i-1];
res[j][i] += img[j+1][i-1];
res[j][i] += img[j-1][i ];
res[j][i] += img[j ][i ];
res[j][i] += img[j+1][i ];
res[j][i] += img[j-1][i+1];
res[j][i] += img[j ][i+1];
res[j][i] += img[j+1][i+1];
res[j][i] /= 9;
}
}
这样就留下了我们感兴趣的两个外部循环。
现在我们可以看到问题在这个问题中是一样的：为什么迭代遍历二维数组时，循环的顺序会影响性能？
您正在逐列迭代矩阵，而不是逐行迭代。
为了解决这个问题，你应该交换两个循环。
for(j=1;j<SIZE-1;j++) {
for(i=1;i<SIZE-1;i++) {
res[j][i]=0;
res[j][i] += img[j-1][i-1];
res[j][i] += img[j ][i-1];
res[j][i] += img[j+1][i-1];
res[j][i] += img[j-1][i ];
res[j][i] += img[j ][i ];
res[j][i] += img[j+1][i ];
res[j][i] += img[j-1][i+1];
res[j][i] += img[j ][i+1];
res[j][i] += img[j+1][i+1];
res[j][i] /= 9;
}
}
这完全消除了所有的非顺序访问，因此您不再在大的二权位上随机放慢速度。
Core i7 920 @ 3.5 GHz
原始代码：
8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds
互换外环：
8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
下面的测试已经用Visual C ++编译器完成了，因为它被默认的Qt Creator安装使用（我猜没有优化标志）。 当使用GCC时，Mystical的版本和我的“优化”代码没有太大的区别。 因此，结论是编译器优化比人类更关心微观优化（最后是我）。 我留下我的答案的其余部分供参考。
以这种方式处理图像效率不高。 最好使用单维数组。 处理所有像素是在一个循环中完成的。 随机访问点可以使用：
pointer + (x + y*width)*(sizeOfOnePixel)
在这种情况下，最好计算并缓存三个水平像素组的总和，因为它们每次使用三次。
我做了一些测试，我认为这是值得分享的。 每个结果是五次测试的平均值。
user1615209的原始代码：
8193: 4392 ms
8192: 9570 ms
神秘的版本：
8193: 2393 ms
8192: 2190 ms
两次使用一维数组：第一次为水平和，第二次为总和和平均值。 用三个指针进行两遍寻址，只有这样的增量：
imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];
for(i=SIZE;i<totalSize-SIZE;i++){
resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}
8193: 938 ms
8192: 974 ms
两次使用一维数组并进行如下处理：
for(i=SIZE;i<totalSize-SIZE;i++){
resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}
8193: 932 ms
8192: 925 ms
一次通过缓存水平只提前一行，所以他们留在缓存中：
// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
// Compute horizontal sum for next line
hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
// Final result
resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}
8193: 599 ms
8192: 652 ms
结论：
我相信可以做得更好。
注意请注意，我写了这个答案来解决一般性能问题，而不是Mystical的优秀答案中解释的缓存问题。 一开始它只是伪代码。 我被要求在评论中做测试...这是一个完全重构的测试版本。
元素访问顺序照顾在那里仍然有一些低悬的水果。 积累可以通过一种方式完成，当向右迭代时，只需要从内存中提取3个新值并进行累加。 诀窍是知道如何放下最左边的列; 添加新列时，请记住它的值，直到它离开采样窗口。
费用前：9读，9加，1分后费用：3读，3加，1分
将采样窗口视为3x3框，您需要分别跟踪每列（1x3）。 积累一个新的列并删除最老的一个。
该部分是高延迟指令，所以隐藏延迟可能是有利的，但在去那里之前，如果按常量除法并且如果循环展开（由编译器）已经做了一些延迟补偿，应该检查编译器输出。
但是，在正确使用缓存的最显着的优化之后，这些确实是小事。
链接地址: http://www.djcxy.com/p/279.html上一篇: Why is my program slow when looping over exactly 8192 elements?
下一篇: Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?