Boost logo

Boost :

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?


Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at