Subject: Re: [boost] [Review:Algorithms] My review
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2011-10-02 22:08:17
On Oct 2, 2011, at 4:46 PM, Phil Endecott wrote:
> 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.
This could work as long as the pattern is less < 256 elements long. Hrrm.
> 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.
You're not the first to mention the docs.
I've tried to capture the issues here https://github.com/mclow/Boost.Algorithm/issues/9 - if you don't see what you want there, please add it.
> 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.
> 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.
If you would send the build log my way, I'll make sure they get squashed.
>> * 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.
Thanks for your review, Phil!
Marshall Clow Idio Software <mailto:mclow.lists_at_[hidden]>
A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
-- Yu Suzuki
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk