Is it more efficient to preallocate a vector?

Question

In C++ Primer fourth edition, by Stanley B.Lippman, Josee Lajoie and Barbara E. Moo it states:

Because vectors grow efficiently, it is usually best to let the vector grow by adding elements to it dynamically as the element values are known.

and

Readers accustomed to using c or java might expect that because vector elements are stored contiguously, it would be best to preallocate the vector at its expected size. In fact the contrary is the case...

and

Allthough we can preallocate a given number of elements in a vector, it is usually more efficient to define an empty vector and add elements to it.

Assuming this is correct (the authors are as reputable as they come, one is a co-author of C++ itself) then can anyone give me a case that proves this statement, and explain why?

Answer 1

It depends.

If you don't know what the final size will be, then let the vector allocate using its allocation scheme (usually doubles each time, or somewhere around there). This way you avoid reallocating for every single element:

std::vector<int> v;

// good:
for (/* populate v */) // unknown number of iterations
{
    v.push_back(i); // possible reallocation, but not often
}

// bad:
for (/* populate v */) // unknown number of iterations
{
    v.reserve(v.size() + 1); // definite reallocation, every time
    v.push_back(i); // (no reallocation)
}

But if you know ahead of time you won't be reallocating, then preallocate:

std::vector<int> v;

// good:
v.reserve(10); 
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // no reallocations
}

// not bad, but not the best:
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // possible reallocation, but not often (but more than needed!)
}

Answer 2

I timed this simple example:

#include<iostream>
#include<vector>

int main() {

    int limit = 100 * 1000 * 1000;
    std::vector<long> my_vec;
    my_vec.reserve(limit); // comment out this line to not preallocate

    for (int i=0; i < limit; i++) {
        my_vec.push_back(i);
    }

    long my_sum = 0;
    for (int i=0; i < limit; i++) {
        my_sum += my_vec[i];
    }

    std::cout << my_sum << std::endl;
    return 0;
}

Complied with:

g++ -std=c++11 -O2 my_file.cpp -o my_exec

And found the difference to be substantial:

Without preallocation:

real    0m3.366s
user    0m1.656s
sys     0m1.660s

With preallocation:

real    0m1.688s
user    0m0.732s
sys     0m0.936s

My conclusion here is: If building a vector is a big part of the program, then preallocating for efficiency makes sense. However, building a larger vector over and over is unlikely, and thus it is rarely a bottle neck. However, using reserve() has other advantages besides preallocating.

Bjarne Stroustrup in The C++ programming language (4th addition) has this to say:

I used to be careful about using reserve() when I was reading into a vector. I was surprised to find that for essentially all my uses, calling reserve() did not measurably affect performance. The default growth strategy worked just as well as my estimates, so I stopped trying to improve performance using reserve(). Instead I use it to increase predictability of reallocation delays and to prevent invalidation of pointers and iterators.

Answer 3

It can be. It depends a lot on what the elements are, how much work it is to copy or construct them, and how many there are.

If you preallocate a vector you will end up calling the default constructor for each element to make empty elements, and then copying the item over the space later. If you add elements it can just copy or construct the element in place which may be more efficient.