为什么我的程序在循环8192个元素时变慢？
这是来自程序的摘录。 matriximg[][]的大小为SIZE×SIZE，初始化为：
img[j][i] = 2 * j + i
然后，你制作一个matrixres[][] ，这里的每个字段都是imgmatrix中围绕它的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。 据我所知，这是因为内存pipe理，但我对这个主题并不太了解，这就是为什么我在这里问。
另外如何解决这个问题将会很好，但如果有人能解释这些执行时间，我已经够快乐了。
我已经知道malloc / free了，但问题不在于内存的使用量，而仅仅是执行时间，所以我不知道如何提供帮助。
这个差异是由以下相关问题引起的同一个超级alignment问题引起的：
- 为什么转置512×512的matrix要比转置513×513的matrix慢得多？
- matrix乘法：matrix大小差异小，时序差异大
但那只是因为代码还有其他问题。
从原始循环开始：
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; } }
这样就留下了我们感兴趣的两个外部循环。
现在我们可以看到这个问题在这个问题上是一样的： 为什么迭代遍历二维数组时，循环的顺序会影响性能？
您正在逐列迭代matrix，而不是逐行。
要解决这个问题，你应该交换两个循环。
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
下面的testing已经用Visual C ++编译器完成了，因为它被默认的Qt Creator安装使用（我猜没有优化标记）。 当使用GCC时，Mystical的版本和我的“优化”代码没有太大的区别。 所以结论是编译器优化比人类更关心微观优化（最后是我）。 我把剩下的答案留作参考。
这样处理图像效率不高。 最好使用单维数组。 处理所有像素是在一个循环中完成的。 随机访问点可以使用：
pointer + (x + y*width)*(sizeOfOnePixel)
在这种情况下，最好是将三个像素组的总和进行水平计算并caching，因为每个像素使用三次。
我做了一些testing，我认为这是值得分享的。 每个结果是五次testing的平均值。
原始码由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
一次caching水平只提前一行，所以他们留在caching：
// 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
结论：
- 没有使用几个指针的好处，只是增量（我认为它会更快）
- caching水平和数比计算好几次要好。
- 两次通过不是三倍，只有两次。
- 同时使用一次和caching中间结果可能会快3.6倍
我相信可以做得更好。
注意请注意，我写这个答案的目的是针对一般性能问题，而不是在Mystical的优秀答案中解释的caching问题。 在开始时，它只是伪代码。 我被要求在评论中做testing…这是一个完全重构的版本与testing。
元素访问顺序照顾在那里仍然有一些低悬的水果。 积累可以通过一种方式来完成，当向右迭代时，只需要从存储器中提取3个新值并进行累加。 诀窍是知道如何放下最左边的列; 当添加一个新列时，请记住它的值，直到它离开采样窗口。
费用前：9读，9加，1分后费用：3读，3加，1分
将采样窗口视为3×3框，您需要分别跟踪每列（1×3）。 积累一个新的列，并删除最老的一个。
该部分是一个高延迟指令，所以隐藏延迟可能是有利的，但在去那里之前，如果按常量除法和如果循环展开（由编译器）已经做了一些延迟补偿，应该检查编译器输出。
但是，在正确使用caching的最显着的优化之后，这些确实是小事。
