17

今天我决定对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-nativetime命令（用户时间）计算的。

代码：

#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：所有版本都打印相同的结果。

NB 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，分别。

NB 3：每个方法都是单独编译和运行的（不是在同一个可执行文件中背靠背计时），以防止缓存中的不公平差异。

NB 4：
数组数组的组装：http: //ideone.com/SM8dB
数组向量的组装：http: //ideone.com/vhpJv
向量的组装：http: //ideone.com/RZTNE

NB 5：为了绝对清楚，我绝不打算批评 STL。一个绝对喜欢的 STL，不仅我经常使用它，而且有效使用的细节教会了我很多 C++ 微妙而伟大的特性。相反，这是一种智力追求：我只是在安排时间来学习高效 C++ 设计的原则。

此外，责怪 STL 是不合理的，因为很难对运行时差异的病因进行反卷积：启用优化后，编译器优化可能会减慢而不是加快代码速度。在关闭优化的情况下，它可能来自不必要的复制操作（将被优化并且永远不会在生产代码中执行），这可能比其他数据类型更偏向某些数据类型。

如果您像我一样好奇，我希望您能帮助解决这个问题。

4

6 回答 6

3

我怀疑array在堆栈或堆上分配时，编译器只需要array在使用vector分配器时对齐，它可能使用operator new它必须返回适合任何类型对齐的内存。如果分配的内存恰好更好地对齐，允许更多的缓存命中/更大的读取，那么这似乎可以很容易地解释性能差异。

于 2012-07-03T12:05:24.477 回答
3

考虑第二个和第三个测试。从概念上讲，它们是相同的：K * N * sizeof(double)从堆中分配字节，然后以完全相同的方式访问它们。那么为什么不同时期呢？

您所有的“更快”测试都有一个共同点：new[]. 所有较慢的测试都分配new在堆栈上或堆栈上。vector可能使用new[]Under the Hood™。唯一明显的原因是它的new[]实现new比预期的要显着不同。

我要建议的是，new[]它将回退mmap并直接在页面边界上分配，从而加快对齐速度，而其他两种方法不会在页面边界上分配。

考虑使用 OS 分配函数直接映射已提交的页面，然后将 astd::array<std::array<double, N>, K>放入其中。

于 2012-07-01T02:46:41.200 回答
1

我刚刚在我的桌面上使用 MSVC++ 2010 进行了尝试，除了5.0 秒之外vector，所有测试的时间都相同（1.6 秒）。vectors

我会考虑查看您的库的实际实现，array看看vector是否有任何明显的差异。

尝试用迭代器样式的循环替换索引样式的循环，看看这是否会影响性能。

另外，尝试clock()从程序内部对程序进行计时：除其他外，这可以让您判断代码的哪一部分表现不同。甚至可能值得在嵌套范围中添加，这样您也可以对对象析构函数进行计时。

于 2012-07-01T20:31:58.597 回答
1

当简单的解释就足够时，不要寻找复杂的解释。这是一个优化器错误。普通的、固定大小的 C 风格堆栈分配数组的性能类似于std::array，所以不要责怪std::array实现。

于 2012-07-01T07:04:03.993 回答
0

我看到的唯一大区别是您的数据存储方式不同。在前两种情况下，您的数据存储在一个巨大的块中。所有其他情况都存储指向矩阵中行的指针。我不太清楚为什么这会使您的代码更快，但它可能与查找和 CPU 预取有关。在迭代之前尝试缓存矩阵行，这样您就不需要查找mat[k]每个条目。这可以使它更快，甚至速度。可能是您的编译器可以在这种情况下执行此操作，vector<array<T>>但不能在这种array<array<T>>情况下执行此操作。

于 2012-07-01T11:18:23.913 回答
0

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

于 2012-07-01T02:44:37.127 回答