[c++] 为什么我的程序在循环8192个元素时很慢?



Answers

下面的测试已经用Visual C ++编译器完成了,因为它被默认的Qt Creator安装使用(我猜没有优化标志)。 当使用GCC时,Mystical的版本和我的“优化”代码没有太大的区别。 因此,结论是编译器优化比人类更关心微观优化(最后是我)。 我留下我的答案的其余部分供参考。

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

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

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

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

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的优秀答案中解释的缓存问题。 一开始它只是伪代码。 我被要求在评论中做测试...这是一个完全重构的测试版本。

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;

基本上,当SIZE是2048的倍数时,这个程序很慢,例如执行时间:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

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

如何解决这个问题会很好,但如果有人能解释这些执行时间,我已经够快乐了。

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






Related