为什么我的程序在循环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 8192float img[SIZE][SIZE]; // input imagefloat res[SIZE][SIZE]; //result of mean filterint 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 secsSIZE = 8192: 7.20 secsSIZE = 8193: 3.18 secs

编译器是GCC。据我所知，这是因为内存管理，但我真的不知道太多关于这个主题，这就是为什么我在这里问。

如何解决这个问题也很好，但如果有人能解释这些执行时间，我已经很高兴了。

我已经知道malloc/free，但问题不在于使用的内存量，而仅仅是执行时间，所以我不知道这会有什么帮助。

96758 次浏览
小开
最佳答案

这种差异是由以下相关问题中相同的超对齐问题引起的：

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

从原始循环开始：

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

这就剩下了我们感兴趣的两个外环。

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

您正在按列而不是按行迭代矩阵。

要解决这个问题，您应该交换两个循环。

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

这完全消除了所有非顺序访问，因此您不再会在2的大幂上随机减速。

Core i7 920@3.5 GHz

原始代码：

8191: 1.499 seconds8192: 2.122 seconds8193: 1.582 seconds

互换外环：

8191: 0.376 seconds8192: 0.357 seconds8193: 0.351 seconds
小开

以下测试是使用VisualC++编译器完成的，因为它是默认的Qt Creator安装（我猜没有优化标志）。使用GCC时，Mystical的版本和我的“优化”代码之间没有太大区别。所以结论是编译器优化比人类更好地照顾微优化（最后是我）。我留下我的其余答案供参考。

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

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

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

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

用户1615209的原始代码：

8193: 4392 ms8192: 9570 ms

神秘的版本：

8193: 2393 ms8192: 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 ms8192: 974 ms

使用一维数组进行两次传递并像这样寻址：

for(i=SIZE;i<totalSize-SIZE;i++){resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;}
8193: 932 ms8192: 925 ms

一次缓存水平和只领先一行，因此它们留在缓存中：

// Horizontal sums for the first two linesfor(i=1;i<SIZE*2;i++){hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];}// Rest of the computationfor(;i<totalSize;i++){// Compute horizontal sum for next linehsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];// Final resultresPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;}
8193: 599 ms8192: 652 ms

结论：

  • 使用几个指针和增量没有好处（我以为会更快）
  • 缓存水平和比多次计算它们要好。
  • 两次传球不是快三倍，只有两次。
  • 使用单次传递和缓存中间结果可以实现3.6倍的速度

我相信有可能做得更好。

注意请注意，我写这个答案是针对一般性能问题，而不是Mystical优秀答案中解释的缓存问题。一开始它只是伪代码。注释中要求我做测试…这是一个完全重构的测试版本。


提交答案