为什么我的程序在完全循环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++) 
    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;
    }}

这完全消除了所有非顺序访问，因此您不再在大功率二次上获得随机减速。

---

酷睿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