Boost logo

Boost :

Subject: [boost] [Review:Algorithms] My review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-10-02 19:46:55

Here is my review of the proposed Boost.Algorithm library.

A problem with Boost in the past has been that the contributions have
primarily been larger projects, while smaller things have not been
submitted despite their potential usefulness because of the effort
required to prepare and review them (real or perceived). I therefore
very much welcome the idea of a library to which smaller contributions
can be submitted - though we have yet to find out how such submissions
will be processed, and perhaps some discussion of this would be helpful now.

(I have an implementation of an edit distance / edit script "diff"
algorithm that could probably be contributed.)

Regarding the particular algorithms initially included:

Search algorithms:

These are certainly worth having and the implementations look
satisfactory. Jim Xochellis has made some comments about relaxing the
iterator requirements and this would be worth doing if possible.
Reducing the size of the tables by storing uint8_t for short patterns
(especially on 64-bit systems where 7/8 of the space is currently
wasted) might be worthwhile, though it could conflict with the idea of
relaxing the iterators. Perhaps something can be done with the traits
class to make it easier for the user to tweak this, e.g. passing the
skip-distance type as a defaulted template parameter to the traits
class. Documentation needs to be improved as previously discussed,
especially to guide the user to select the correct algorithm.

Other algorithms i.e. Ordering & clamping:

I have come to the conclusion that these algorithms are too trivial to
be included in Boost.

Anyone who wants one of these functions can easily implement their own
in a "personal utility library" or similar; they are trivial to code
and there are no subtle issues or portability problems. The difficulty
with putting them in Boost is that there are different possibilities
for naming and aspects of the behaviour and there is no one version
that will suit everyone - for example, I would not want to use a
version of clamp that is three times slower than my preferred
implementation. Furthermore, the amount of discussion of a proposal
seems to be in inverse proportion to its complexity! To avoid getting
bogged down in endless discussions of trivia we should set a lower
bound on the complexity of submissions, and these functions are below
that threshold.

> * What is your evaluation of the design?


> * What is your evaluation of the implementation?


> * What is your evaluation of the documentation?

Needs some work, but I'm confident this will happen.

> * What is your evaluation of the potential usefulness of the library?

Search algorithms useful.
Other stuff not sufficiently useful.

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

I did some simple tests and benchmarks with gcc on ARM Linux.
I do recall some "unused argument" warnings that could be suppressed by
removing or commenting the arg name.

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

I've read all of the docs and much of the code, written some test /
benchmark programs, and taken part in discussions.

> * Are you knowledgeable about the problem domain?

Not especially.

In summary, my opinion is that the library should be accepted in part.

Regards, Phil.

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