473,836 Members | 1,586 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Unexpected pop_head performance compared to push_heap

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:



Item item = PQ.top() ; PQ.pop();

So I added some manual profiling code around those two operations:

Timer t ; t.start();
t.stop(); total_insert_ti me += t.time();

Timer t ; t.start();
Item item = PQ.top() ; PQ.pop();
t.stop(); total_remove_ti me += 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_ti me : 34 seconds
total_remove_ti me: 240 seconds

And this ratio is more or less consistent, not only among several runs
of the same algorithm with the same input in my mahcine but among
several runs on different platforms with different STL implementations
and machines.

FWIW, in all the different paltforms the code is compiled with the
default options, which in many cases means a range checked STL.

What I found very odd here is that pop_heap takes 8-10 times longer
than push_heap in an escenario where total the number of items are
balanced (the PQ is consumed until it's empty)

And there's more... it turns out that 95% of the items are insterted in
a initialization phase before the first is ever removed..... after the
first remove, a run of items may be inserted for each remove, but only
5% of the total is inserted in this phase.
I tried putting all the items from the initialization phase (95% of the
total) in a vector, with storage reserved in advance for 200000 items
to avoid additional allocations, then constructing the PQ with that
sequence (which calls make_heap up front), but the results are roughly
the same... removing all of the items takes 8-10 times longer than
inserting them.

Is this expected?
What can I do?

Given that 95% of the items are inserted up front, could using a set<>
and implementing the pop_heap() as a linear search for the first
unflagged item be better? (flagging items instead of removing them to
avoid tree rebalancing)... or maybe using a manually sorted list so
that removal becomes O(1) even if inserting is O(n.log n) instead of
O(log n) as in the heap?


Fernando Cacciola

Jun 22 '06 #1
0 1281

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

by: Marc H. | last post by:
Hello, I recently converted one of my perl scripts to python. What the script does is simply search a lot of big mail files (~40MB) to retrieve specific emails. I simply converted the script line by line to python, keeping the algorithms & functions as they were in perl (no optimization). The purpose was mainly to learn python and see the differences with perl. Now, once the converted script was finished, I was amazed to find that
by: Kevin C | last post by:
Quick Question: StringBuilder is obviously more efficient dealing with string concatenations than the old '+=' method... however, in dealing with relatively large string concatenations (ie, 20-30k), what are the performance differences (if any with something as trivial as this) between initializing a new instance of StringBuilder with a specified capacity vs. initializing a new instance without... (the final length is not fixed) ie,
by: Kenneth Massey | last post by:
I was noticing significantly worse performance in some of my C++ codes compiled with gcc 3.4.3 as compared to gcc 3.3.4. I have boiled it down into one relatively short code that illustrates. It seems to be an issue of excessive cache misses in certain pointer lookup operations in gcc 3.4.3 binaries. BTW, are there any tools to actually count cache misses? If anyone has a few minutes to compile and run the following code, I would be...
by: jd | last post by:
I have an xsl file to generate xml in to an html file. The size of the xsl is 300kb and size of the xml is 47 kb (the size of xml is variable). I am using VB.net to convert the xml file into an html file. The vb.net module peforms following task: load the xml file in XMLDocument object ( I can't use XpathDocument object) load the xsl file in XSLTransform object perform the transformation.
by: smoody | last post by:
I have an ASP.NET application which uses a .NET Web Service as a wrapper to a COM+ DLL. Performance for a single user is very good. However, I have noticed that when multiple requests are made simultaneously to the page, it takes (2 x number of users) longer to serve the page. Interestingly enough, all users get the page at the same time. I have traced the routines in the application and the web service, and the actual getdata...
by: Greg | last post by:
1. What work is in progress to bring C# performance closer to C++/CLI? Can we expect C# to equal C++/CLI performance? If so when? 2. Also what work is in progress to improve MSIL/CLR/JIT performance in general? As relases to the Framework e.g. 2.1, 2.2,.. are made do these include performance imporovements? -- Greg McPherran www.McPherran.com
by: toton | last post by:
Hi, I want a few of my class to overload from a base class, where the base class contains common functionality. This is to avoid repetition of code, and may be reducing amount of code in binary, not to get polymorphic behavior. None of them has virtual methods, and are self contained (no destructor at all) thus do not have a chance to have memory error. Thus the derived classes has additional functionality, not additional data.
by: Jim Michaels | last post by:
I have a 638 line glob of PHP code & HTML that won't run. I get "PHP Parse error: syntax error, unexpected '}' in quiz\\quiz.php on line 594". I wrote a brace checker that checks perens, square brackets, and curly braces for mismatches & opens and it checks out perfect. so I don't know what it is about the curly brace error. it's false. anybody have a clue as to what the real error might be? the code looks pristine to me. ...
by: George2 | last post by:
Hello everyone, I want to know why virtual function's footprint and performance is compared with normal function call. Here is my analysis, please review whether I am correct. Thanks. 1. foorprint
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.