Re: Surprising pop_head performance compared to push_heap
Greg Herlihy wrote:
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.
This would be true if std::priority_queue was implemented in such a
naive way.
In GNU C++ library for example, push() is container's push_back()
followed by push_heap(). The latter shifts the new element up the tree
until it takes a right position. pop() is pop_heap() followed by
container's pop_back(). pop_heap() exchanges the first (topmost)
element with the last one and then shifts the first element down the
tree. The point to note here is that no container's pop_front() is
involved.
I would expect any other C++ library implementation do the same since
this optimal version of algorithm is described in most algorithm
textbooks. http://en.wikipedia.org/wiki/Binary_heap
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]