[boost] [Review:Algorithms] My review

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?

Straightforward.

> * What is your evaluation of the implementation?

Satisfactory.

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