Boost :: stable_vector is an order of magnitude slower than std :: vector. What for?

Question

I notice a big performance difference between std :: vector and boost :: stable_vector. The following is an example when I create and paste 100,000 ints into a vector and a stable vector.

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(); } 

compilation:

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

exit:

  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%) 

What is the reason for this huge discrepancy? I understand that both types should have similar insert performance.

UPDATE: accelerated version: 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. 

I added std :: list to the code and tried passing -DNDEBUG in addition to -O3.

 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%) 

So, with -O3 and -DNDEBUG I get comparable performance with std :: list

Answer 1

Since stable_vector does not use continuous storage, it seems reasonable that it will take much more to allocate it than std::vector initial memory.

As noted in the background message on stable_vector , one of the possible implementations of stable_vector involves allocating a separate node for each vector element. And, of course, the source code for the stable_vector constructor shows that it calls resize , which calls insert with a pair of iterators, and insert executes the N node distribution:

 // (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; } 

So, it does something similar to std::list , which supports your data.