为什么数组<T,N>比vector <T>慢？

Question

今天,我决定把基准和比较的GCC可优化一些分歧std::vector和std::array.通常,我发现了我的预期:在每个短数组上执行任务比在集合等效向量上执行任务要快得多.

但是,我发现了一些意想不到的事情:std::vector用于存储数组集合比使用更快std::array.为了防止它是堆栈上大量数据的一些工件的结果,我还尝试将它作为一个数组分配在堆上和堆上的C风格数组中(但结果仍然类似于一个数组堆栈上的数组和数组的向量).

任何想法,为什么std::vector会永远跑赢大盘std::array(上编译器有更多的编译时间信息)？

我编译使用gcc-4.7 -std=c++11 -O3(gcc-4.6 -std=c++0x -O3也应该导致这个难题).使用bash-native time命令(用户时间)计算运行时.

码:

#include <array>
#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>

template <typename VEC>
double fast_sq_dist(const VEC & lhs, const VEC & rhs) {
  assert(lhs.size() == rhs.size());
  double result = 0.0;
  for (int k=0; k<lhs.size(); ++k) {
    double tmp = lhs[k] - rhs[k];
    result += tmp * tmp;
  }
  return result;
}

int main() {
  const std::size_t K = 20000;
  const std::size_t N = 4;

  // declare the data structure for the collection
  // (uncomment exactly one of these to time it)

  // array of arrays
  // runtime: 1.32s
  std::array<std::array<double, N>, K > mat;

  // array of arrays (allocated on the heap)
  // runtime: 1.33s
  //  std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >;

  // C-style heap array of arrays
  // runtime: 0.93s
  //  std::array<double, N> * mat = new std::array<double, N>[K];

  // vector of arrays
  // runtime: 0.93
  //  std::vector<std::array<double, N> > mat(K);

  // vector of vectors
  // runtime: 2.16s
  //  std::vector<std::vector<double> > mat(K, std::vector<double>(N));

  // fill the collection with some arbitrary values
  for (std::size_t k=0; k<K; ++k) {
    for (std::size_t j=0; j<N; ++j)
      mat[k][j] = k*N+j;
  }

  std::cerr << "constructed" << std::endl;

  // compute the sum of all pairwise distances in the collection
  double tot = 0.0;
   for (std::size_t j=0; j<K; ++j) {
     for (std::size_t k=0; k<K; ++k)
       tot += fast_sq_dist(mat[j], mat[k]);
   }

   std::cout << tot << std::endl;

  return 0;
}

注1:所有版本打印相同的结果.

注2:而只是为了证明之间的运行时间的差异std::array<std::array<double, N>, K>,std::vector<std::array<double, N> >以及std::vector<std::vector<double> >不是简单地从分配/初始化分配时,简单地分配收集的运行时间(即注释掉计算和打印tot)分别为0.000s,0.000s,和0.004s.

注3:每个方法都是单独编译和运行的(不是在同一个可执行文件中背靠背定时),以防止缓存中的不公平差异.

NB 4:
大会数组的数组:http://ideone.com/SM8dB
大会阵列的矢量:http://ideone.com/vhpJv
大会矢量的矢量:http://ideone.com/RZTNE

NB 5:为了绝对清楚,我绝不打算批评STL.绝对喜欢STL,不仅经常使用它,有效使用的细节也教会了我很多C++的微妙和强大功能.相反,这是一种智力上的追求:我只是为了学习有效的C++设计原则.

此外,归咎于STL是不合理的,因为很难对运行时差异的病因进行去卷积:启用优化后,可以通过编译器优化来减慢代码而不是加速代码.关闭优化后,它可以来自不必要的复制操作(可以优化并且永远不会在生产代码中执行),这些操作可能比某些数据类型更偏向某些数据类型.

如果你像我一样好奇,我会很乐意帮助您解决这个问题.

Answer 1

我突然想到的一件事是，堆栈上如此大的对象一次性可能会触发操作系统对堆栈空间的重新分配。尝试在 main 末尾转储 /proc/self/maps