[boost] [review] [heap] Summary

Subject: [boost] [review] [heap] Summary
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-18 10:49:20

The formal review of Tim Blechmann's Heap library has concluded.

Only four votes were cast, although more people commented on issues
either on the mailing list or though the Code Collaborator tool.
However, from the comments received, the review identified no
fundamental problems in the design or implementation of the library
that would entail rejection. A such,

        the Boost.Heap library is ACCEPTED into Boost

Votes for the library were cast by:
Phil Endecott
Daniel Russel

Votes against:
Thomas Klimpel (provisionally)
Andrew Sutton

Other comments received during the course of the review were generally
positive, with a number of technical issues identified that need to to
be addressed. The final version of the library can be fully accepted
once Tim has addressed the technical issues identified during the
review.

Below is a summary of technical concerns.

- The pairing heap has a known issue, regarding stack overflows,
making it potentially unusable for production code. If the recursion
issue can't be adequately solved, then the data structure should carry
a much stronger warning  label (i.e., put it in an experimental
directory).

- The performance of b_heap vs. d_ary_heap vs. priority_queue needs to
be better characterized. Under what circumstances does one outperform
the other. If no convincing scenario can be found where b_heap
outperforms the others, then it should also be placed in an
experimental directory.

- The heap concepts need to be revisited as per comments on the review
tool. The concepts should also describe semantics of the operations,
not just the interfaces.

- There were several comments on the implementation of heap stability.
Three alternatives were identified: “naturally stable” heaps (of which
no examples were given), the current counter based approach, and a
chaining approach. No consensus on the best implementation strategy.
Although the counter-based approach is probably adequate for most
applications, it is not universally desirable. A more thorough
investigation of alternative strategies is encouraged. It would be
acceptable to document the investigation in a “Future Work” section of
the library documentations (with any experiments also housed in the
library).

- The notion of Mergeable heaps needs to be better addressed, at least
to differentiate between heaps that merge in O(n) or slower time and
those that can merge in O(lg n) time. The proposed solution is to
write merge as a general heap algorithm and specialize it for
Mergeable heaps by calling the member function merge. Also, merge
should be destructive, so merge and clear should not be needed.

- The documentation must be substantially improved with respect to the
overall design of heap data structures (i.e., concepts), especially
mutable heaps and best practices. It also needs to provide both
theoretical and performance comparisons for the different heaps.

- Include documentation of the benchmarking tool in the documentation.
It could be instructive for users to evaluate different heap
implementations on their host or target architectures.

- Document the complexity of == and < for heaps.

- Address the comments and issues in the Review Tool.

There were other recommendations that should be considered in the long
term for the library.

- Thorsten Ottosen suggest making b_heap and d_ary_heap container
adaptors along the lines of std::stack, std::queue, and
std::priority_queue, allowing parameterization over (e.g., stack-based
container). Subsequent discussion indicates that there are some
impracticalities in doing so, namely that it could invalidate other
policies (e.g., stability).

- Phil Endecott suggested rewriting some heaps (b_heap and d_ary_heap)
in terms of more general algorithms operating on a (Random Access)
Range in order to support the formulation of heap structures on other
memory structures. Doing this would also help support the definition
of heaps that satisfied Thorsten's request.

I strongly recommend investigating Phil's suggestion, but this is not
a barrier to acceptance. This feature could be added in future
revisions of the library.

I'd like to thank the community members who took the time to review
Tim's work and especially those that submitted formal reviews. I'd
also like to thank Tim (again) for his contributions and patiently
answering our questions and addressing our comments.

Andrew