c++ - 二维阵列两个方向之间的性能测试

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

这与 locality of reference 有关.如果您按照元素存储在内存中的顺序访问元素，这将比以跨步模式访问它们快得多，因为内存缓存和内存带宽将得到更有效的利用。

以上内容可以解释第二个版本比第一个版本更快，而这正是我的盒子上发生的情况:

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

使用 -O3 使用 g++ 4.4.3 编译并在某种描述的 Xeon 机器上运行(64 位 Ubuntu)。

如果您仍然 100% 确定您看到的是相反 效果，那么与我所做的相比，您所做的肯定有根本不同。如果您告诉我们图像的尺寸以及图像的精确分配方式(以帮助建立内存布局)，这可能会有所帮助。