Boost logo

Boost :

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




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk