首页 文章

为什么我的程序在完全循环8192个元素时会变慢？

提问于
浏览 次
708

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

c++ performance memory-management gcc

3 回答

  • 53

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

    但那只是因为代码还有另外一个问题 .

    从原始循环开始：

    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;
    }
}

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

    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
    回复于
  • 896

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

    费用前：9读，9加，1师后费：3读，3加，1师

    将采样窗口视为3x3框，您可以分别跟踪每列（1x3） . 累积新列并删除最旧的列 .

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

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

    回复于
  • -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倍

    我相信它可以做得更好 .

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

    回复于

相关问题