Re: Surprising pop_head performance compared to push_heap
Fernando Cacciola wrote:
Hi people,
I have some piece of code that takes way too much time to do what it
does (which is irrelevant here) and while searching for the cause I
stumbled upon the following surprising results:
The code uses a priority queue and so have lines of the form:
PQ.push(item);
and
Item item = PQ.top() ; PQ.pop();
So I added some manual profiling code around those two operations:
Timer t ; t.start();
PQ.push(item)
t.stop(); total_insert_time += t.time();
Timer t ; t.start();
Item item = PQ.top() ; PQ.pop();
t.stop(); total_remove_time += t.time();
During the particularly long run, about 150000 items are inserted in
total and each and every one of them removed. (the main loop finishes
when the PQ is empty)
But here is the puzzing (to me at least) result:
total_insert_time : 34 seconds
total_remove_time: 240 seconds
The results should not be puzzling at all. These timings merely confirm
that that it is faster to add items at the back of an array (actually,
a std::vector in this case) than it is to remove items from the front
(or conversely, that it is faster to remove items from the back of a
std::vector than to add items at its front).
The reason for the difference should be clear: adding (or "pushing")
items at the back of the vector (serving here as the priority queue) is
a constant time operation; whereas removing even just one item from the
front necessitates shifting all of the remaining items forward to fill
the space just vacated. Worse, removing items from the front requires
more and more work as the number of items in the queue increases.
One obvious way to avoid this kind of slowdown would be to use a
different kind of container to implement a priority queue. Ideally this
replacement container would not favor either the front or back when it
came to inserting or removing items. In other words, either operation
would take the same amount of time at either end of the container.
Fortunately, the Standard anticipated that a container with exactly
that property would be useful - which is why a std::deque is a standard
C++ class of container - and the one that will solve this performance
issue.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]