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

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% 确定您看到了相反效果，那么与我正在做的事情相比，您所做的事情一定有根本上的不同。如果您告诉我们图像的尺寸以及它的准确分配方式（以帮助建立内存布局），这可能会有所帮助。

Answer 2

aix 关于引用位置的说法是正确的。更明确地说，这是因为内存层次结构。

当您第一次访问一个元素时，可能是缓存未命中。加载整个缓存行，然后进行读/写。

根据您遍历数组的方向，下一次访问将在位置 i+1 或 i+N 处。 i+1 可能位于同一高速缓存行中，但 i+N 通常位于另一高速缓存行中，需要另一次大的读取。

对于小N，整个事情最终都在缓存中，并且方向并不重要。对于适当大的 N，并非所有数组都可以放入缓存中最快（且最小）的部分，因此包含元素 i 的缓存行可能会在访问 i+M*N 之前被删除，并且必须在访问 i 之前重新加载+1。

为了使其尽可能快，您必须特别关注 CPU 架构。有些比其他对对齐更加敏感。有些人更喜欢每个缓存行一次（达到容量），然后再进行复制。当然，时间切片和处理器共享会把事情搞砸。