Is boost::container::vector faster than std::vector? Why?

Question

I did a interesting test on boost vector and std vector as the following

int N = 10000;
{
    boost::timer::auto_cpu_timer t;
    std::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

{
    boost::timer::auto_cpu_timer t;
    boost::container::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

win32 release, compiled by vc2010, /O2 /Oy-

for N = 10000

for std vector: 0.140849s wall, 0.140401s user + 0.000000s system = 0.140401s CPU (99.7%)

f boost vector: 0.056174s wall, 0.062400s user + 0.000000s system = 0.062400s CPU (111.1%)

for N = 100,000

std: 14.050757s wall, 14.055690s user + 0.000000s system = 14.055690s CPU (100.0%)

boost: 5.585048s wall, 5.584836s user + 0.000000s system = 5.584836s CPU (100.0%)

When adding reserve(N) to both, CPU times change little.

Any difference between them? Boost is much faster than std, why? Thanks.

Check sizeof(), std::vector 16, while boost::container::vector 12.

Answer 1

Keep in mind that the speed of all code will vary from compiler to compiler and between versions of that compiler. The standard libraries provide code which works portably from platform to platform, but it is difficult to make speed guarantees.

If you were only running this code on your own machine, then you should choose the faster option, if that is what you want. If you are asking this question because you want to make a universally-faster choice, then I don't think there's a way to know what that is short of testing it.

Naturally, when one is wondering about speed in a general way, as you seem to be, you'd want to assess that for inserting many different numbers of objects, run many replicate tests, and use a variety of objects (classes, doubles, chars, et cetera). You may also choose to do all this with varying amounts of free stack space. If you don't consider all the factors then your question by default becomes, "Why, in my particular case, is there a speed difference?" It is usually difficult to say.

A better question might be, "I have observed under a variety of test conditions a speed difference between these two pieces of similarly-functioning code. Is there some architectural difference between them which may account for this?" The answer is maybe.

cplusplus.com on std::vector

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (see push_back).

From this we see that the behavior you're seeing is dependent on your particular version of the STL library you are using, and that growth should be logarithmic, and that growth usually requires a lot of copying. A deque does not require a lot of copying, so it may scale better in your tests.

Presumably, boost::container functions similarly. I don't know because I couldn't find a write-up on it. But I did find this:

All containers offered by Boost.Container implement placement insertion, which means that objects can be built directly into the container from user arguments without creating any temporary object. For compilers without variadic templates support placement insertion is emulated up to a finite (10) number of arguments.

If std::vector does not use a similar architecture and instead creates a temporary object, this could lead to differences in run-times. But probably this does not apply to int types. Perhaps someone else can find a different architectural difference.