Std :: vector :: reserve 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 approximately 17,000 times, and it was executed (as far as I can see. There was some kind of transformation), about 2 values ​​are worse with the call vector :: reserve.

I always had the impression that the reserve can speed up push_back even for small values, but this does not seem true, and I can not find any obvious reasons why this should not be so. Does the reserve retain the ability to embed functions? Is calling size () too expensive? Does it depend on the platform? I will try to compile a little test code to confirm this in a clean environment.

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

Answer 1

The implementation of GCC reserve() will allocate the exact number of elements, and push_back() will grow exponentially in the internal buffer, doubling it, so you defeat exponential growth and force redistributing / copying at each iteration. Run the test under ltrace or valgrind and view the number of calls to malloc() .

Answer 2

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

Otherwise, just use push_back() and rely on the default strategy - it will redistribute exponentially and significantly reduce the number of redistributions at the cost of a bit of suboptimal memory.

Answer 3

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

The reserve will have to copy the whole vector ...

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

If you don’t know in advance how big your vector is, and if you need random access, consider using std :: deque.

Answer 4

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

If instead std :: vector increased its allocated space by a constant value, the number of overruns would increase linearly with the growth of the vector.

What you did essentially results in the vector growing at a constant value of 3, which means linear growth. Linear is obviously worse than logarithmic, especially with large numbers.

As a rule, the only growth other than logarithmic is constant. This is why the standards committee created a backup method. If you can avoid all reallocs (constants), you will work better than the default logarithmic behavior.

However, you might think of Herb Sutter's comments that you prefer std :: deque over vector www.gotw.ca/gotw/054.htm

Answer 5

Move reserve out of add.

Each time you call add, you reserve at least 3 additional elements. Depending on the implementation of the vector, this can increase the size of the backup array almost every time you call add. That is, it definitely causes a difference in the performance that you describe.

The correct way to use the reserve is something like:

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

Answer 6

If you have profiled the code, I am sure you will see that + = IS is very fast, the problem is that the reserve is killing you. You should really use the reserve when you have any knowledge of how large the vector will grow. If you guess in advance, then make ONE reserve, otherwise just go with push_back by default.