c++ - 二维 vector 优化

Question

这只是一个紧凑的测试用例，但我有一个 double vector ，我想填充所有成对差异的方阵(2D vector )。当使用 -O3 优化编译时，这在我的计算机上大约需要 1.96 秒(仅从嵌套的双 for 循环计算)。

#include <vector>
using namespace std;

int main(){
  vector<double> a;
  vector<vector<double> > b;
  unsigned int i, j;
  unsigned int n;
  double d;

  n=10000; //In practice, this value is MUCH bigger
  a.resize(n);

  for (i=0; i< n; i++){
    a[i]=static_cast<double>(i);
  }

  b.resize(n);
  for (i=0; i< n; i++){
    b[i].resize(n);
    b[i][i]=0.0; //Zero diagonal
  }

  for (i=0; i< n; i++){
    for (j=i+1; j< n; j++){
      d=a[i]-a[j];

      //Commenting out the next two lines makes the code significantly faster
      b[i][j]=d; 
      b[j][i]=d;
    }
  }
  return 0;
}

但是，当我注释掉这两行时:

b[i][j]=d; 
b[j][i]=d;

程序在大约 0.000003 秒内完成(仅根据嵌套的双 for 循环计算)!我真的没想到这两条线会成为限速步骤。我已经盯着这段代码看了一段时间，但我没有想法。任何人都可以就如何优化这段简单的代码以显着减少时间提出任何建议吗？

Answer 1

当您注释掉这两行时，嵌套循环中剩下的就是继续计算 d 然后丢弃结果。由于这对程序的行为没有任何影响，编译器只会优化嵌套循环。这就是程序几乎立即完成的原因。

事实上，我通过使用 g++ -O3 编译代码两次，一次仅使用 d=a[i]-a[j] 语句确认了这一点嵌套循环，一次完全删除嵌套循环。发出的代码是相同的。

然而，您的代码目前比它必须的要慢，因为它缺少缓存。当您像这样在嵌套循环中访问二维数组时，如果可能，您应该始终安排迭代在内存中连续进行。这意味着第二个索引应该是变化更快的那个。对 b[j][i] 的访问违反了此规则并丢失了缓存。所以让我们重写。

之前:

for (i=0; i< n; i++){
    for (j=i+1; j< n; j++){
        d=a[i]-a[j];
        b[i][j]=d; 
        b[j][i]=d;
    }
}

时间:

real    0m1.026s
user    0m0.824s
sys     0m0.196s

之后:

for (i = 0; i < n; i++) {
    for (j = 0; j < i; j++) {
        b[i][j] = a[j] - a[i];
    }
    for (j = i+1; j < n; j++) {
        b[i][j] = a[i] - a[j];
    }
}

时间:

real    0m0.335s
user    0m0.164s
sys     0m0.164s