提问



以下是相关程序的摘录。矩阵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了,但问题不在于使用的内存量,它只是执行时间,所以我不知道这会有多大帮助。

最佳参考


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



  • 为什么将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;
    }
}


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





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

其它参考1


以下测试已经使用Visual C ++编译器完成,因为它由默认的Qt Creator安装使用(我猜没有优化标志)。当使用GCC时,Mystical的版本和我的优化代码之间没有太大的区别。所以结论是编译器优化比人类更好地处理微优化(我最后)。我留下余下的答案参考。





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


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


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


我做过一些测试,我认为值得分享。每个结果平均有五个测试。


用户1615209的原始代码:


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


使用1D数组进行两次传递并进行如下寻址:


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

其它参考2


处理的元素访问顺序仍然存在一些悬而未决的成果。可以以这样的方式进行累积:当向右迭代时,仅需要从存储器中取出3个新值并累积。诀窍是知道如何删除最左边的列;添加新列时,请记住它的值,直到它离开采样窗口。


之前的费用:9读,9加,1师
费用后:3读,3加,1师


将采样窗口视为3x3框,您可以分别跟踪每列(1x3)。累积新列并删除最旧的列。


除法是高延迟指令,因此隐藏延迟可能是有利的,但在去那里之前,如果省略除以常数并且循环展开(由编译器)已经进行了一些延迟补偿,则应检查编译器输出。


但在正确使用缓存的最戏剧性优化之后,这些都是微不足道的事情。