为什么我的程序在完全循环8192个元素时会变慢？

Question

为什么我的程序在完全循环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 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

编译器是GCC。据我所知，这是因为内存管理，但我对这个主题并不太了解，这就是我在这里问的原因。

另外如何解决这个问题会很好，但如果有人能解释这些执行时间，我已经足够开心了。

我已经知道malloc / free了，但问题不在于使用的内存量，它只是执行时间，所以我不知道这会有多大帮助。

Answer 1

差异是由以下相关问题引起的相同超对齐问题引起的：为什么转换512x512的矩阵要比转换513x513的矩阵慢得多？矩阵乘法：矩阵大小差异小，时序差异大但那只是因为代码还有另外一个问题。从原始循环开始：for(i=1;i<SIZE-1;i++)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;for(j=1;j<SIZE-1;j++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(k=-1;k<2;k++)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(l=-1;l<2;l++)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+l][i+k]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;/=&nbsp;9;}首先注意两个内环是微不足道的。它们可以按如下方式展开：for(i=1;i<SIZE-1;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;for(j=1;j<SIZE-1;j++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;/=&nbsp;9; &nbsp;&nbsp;&nbsp;&nbsp;}}这样就留下了我们感兴趣的两个外环。现在我们可以看到问题在这个问题中是一样的：为什么在迭代2D数组时，循环的顺序会影响性能？您是按列而不是按行迭代矩阵。要解决此问题，您应该交换两个循环。for(j=1;j<SIZE-1;j++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;for(i=1;i<SIZE-1;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]=0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i&nbsp;&nbsp;]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j-1][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j&nbsp;&nbsp;][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;+=&nbsp;img[j+1][i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res[j][i]&nbsp;/=&nbsp;9; &nbsp;&nbsp;&nbsp;&nbsp;}}这完全消除了所有非顺序访问，因此您不再在大功率二次上获得随机减速。酷睿i7 920 @ 3.5 GHz原始代码：8191:&nbsp;1.499&nbsp;seconds8192:&nbsp;2.122&nbsp;seconds8193:&nbsp;1.582&nbsp;seconds互换的外循环：8191:&nbsp;0.376&nbsp;seconds8192:&nbsp;0.357&nbsp;seconds8193:&nbsp;0.351&nbsp;seconds