为什么我的程序在遍历8192个元素时速度很慢？

Question

下面是所讨论的程序的摘录。矩阵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，但问题不在于使用的内存数量，而仅仅是执行时间，所以我不知道这会有什么帮助。

Answer 1

产生差异的原因是与以下相关问题相同的超对齐问题：

• 为什么转置512x512的矩阵比转置513x513的矩阵慢得多？
• 矩阵乘法：矩阵大小差异小，定时差异大

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

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