c - 为什么我的程序慢, 当循环恰好超过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;

基本上,当大小是 2048的倍数时,这个程序是缓慢的,比如 执行时间:


SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

编译器是 GCC 。从我所知道的,这是因为内存管理,但我对这个主题知之甚少,这就是为什么我在这里请求的原因。

另外,如何修复这将是很好的,但如果有人可以解释这些执行时间我已经足够快乐了。

我已经知道了 malloc/free,但是这个问题没有多少内存,它只是执行时间,所以我不知道如何帮助。

时间:

差异是由与以下相关问题相同的super-alignment问题引起的:

但这只是因为代码还有另外一个问题。

从原始循环开始:


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;
 }
}

这就是我们感兴趣的两个 outer-loops 。

现在我们可以看到问题是同样的问题: 为什么循环的顺序会在迭代 2个数组时影响性能

你正在迭代矩阵column-wise而不是 row-wise 。


要解决这个问题,你应该交换两个循环。


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;
 }
}

对大型这就消除了所有的non-sequential访问完全这样以后就不会再获得随机


核心 i7 920 @ 3.5 GHz

原始代码:


8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

交换的Outer-Loops:


8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds

下列测试已经用 Visual C++ 编译器完成,因为默认Qt创建者安装( 我猜没有优化标志) 使用了它。 使用GCC时,神秘和我的"优化"代码之间没有很大的差别。 因此,我们的结论是编译器优化比人类的( 终于我了) 更好地优化了微优化。 我留下了剩下的答案供参考。


以这种方式处理图像是无效的。 最好使用一维数组。 处理所有像素在一个循环中完成。 可以使用以下方法来随机访问点:


pointer + (x + y*width)*(sizeOfOnePixel)

在这种情况下,最好水平计算和缓存三个像素组的总和,因为它们每次使用三次。

我做了一些测试,我认为值得分享。 每个结果都是五个测试的平均值。

user1615209的原始代码:


8193: 4392 ms
8192: 9570 ms

神秘的版本:


8193: 2393 ms
8192: 2190 ms

使用 1个数组的两次传递: 第一个通过水平求和,第二个用于垂直和和平均值。 有三个指针的两次传递,并且只有这样增量:


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

使用 1数组和类似这样的寻址:


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

结论:

  • 没有使用多个指针的好处( 我认为它会更快)
  • 缓存水平总和比计算它们好一些。
  • 两次传递的速度不是三倍,只有两次。
  • 使用一次传递和缓存中介结果,可以更快地实现 3.6次

我相信可以做得更好。

注意 请注意,我写了这个针对目标一般性能问题的答案,而不是用出色的神秘答案解释的缓存问题。 起初它只是伪代码。 我被要求在评论中做测试。。 这是一个完全重构的版本,带有测试。

...