Re: [boost] [heap][formal review]

Subject: Re: [boost] [heap][formal review]
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-13 10:56:11

My review also...

- What is your evaluation of the design?

The design of the library included a number of features that did not
seem to be adequately motivated by requirements, especially the
ability to iterate over the elements of a heap. It's not obvious that
any applications require or would use this feature, nor what specific
requirements that they may have of iteration (heap-order vs.
tree-order iteration.

I feel that the design (of individual data structures) focuses too
heavily on policy-based design. I think that there are a number of
parameters that should be "positional parameters" rather than
optionally or arbitrarily specified, especially the Compare functions
since they define a fundamental property of the heaps. Also, the
b_heap and d_ary heap should also be parameterized over (dynamic
random access?).

The concept of Mergeable heaps (those supporting efficient merge
operations), at the time of submission, was inadequately addressed.

- What is your evaluation of the implementation?

The implementation is adequate and appears correct (based on
inspection and performance comparisons).

I think that the definition of heap equality and order may be strict
to the point of inefficient. I think it should still be sufficient to
define these operations in terms of object structure rather than the
sequence of values produced.

- What is your evaluation of the documentation?

I think that the documentation could be substantially improved. It
should start with an introduction of a basic Heap concept and describe
the operations push, pop, top, size, and empty. This should be
followed by a table of implementations and their runtime complexity
for different operations.

I feel that the documentation needs to explicitly present the concepts
(as in heap_concepts.hpp) defined in the library. Also, it would be a
good idea to tie the documentation into previously specified concepts
in boost/concept_check.hpp. That would simplify the description of
heaps as EqualityComparable and LessThanComparable, and also Container
(for iterators, size and empty).

The discussion of Mutability needs to be greatly enhanced. It isn't
sufficient to simply show the interfaces for acquiring and updating
handles. A Mutable Heap is really part of a larger data structure that
incorporates a mapping between heaped objects and their handles. You
can't really talk about real applications of Mutable Heaps without
this mapping. This should be given much more attention in the
description.

I also would have liked to have seen a little more historical
perspective in the introduction. Why was the library written? What
libraries motivated the current design?

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

As a collection of basic data structures, the library is potentially
very useful. Not all data structures in the library are equally useful
(binomial heap is largely obsolete), but they are still useful to
others understand their design and implementation.

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

Earlier versions of the library with GCC 4.5. I did not have any
problems that I recall. I did not try to build a performance
comparison as other reviewers did.

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

I spent a good amount of time inspecting the source code and documentation.

- Are you knowledgeable about the problem domain?

Yes.

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

Not in its current state. I feel that the library is over-designed and
needs to be simplified.

The problem is not that the author did not produce a viable design and
implementation of a heap library. I think he did just that, and with
some cleanups to the documentation and minor reworking of some
implementation, this is a fine library.

The problem is that library is comprised of a collection of
fundamental data structures, some of which have been known for 30 or
40 years (if not more). This fact makes acceptance of such a library
much harder than a lesser known or new domain. We all know about data
structures and algorithms (and know them pretty well), and we all know
what these data structures and how they work (or can figure it out).
An ideal library of these data structures would perfectly match our
expectations, whatever those may be. Any deviation from the ideal
would be questionable, and that seems to be how the review played out.

Conceptually, the notions of Mergeability and Mutability are not as
crisply defined as I would have hoped. While it's possible to merge
all heaps, only some are efficiently (i.e., O(lg n)) mergeable. I
think that the approach to Mutability is well-conceived, but not
particularly well communicated. It took me some time before I figured
out its usage and implications.

I'm still not convinced that Stability is an essential requirement, or
that the library's approach to the solution is adequate. I would have
preferred the library not attempt provide such a feature. The same
could be said for iterators.

Another issue is the absence of comparison with the BGL heaps. What
benefits do we get from using your library? What benefits might we get
from the BGL heaps? What are the real performance comparisons?

Despite the fact that I am voting for not including the library, I see
a great deal of value in its continued development and refinement and
would encourage Tim to continue working towards an accepted Heap
library for Boost.

Andrew