5

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

测试.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 相当的性能

4

1 回答 1

5

由于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你的数据支持的事情。

于 2013-09-06T15:50:02.467 回答