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

Subject: Re: [boost] [heap][formal review]
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-13 12:54:59

hi andrew,

> - 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,

well, it use use the priority queue inside a scheduler, you may want to modify 
the payload ...

> nor what specific
> requirements that they may have of iteration (heap-order vs.
> tree-order iteration.

the current iterators do not guarantee any order (this is specified in the 
documentation). i am currently working on ordered iterators.

> 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. 

i do not agree with this: compare functions are optional, since std::less is 
used by default. this makes the code more compact:

some_heap<T, some_policy<> >
vs
some_heap<T, std::less<T>, some_policy<> >

in the second version, std::less<T> has to be stated explicitly, although the 
default is used.

however i agree, that the arity of the d_ary_heap could be a positional 
parameter, as it is mandatory.

> Also, the
> b_heap and d_ary heap should also be parameterized over (dynamic
> random access?).

taking a container instead of an allocator will be straight-forward for non-
stable d-ary and b-heaps. for stable heaps a type-correct version needs to be 
specified. for the mutable versions i am not sure whether it is feasible, since 
it will require some knowledge about the internal representation. maybe a 
metafunction will do it, but it is not going to be beautiful ... (stl containers 
cannot be rebound like allocators, can they?)

> - 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.

i find a (structual) equality pretty useless compared to an equivalence. but 
maybe i should simply remove all direct heap comparisons and replace them with 
templated equivalence and lexical comparison functions ...

> - What is your evaluation of the documentation?

... will try to improve ...

> - 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.

the binomial heap is not necessarily obsolete: it is the only mergable data 
structure, provides all heap operations in O(log(N)) worst case. i know, many 
people do not care about the worst case performance, but for those people who 
care the binomial heap should be useful.

> 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.

the last idea was to provide generic free functions with a specialization for 
`efficiently mergable' heaps. however i still do not like the idea of 
introducing a MergablePriorityQueue concept, because it would basically be an 
EfficientlyMergablePriorityQueue concept.

> 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.

depending on the use case it is definitely a requirement ... i have seem many 
workarounds in real-world software, where the stability of non-stable priority 
queues need some ugly workarounds ...

> 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?

well, the bgl heaps are not part of boost's public API: so the first benefit of 
boost.heap over bgl's heaps is that it actually has a documentation and that the 
API will be stable ... nevertheless it heavily relies on bgl's propertymap, 
making the interface not very intuitive. some of the bgl heaps do not have 
allocator support, which makes it impossible to use them when a custom allocator 
has to be used ...

thanks a lot for your review and for managing the review in the first place!

tim