为什么我的程序在恰好循环 8192 个元素时很慢？

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

为什么转置 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;
    }
}

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

现在我们可以看到这个问题的问题是一样的：Why does the order of the loops affect performance when iterating over a 2D array?

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

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

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 seconds
8192: 2.122 seconds
8193: 1.582 seconds

互换外环：

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

---

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

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

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

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

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

user1615209的原始代码：

8193: 4392 ms
8192: 9570 ms

神秘的版本：

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

两遍使用一维数组并像这样寻址：

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 倍的速度

我确信可以做得更好。

注意请注意，我写这个答案是为了解决一般性能问题，而不是 Mystical 的优秀答案中解释的缓存问题。一开始它只是伪代码。我被要求在评论中进行测试......这是一个完全重构的带有测试的版本。

---