Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue

Subject: Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-06-24 21:38:35

On Sun, Jun 24, 2012 at 3:14 PM, Neil Groves <neil_at_[hidden]>wrote:

>
> On 24 Jun 2012, at 19:33, Jeffrey Lee Hellrung, Jr. wrote:
>
> > On Sun, Jun 24, 2012 at 3:52 AM, Neil Groves <neil_at_[hidden]
> >wrote:
>
[...]

> >> As a general idiom the use of lazily adapting upon the invocation of
> >> begin/end would mix two responsibilities. If one considers the
> >> complications involved with managing functor and predicate state being
> >> delayed until the invocation of begin/end it appears to be a
> considerably
> >> more complex solution.
> >
> >
> > I don't understand what you mean here. Surely adapted iterators must
> > likewise manage "functor and predicate state"? Can you elaborate?
> >
>
> Sure it is often the case that the predicate is held by an iterator.
> However users have been free to implement their own range adaptors and I
> have frequently held a predicate once in a range rather than twice in the
> iterators.
>

I'm still not sure what complications you are referring to.

> I do not perceive a compensating advantage for this approach. Of course, I
> >> may well be missing the advantage and invite correction.
> >>
> >
> > As Michael points out, it helps solve the temporary lifetime issue in for
> > loops...and I guess it allows one to return adapted ranges from
> functions?
> >
>
> Yes, I don't dispute that this is part of a working solution. I had not
> realised that this was a fundamental part of the proposed solution. I think
> it is worth exploring alternative solutions since I think none of us are
> entirely happy with the total impact of the change. I'm hoping to reduce
> the overhead when one does not require the move and to reduce the impact
> upon valid client code that may repetitiously call begin()/end().
>
> > And, ultimately, if there's ultimately just one call to begin/end on the
> > final adapted range (the common case?), both the present implementation
> of
> > the Boost.Range adaptors and a lazy implementation would go through the
> > same sequence of iterator constructions, right?
> >
>
> In the common case it does make a small difference, however in the
> worst-cases the impact could be very large on what is perfectly valid
> client code. This does mean I completely reject this solution, but it does
> motivate me to look for alternative solutions. The proposal is better than
> anything I have implemented or got a very clear idea on yet. I'll look at
> building a prototype in the next couple of days.
>

My rebuttal is that:
(a) I understood it to be poor practice to repeatedly call begin/end more
than once (or, in rare situations, a small constant number of times). For
example, range-based-for is defined in terms of a cached end, rather than
repeatedly calling end on the looped range every time the end-test is
evaluated.
(b) Range adaptors can be free to cache begin and end iterators (in
addition to the adapted range), if that would yield noticeably better
performance for more than one begin/end calls (e.g., filtered_range and
dropped_range), but I suspect for most range adaptors, it doesn't make a
difference. Take, for example, a transformed_range. If it's implemented as
a pair of transform_iterators, calling begin/end requires copying the
underlying iterators in addition to the transform function. If
transformed_range is implemented as the underlying range paired with a
function, calling begin/end requires generating the underlying begin/end
iterators and still copying the transformation function. If copying the
underlying iterators is no faster than generating the begin/end iterators
from the underlying range, there should be no difference in performance
between the two implementations of transformed_range. Of course, there's a
big assumption on the relative speed of begin/end versus iterator copying
of the underlying range, but I think it's, again, the common case; it's
something we can aim to guarantee for all provided range adaptors; and if
it's a client range that fails this assumption, we can provide a facility
(oh yeah, that's what iterator_range is for) to explicitly address this.
(c) Further, a transformed_range could actually have *smaller* (in the
sizeof sense) and cheaper-to-copy adapted iterators since the actual
transformation function does not need to be stored by value within the
iterators; it can optionally just store a pointer to the function held in
the transformed_range if the function is too large and/or too expensive to
copy.

Anyways, I might not be changing your mind, but I might be pointing out
some things you hadn't thought of, I don't know :)

- Jeff