Re: [boost] [Boost-users] Formal Review: Boost.RangeEx

Subject: Re: [boost] [Boost-users] Formal Review: Boost.RangeEx
From: Neil Groves (neil_at_[hidden])
Date: 2009-02-22 05:37:56

Thank you for taking the time to review Boost.RangeEx.

On Sat, Feb 21, 2009 at 11:50 AM, Christopher Jefferson <
chris_at_[hidden]> wrote:

>
> On 20 Feb 2009, at 12:28, Thorsten Ottosen wrote:
>
>  Dear Developers and Users,
>>
>> It's my pleasure to announce that the review of Neil Groves' RangeEx
>> library starts today and lasts until March 3, 2009.
>>
>>
>> Writing a review
>> ++++++++++++++++
>>
>> If you feel this is an interesting library, then please submit your review
>> to the developer list (preferably), or to the review manager.
>>
>
>
> The following review is based on reading the documentation, looking through
> the source, and mapping some code using an existing custom range library to
> this code.
>
>> Here are some questions you might want to answer in your review:
>>
>> - What is your evaluation of the design?
>>
>
> The library seems to provide a firm foundation to an important area.
>
>
>> - What is your evaluation of the implementation?
>>
>
>
>>
> The code seems very clean and well designed, there do not seem to be any
> surprises.
>
>  - What is your evaluation of the documentation?
>>
>>
> The documentation is simple, but mostly complete. A few small comments:
> 1) I assume the intention is that most functions delegate to the library
> implementations (for example range sort -> std::sort). Explicitly stating if
> this is, or is not, the case would be useful.
> 2) overwrite's documentation could do with being longer (but I will comment
> on this further later).
> 3) The return types of prev_permutation and next_permutation are wrong
> (should be bool, not void)
>

These are all valid points that I would like to address should the library
be accepted. I am particularly grateful for your correct observation that my
documentation contains defects with respect to prev_permutation and
next_permutation.

>
>
>  - What is your evaluation of the potential usefulness of the library?
>>
>
> Initially very useful at just making functions smaller and neater, I
> believe the Range Adaptors (which I have not used) will provide further
> power later.
>
>>
>> - Did you try to use the library? With what compiler? Did you have any
>> problems?
>>
>
> I used g++ 4.3 without problems.
>
> There are a few areas I would like to see fixed, these are very minor
> changes.
>
> 1) There seems some unnecessary inconsistency in return values, for example
> generate returns the range, but fill returns void.
>

I agree. This was the last feature to be added, and it appears that my
intent to be consistent has not carried through to a consistent
implementation. I will address this before release.

> 2) I would like to see partial_sort return the partially sorted range.

This will be done before release.

>
> 3) The *_heap functions should also return the original range. Certainly
> sort_heap should for consistency with sort.

Absolutely.

>
> 4) I have found it useful to have a simple helper function that turns a
> single value into a range with one value.
>

I can add this. I'm struggling to think of a good name. What name did you
chose?

>
> The larger area I would really like to see improvement in is copy /
> overwrite. I believe some bigger improvements, particularly in the area of
> safety, have been missed here.
>

I suspect that my documentation is not adequate to have communicated my
intent. I am of the opinion that copy is rarely the best algorithm to use.
Instead of:

std::vector<int> v;

boost::copy( input | filtered(pred), std::back_inserter(v) );

I prefer the algorithm_ext/push_back.hpp or algorithm_ext/insert.hpp, for
example:

boost::push_back( v, input | filtered );

I prefer the latter because:
1. It is safer since the insertion into the container is inherently safe and
requires no runtime checking.
2. It is typically faster because boost::push_back uses range insertion into
the target container.

I believe that this addresses typical copy-esque safety nicely, but it does
not address the safety of overwrite.
The standard-like boost::copy has an output iterator which will often be
checked in debug builds using the debugging iterator support of your
standard library. With the current interface I cannot think of a way in
which to improve the safety of boost::copy however the function exists
because it could be that one needs to write to an OutputIterator and does
not have an appropriate push_back-able, push_front-able or insert-able
target.

I am interested in other opinions, since this is an ideal time to re-asses
my rationale and address any deficiencies.

The overwrite algorithm has an assertion in debug builds that will fire, in
release builds the behaviour is undefined.
I am of the opinion that this fits the principle of not paying for what you
don't use in release configuration, while providing additional safety in
debug builds for a very small performance cost.

>
> 1) overwrite should state what happens if the output range is overflowed. I
> would like an exception to be thrown.

I respectfully disagree, although I think we can reach a compromise. I
prefer for you to opt-in to something that will incur a performance and
space cost. Therefore I am able to provide an overload with this behaviour,
but prefer the default mechanism of assertions in debug builds. I invite
other opinions on this design decision.

> 2) Why isn't overwrite just an overload of copy?

I assumed that overload resolution would be problematic since the range and
the iterator overloads have the same number of parameters, and the iterator
version has to handle raw pointers etc. I may be under-estimating the
meta-programming techniques of enable_if. I will perform some
experimentation on old compilers and see how well they handle the change.

>
> 3) copy_backward should also have a two-range overload.
>

This sounds like a good idea.

>
> The obvious problem with bounds checking is efficiency. However from my
> experience, it is easy to check random access ranges by a couple of calls to
> 'distance', and for bidirectional and forward ranges, the overhead of
> checking for end of range is very small. If it isn't acceptable to adding
> checking to copy, I would like to see a checked_copy.
>

The check for overwrite doesn't even incur the additional cost of an O(N)
distance for non-random access ranges. Often the range algorithms can check
more cheaply and in most cases I already do so. Since copy uses an
OutputIterator as a target, I know of no way to implement the requested
check. The overwrite function already contains very cheap bounds checking in
debug builds

After evaluating my comments, do you still think a checked_copy is
necessary? I'm not rejecting your ideas, but providing rationale (that
should probably be put into the documentation).

>
> I am happy to contribute code to this area.
>

Thanks, I'm even happier to take a look at it!

>
>
>
>> - How much effort did you put into your evaluation? A glance? A quick -
>> reading? In-depth study?
>>
>
> A quick reading, seeing if it implemented the features in our existing
> library.
>
>>
>> - Are you knowledgeable about the problem domain?
>>
>
> Reasonably.
>
>>
>>
>> And finally, every review should answer this question:
>>
>> - Do you think the library should be accepted as a Boost library?
>>
>>
> Yes

Thank you again for taking the time to review the library.

Best Wishes,
Neil Groves

>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>