std::vector::reserve performance penalty

Question

inline void add(const DataStruct& rhs) {
   using namespace boost::assign;
   vec.reserve(vec.size() + 3);
   vec += rhs.a, rhs.b, rhs.c;
}

The above function was executed for about 17000 times and it performed (as far as I can see. There was some transformation involved) about 2 magnitudes worse with the call to vector::reserve.

I always was under the impression that reserve can speed up push_back even for small values but this doesn't seem true and I can't find any obvious reasons why it shouldn't be this way. Does reserve prevent the inlining of the function? Is the call to size() too expensive? Does this depend on the platform? I'll try and code up some small benchmark to confirm this in a clean environment.

Compiler: gcc (GCC) 4.4.2 with -g -O2

Answer 1

Use only reserve if you know in advance how much place it will use.

Reserve will need to copy your whole vector...

If you do a push_back and the vector is too small, then it will do a reserve (vec.size()*2).

If you don't know beforehand how big your vector is going to be and if you need random access, consider using std::deque.

Answer 2

You only use reserve() if you know in advance the number of elements. In that case reserve() space for all elements at once.

Otherwise just use push_back() and rely on the default strategy - it will reallocate exponentially and greatly reduce the number of reallocations at a cost of slightly suboptimal memory consumption.

Answer 3

Move the reserve outside of the add.

Each time you invoke "add", you are reserving atleast 3 extra elements. Depending on the implementation of vector, this could be increasing the size of the backing array almost every time you call "add". That is would definately cause the performance difference that you describe.

The correct way to use reserve is something like:

vec.reserve(max*3);
for(int i=0; i<max; i++)
   add(i);

Answer 4

GCC implementation of reserve() will allocate exact number of elements, while push_back() will grow internal buffer exponentially by doubling it, so you are defeating the exponential growth and forcing reallocation/copy on each iteration. Run your test under ltrace or valgrind and see the number of malloc() calls.

Answer 5

If you profiled the code I bet you would see that the += IS very fast, the problem is the reserve is killing you. You should really only use reserve when you have some knowledge of how big the vector will grow to. If you can guess ahead of time then do ONE reserve, otherwise just go with the default push_back.

Answer 6

When std::vector needs to reallocate it grows its allocation size by N*2, where n is its current size. This results in a logarithmic number of reallocs as the vector grows.

If instead the std::vector grew its allocated space by a constant amount, the number of reallocs would grow linearly as the vector grows.

What you've done is essentially cause the vector to grow by a constant amount 3, meaning linear growth. Linear is obviously worse that logarithmic, especially with big numbers.

Generally, the only growth better than logarithmic is constant. That is why the standards committee created the reserve method. If you can avoid all reallocs (constant) you will perform better than the default logarithmic behavior.

That said you may want to consider Herb Sutter's comments about preferring std::deque over vector www.gotw.ca/gotw/054.htm