[boost] [Heaps] Review

Subject: [boost] [Heaps] Review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-13 11:01:52

Dear All,

Here is my review of the proposed Heaps library.

     What is your evaluation of the design?

Satisfactory.  If possible, I think it would be good to provide the new 
heaps with interfaces as close as possible to the std:: heap, i.e. as 
algorithms (push, pop, etc.) over arbitrary containers or ranges, as 
well as the current containers.  This would allow:
(a) Existing code using std::push|pop_heap could be converted to use 
one of the alternative designs with just some search-and-replace;
(b) Portions of a container could be managed as heaps, with other 
portions unordered, sorted, etc.;
(c) Heaps over raw memory (e.g. memory-mapped files) would be possible.
(I posted this suggestion in an email a few days ago but haven't had 
any replies.  It is possible that there is something that I have 
overlooked that makes this impractical.)

     What is your evaluation of the implementation?

I found one bug, which Tim was able to fix quickly.  Although I've not 
looked in detail at the code, what I have seen appears satisfactory.  
It does seem to lack either comments or much else in the way of 
internals-documentation, though.

I am concerned about the performance of the B Heap.  It seems to 
execute twice as many instructions as a "traditional" heap, and it's 
hard to concoct a situation where its improved memory access pattern 
makes up for that.  Some more investigation of this is needed.  My past 
exposure to "B" structures has mainly seen them used for on-disk data.  
How do cache, main memory, and disk access times compare these days?  
It would be great to see some real-application benchmarking of this.

     What is your evaluation of the documentation?

It needs some expansion, but it's on the right lines.  It suffers, from 
too many, commas.  A table indicating the features and complexity of 
those features for each heap would be useful at the start.

     What is your evaluation of the potential usefulness of the library?

Personally I currently have no need for those heaps with improved merge 
performance, and the B-heap doesn't help me because it is slower than 
the std:: heap.  Despite this, I believe it is useful enough to warrant 
inclusion in Boost.

     Did you try to use the library? With what compiler? Did you have 
any problems?

Yes, with gcc 4.* on Linux; one bug which Tim says has been fixed.

     How much effort did you put into your evaluation? A glance? A
     quick reading? In-depth study?

A few hours.

     Are you knowledgeable about the problem domain?

Not especially, though I have used std heaps in a couple of applications.

And finally, every review should answer this question:

     Do you think the library should be accepted as a Boost library?

Yes.

Regards,  Phil.