2D阵列的两个方向之间的性能测试

Question

此代码(A)的执行速度比第二个快得多(10倍):

for(int w=0; w<width; w++) {
        for(int h=1; h<height; h++) {
            image[h][w] = (1-a)*image[h][w] + a*image[h-1][w];
        }
    }

第二个:

for(int h=0; h<height; h++) {
        for(int w=1; w<width; w++) {
            image[h][w] = (1-a)*image[h][w] + a*image[h][w-1];
        }
    }

这是为什么？在水平或垂直方向上遍历图像中的所有像素是相同的.

有没有办法加快第二个？

提前致谢.

Answer 1

这与参考地点有关.如果以与存储在内存中相同的顺序访问元素,这将比以跨步模式访问它们快得多,因为内存缓存和内存带宽将被更有效地利用.

上面会解释第二个版本比第一个版本更快,这正是我的盒子上发生的事情:

aix@aix:~$ time ./ver1
real    0m29.421s

aix@aix:~$ time ./ver2
real    0m2.198s

这是我用来分配数组的代码:

  double a = 0.5;
  int width = 2048;
  int height = 2048;
  double* data = new double[height * width];
  double** image = new double*[height];
  for (int i = 0; i < height; i++) {
    image[i] = data + i * width;
  }

版本1次以下循环:

  for (int iter = 0; iter < 100; iter++) {
    for(int w=0; w<width; w++) {
      for(int h=1; h<height; h++) {
        image[h][w] = (1-a)*image[h][w] + a*image[h-1][w];
      }
    }
  }

版本2循环:

  for (int iter = 0; iter < 100; iter++) {
    for(int h=0; h<height; h++) {
      for(int w=1; w<width; w++) {
        image[h][w] = (1-a)*image[h][w] + a*image[h][w-1];
      }
    }
  }

用g++4.4.3 编译-O3并运行一些描述的Xeon盒子(64位Ubuntu).

如果你仍然100%确定你会看到相反的效果,那么与我正在做的相比,你所做的事情肯定会有一些根本不同的东西.如果你告诉我们你的图像的尺寸以及它是如何分配的(为了帮助建立内存布局),它可能会有所帮助.