I have been running a c++ program for scientific purpose and I am now looking at optimizing it.
The bottleneck seems to be a function where I need to stack pairs of integers. Their number is impossible to know from the start, and I have been using a std::vector
of a custom struct holding two ints
. Is there a more efficient data container for repetitively adding elements at the end? Should I use it with two ints
instead of a pair or custom structure?
edit:
After timing and profiling my program, I can say that, for my use, vector
is slightly faster than deque
(by only 3%). My layman conclusion is that the CPU makes a good use of the contiguity of the data. Optimization is more than ever a sorcery for me! And to those it may help: I actually improved significantly my running time by switching from the STL C++ 11 random number generator to the BOOST one.
The cost of the logarithmic number of reallocations you have to do is arguably irrelevant. However, you may consider using a
std::deque
that guaranteesO(1)
insertion at the front and at the end. You would lose contiguity, but some cache friendliness is kept. Adeque
is usually a decent trade-off, especially if you need to pop from the front.Consider also estimating the number of elements the vector will store, and using
reserve
. Be careful however not to waste too much memory or you'll get the opposite effect.