boost :: stable_vector插入比std :: vector慢几个数量级.为什么？

Question

我注意到std :: vector和boost :: stable_vector之间存在很大的性能差异.下面是我构建并在向量和稳定向量中插入100,000个int的示例.

TEST.CPP:

#include <iostream>
#include <vector>
#include <boost/container/stable_vector.hpp>
#include <boost/timer/timer.hpp>

int main(int argc, char** argv) {
    int size = 1e5;
    boost::timer::cpu_timer timer;

    timer.start();
    std::vector<int> vec(size);
    timer.stop();
    std::cout << timer.format();

    timer.start();
    boost::container::stable_vector<int> svec(size);
    timer.stop();
    std::cout << timer.format();
}

编译:

g++ -O3 test.cpp -o test -lboost_system-mt -lboost_timer-mt

输出:

 0.000209s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
 5.697013s wall, 5.690000s user + 0.000000s system = 5.690000s CPU (99.9%)

造成这种巨大差异的原因是什么？我的理解是两种类型都应具有相似的插入性能.

更新:提升版本:1.54

dev/stable_vector_test: g++ --version
i686-apple-darwin11-llvm-g++-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

我在代码中添加了std :: list,并尝试在-O3之外传递-DNDEBUG.

dev/stable_vector_test: make
g++ -g test.cpp -o test -lboost_system-mt -lboost_timer-mt
dev/stable_vector_test: ./test
size: 10000
vector:         0.000047s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
list:           0.001168s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
stable_vector:  0.963679s wall, 0.960000s user + 0.000000s system = 0.960000s CPU (99.6%)
dev/stable_vector_test: make opt
g++ -O3 -DNDEBUG test.cpp -o test -lboost_system-mt -lboost_timer-mt
dev/stable_vector_test: ./test
size: 10000
vector:         0.000038s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
list:           0.000659s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
stable_vector:  0.000752s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

因此,使用-O3和-DNDEBUG,我可以获得与std :: list相当的性能

Answer 1

由于stable_vector不使用连续存储,因此std::vector分配其初始内存需要更长的时间似乎是合理的.

正如在stable_vector上的背景文章中所指出的,一种可能的实现stable_vector涉及为向量的每个元素分配单独的节点.当然,构造函数的源代码stable_vector显示它调用resize,insert使用一对迭代器调用,并insert执行N个节点分配:

// (initialization...)
while(first != last){
  const node_ptr p = this->priv_get_from_pool();
  BOOST_ASSERT(!!p);
  //Put it in the index so rollback can return it 
  //in pool if construct_in_place throws
  *it_past_newly_constructed = p;
  //Constructs and fixes up pointers This can throw
  this->priv_build_node_from_it(p, it_past_newly_constructed, first);
  ++first;
  ++it_past_newly_constructed;
}

所以它正在做类似的事情std::list,你的数据支持.