内部数组访问比std :: vector访问快得多 - Black Magic？

Question

我已经设置了一个测试程序来比较数组访问性能和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迭代器"的情况.

Answer 1

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

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;

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