6

我已经建立了一个测试程序来比较数组访问性能和 std::vector 的性能。我发现了几个类似的问题，但似乎都没有解决我的具体问题。当我过去读到它们应该是等效的时，我一直在为为什么数组访问似乎比向量访问快 6 倍而摸不着头脑。事实证明，这似乎是英特尔编译器 (v12) 和优化的一个功能（发生在 -O1 以上的任何情况下），因为我在使用 gcc v4.1.2 时看到 std::vector 的性能更好，而数组只有gcc v4.4.4 的 2 倍优势。我在具有 Xeon X5355 内核的 RHEL 5.8 机器上运行测试。顺便说一句，我发现迭代器比元素访问更快。

我正在使用以下命令进行编译：

icpc -fast test.cc
g++44 -O3 test.cc

谁能解释速度的显着提高？

#include <vector>
#include <iostream>

using namespace std;

int main() {
  int sz = 100;
  clock_t start,stop;
  int ncycle=1000;
  float temp  = 1.1;

  // Set up and initialize vector
  vector< vector< vector<float> > > A(sz, vector< vector<float> >(sz,  vector<float>(sz, 1.0)));

  // Set up and initialize array
  float*** a = new float**[sz];
  for( int i=0; i<sz; ++i) {
    a[i] = new float*[sz];
    for( int j=0; j<sz; ++j) {
      a[i][j] = new float[sz]();
      for( int k=0; k<sz; ++k)
        a[i][j][k] = 1.0;
    }
  }

  // Time the array
  start = clock();
  for( int n=0; n<ncycle; ++n )
    for( int i=0; i<sz; ++i )
      for( int j=0; j<sz; ++j )
        for( int k=0; k<sz; ++k )
          a[i][j][k] *= temp;

  stop = clock();
  std::cout << "STD ARRAY: " << double((stop - start)) / CLOCKS_PER_SEC << " seconds"     << std::endl;

  // Time the vector
      start = clock();
  /*
  */
  for( int n=0; n < ncycle; ++n )
    for (vector<vector<vector<float> > >::iterator it1 = A.begin(); it1 != A.end();     ++it1)
      for (vector<vector<float> >::iterator it2 = it1->begin(); it2 != it1->end();     ++it2)
        for (vector<float>::iterator it3 =it2->begin(); it3 != it2->end(); ++it3)
          *it3 *= temp;
  /*
     for( int n=0; n < ncycle; ++n )
       for( int i=0; i < sz; ++i )
         for( int j=0; j < sz; ++j )
           for( int k=0; k < sz; ++k )
             A[i][j][k] *= temp;
  */

  stop = clock();
  std::cout << "VECTOR: " << double((stop - start)) / CLOCKS_PER_SEC << " seconds" <<     std::endl;


  for( int i=0; i<100; ++i) {
    for( int j=0; j<100; ++j)
      delete[] a[i][j];
  }
  for( int i=0; i<100; ++i) {
    delete[] a[i];
  }
  delete[] a;
  return 0;
}

解决了

在注意到 Bo 表示编译器“了解所有循环”并因此可以比向量情况更优化它之后，我用调用“rand()”的乘法替换了乘法“temp”。这拉平了竞争环境，实际上似乎使 std::vector 略有领先。各种场景的时序如下：

ARRAY (flat): 111.15 seconds
ARRAY (flat): 0.011115 seconds per cycle
ARRAY (3d): 111.73 seconds
ARRAY (3d): 0.011173 seconds per cycle
VECTOR (flat): 110.51 seconds
VECTOR (flat): 0.011051 seconds per cycle
VECTOR (3d): 118.05 seconds
VECTOR (3d): 0.011805 seconds per cycle
VECTOR (flat iterator): 108.55 seconds
VECTOR (flat iterator): 0.010855 seconds per cycle
VECTOR (3d iterator): 111.93 seconds
VECTOR (3d iterator): 0.011193 seconds per cycle

要点似乎是向量与数组一样快，并且在展平（连续内存）并与迭代器一起使用时稍快。我的实验平均只进行了超过 10,000 次迭代，因此可以说这些都是大致相同的，应该由最容易使用的那个来决定使用哪个；就我而言，这将是“3d 迭代器”的情况。

4

3 回答 3

3

这里没有黑魔法，编译器很容易在这里看到

for( int n=0; n<ncycle; ++n )
   for( int i=0; i<sz; ++i )
     for( int j=0; j<sz; ++j )
       for( int k=0; k<sz; ++k )
          a[i][j][k] *= temp;

在编译时一切都是已知的。它可以轻松展开循环以加快速度。

于 2012-08-23T15:14:28.160 回答
1

数组只是一个指向内存区域的指针。你不能比这更直接。

向量需要调用内联函数来做同样的事情。这可能会或不会真正内联。因为 inline 和 __forceinline 只是编译器内联代码的指南。反过来，编译器可以自由地做它想做的任何事情。

此外，迭代器不一定是指针。编译器正在调用一个内联函数，该函数可能是内联的，也可能不是内联的。（同样，内联是对编译器的指导，而不是规则）。

有疑问时。编译为汇编并查看生成的代码。如果编译器正在完成它的工作，那么应该没有明显的差异。但是，如果编译器没有内联应该内联的内容，那么使用向量而不是数组会大大降低编译器的性能。

于 2013-04-30T07:03:28.367 回答
0

嵌套数组中的所有元素都位于连续的内存位置，因此当编译器遇到该形式的表达式时，a[x][y][z]它会生成计算实际索引的代码，其中仅涉及整数乘法和加法。std::vector另一方面，嵌套实际上是嵌套的。对于表达式v[x][y][z]，涉及另外两个级别的间接，因为v[x]实际上存在一个std::vector对象，其中包含指向向量数组的指针，而向量数组又包含真实数据。

于 2013-04-30T10:06:48.173 回答