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

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 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.