为什么C数组比std::array快这么多？

Question

为什么C数组比std::array快这么多？

16

我们目前正在使用C++编写一些对于大量矩阵和向量进行操作的性能关键代码。根据我们的研究，std::array 和标准C数组之间应该没有太大的性能差异(参见这个问题或这个问题)。然而，在测试过程中，我们发现使用C数组比std::array可以获得巨大的性能提升。以下是我们的演示代码：

#include <iostream>
#include <array>
#include <sys/time.h>

#define ROWS 784
#define COLS 100
#define RUNS 50

using std::array;

void DotPComplex(array<double, ROWS> &result, array<double, ROWS> &vec1, array<double, ROWS> &vec2){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void DotPSimple(double result[ROWS], double vec1[ROWS], double vec2[ROWS]){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void MatMultComplex(array<double, ROWS> &result, array<array<double, COLS>, ROWS> &mat, array<double, ROWS> &vec){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

void MatMultSimple(double result[ROWS], double mat[ROWS][COLS], double vec[ROWS]){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

double getTime(){
    struct timeval currentTime;
    gettimeofday(&currentTime, NULL);
    double tmp = (double)currentTime.tv_sec * 1000.0 + (double)currentTime.tv_usec/1000.0;
    return tmp;
}

array<double, ROWS> inputVectorComplex = {{ 0 }};
array<double, ROWS> resultVectorComplex = {{ 0 }};
double inputVectorSimple[ROWS] = { 0 };
double resultVectorSimple[ROWS] = { 0 };

array<array<double, COLS>, ROWS> inputMatrixComplex = {{0}};
double inputMatrixSimple[ROWS][COLS] = { 0 };

int main(){
  double start;
  std::cout << "DotP test with C array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPSimple(resultVectorSimple, inputVectorSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "DotP test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPComplex(resultVectorComplex, inputVectorComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C array : " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultSimple(resultVectorSimple, inputMatrixSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultComplex(resultVectorComplex, inputMatrixComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;
}

编译命令: icpc demo.cpp -std=c++11 -O0 编译结果如下:

DotP test with C array: 
Duration: 0.289795 ms
DotP test with C++ array: 
Duration: 1.98413 ms
MatMult test with C array : 
Duration: 28.3459 ms
MatMult test with C++ array: 
Duration: 175.15 ms

通过-O3标志：

DotP test with C array: 
Duration: 0.0280762 ms
DotP test with C++ array: 
Duration: 0.0288086 ms
MatMult test with C array : 
Duration: 1.78296 ms
MatMult test with C++ array: 
Duration: 4.90991 ms

C数组实现在没有编译器优化的情况下速度更快。为什么？使用编译器优化后，点积同样快。但是对于矩阵乘法，使用C数组仍然可以显著提速。是否有一种方法可以在使用std :: array时实现相等的性能？

更新：

所用编译器：icpc 17.0.0

使用gcc 4.8.5，我们的代码运行速度比使用任何优化级别的英特尔编译器都要慢得多。因此，我们主要关注英特尔编译器的行为。

如Jonas建议，我们调整了RUNS 50,000，并获得以下结果(英特尔编译器)：

使用-O0标志：

DotP test with C array: 
Duration: 201.764 ms
DotP test with C++ array: 
Duration: 1020.67 ms
MatMult test with C array : 
Duration: 15069.2 ms
MatMult test with C++ array: 
Duration: 123826 ms

使用 -O3 标志：

DotP test with C array: 
Duration: 16.583 ms
DotP test with C++ array: 
Duration: 15.635 ms
MatMult test with C array : 
Duration: 980.582 ms
MatMult test with C++ array: 
Duration: 2344.46 ms

- The Floe

5

另外，您的合成基准测试并不真正有用。您主要是在测量编译器是否能够确定结果将会被未使用（在这种情况下，所有计算都可以省略）或者是常量（在这种情况下，编译器可以在编译时完成所有计算）。在这两种情况下，您没有测量到任何有用的信息。 - Uli Schlachter

7

因为你禁用了优化，导致函数调用没有被内联，从而付出了抽象惩罚的代价？ - davmac

8

如果想让编译器优化掉抽象内容，就需要启用优化。 - Uli Schlachter

4

在https://godbolt.org/g/9MnTLs上，`MatMultComplex`和`MatMultSimple`似乎产生了相同的汇编代码。 - eerorika

5

这不是关于C语言的问题，因此我已经移除了C标签。 - JeremyP

显示剩余8条评论

2个回答

12

为什么没有启用编译器优化时会比使用编译器优化快很多呢？原因不得而知。如果您不让编译器进行优化，即使两个代码片段具有相同的行为，您也不能期望它们具有类似的性能。启用优化后，编译器可以将抽象代码转换为高效代码，从而使性能可比较。

使用 std::array 会涉及到函数调用，而使用指针则不会。例如，std::array::operator[] 是一个函数，而指针的下标运算符不是。进行函数调用可能比不进行函数调用慢。所有这些函数调用都可以被优化掉（内联展开），但如果您选择不启用优化，则这些函数调用将保留。

但对于矩阵乘法，使用 C 数组仍然会有显著的加速。可能是基准测试中的一个小问题，或者是编译器的问题。在这里，两个函数具有相同的汇编代码，因此具有相同的性能。

编辑：我同意Jonas的答案。这个基准测试迭代次数太少了。此外，没有重复基准测试并分析偏差，无法确定两个测量之间的差异是否显着。

结论如下：

启用优化后，C数组不比std::array更快。至少在使用clang 3.9.1编译时是这样的，正如链接所示。也许你的编译器会产生不同的汇编代码，但我看不出为什么它会这样做。
C++的“零成本”抽象只有在优化后才是真正的零成本。
编写有意义的微基准测试并不容易。

- eerorika

1

矩阵的C++版本与std::array版本不同。 C++数组只是一组ROWS*COLS个双精度块。 std::array版本至少在概念上是一个数组的数组。这意味着要完全解除引用它需要两个下标操作，而C++版本只需要一个计算。我很惊讶一些现代C++编译器能够将抽象开销几乎完全优化掉。 - JeremyP

2

@JeremyP 当然，2D数组在概念上也是一个数组的数组。我唯一看到的区别是std::array的两个解引用在不同的（内联）函数调用中，因此可能对优化顺序敏感。在合并解引用之前，必须展开这些函数，而指针的两个解引用甚至在内联之前就存在了。坦率地说，如果汇编输出不是（至少几乎）相同的话，我会感到失望。 - eerorika

@user2079303 我在某种程度上同意你的答案。增加运行次数并不会改变我们编译器的行为。比率仍然保持不变。我发现在遵循Uli Schlachter的评论后，基准测试中存在一个“怪癖”。如果在计算后实际使用函数的结果，则两种实现的性能大致相等。 - The Floe

1

@TheFloe 我建议你比较一下编译器生成的汇编代码，看看它们的区别在哪里。 - eerorika

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonas · Accepted Answer

首先，您使用的运行次数太少了。就个人而言，在运行代码之前，我没有意识到您的“持续时间”测量是以毫秒为单位的。

通过将RUNS增加到500万次，对于DotPSimple和DotPComplex计时如下：

使用C数组的DotP测试：

持续时间：1074.89

使用C ++数组的DotP测试：

持续时间：1085.34

也就是说，它们非常接近速度相等。实际上，由于基准测试的随机性质，无论哪个最快的都会因测试而异。对于MatMultSimple和MatMultComplex也是如此，尽管它们只需要50,000次运行。

如果您真的想要更多地了解并测量，您应该接受这种基准测试的随机性，并估算“持续时间”测量的分布。包括函数的随机顺序，以消除任何排序偏差。

编辑：汇编代码（来自user2079303的答案）明确证明了启用优化后没有差异。因此，在启用优化时，零成本抽象实际上是零成本的，这是一个合理的要求。

更新：

我使用的编译器：

g++ (Debian 6.3.0-6) 6.3.0 20170205

使用以下命令：

g++ -Wall -Wextra -pedantic -O3 test.cpp

使用这个处理器：

Intel(R) Core(TM) i5-4300U CPU @ 1.90GHz