headers
Michel Morin | 17 Jun 2012 14:25
Picon

[Range] Range adaptor approach for temporary range lifetime issue

When an rvalue range is adapted in range-based for loop,
the lifetime of the rvalue range ends before the loop body begins.
For example, the following code produces dangling references.

    for (auto x : std::string("Hello world!") | reversed) { /*...*/ }

This is the temporary range lifetime issue.

When I proposed BOOST_FOREACH extension for this issue,
( http://lists.boost.org/Archives/boost/2011/04/180591.php )
a solution with "moving an rvalue range into range adaptors"
was suggested in the thread.

I implemented this approach as a range adaptor (with the aid of
rvalue references and decltype C++11 features):

    for (auto x : std::string("Hello world!") | moved | reversed) { /*...*/ }

When an rvalue range is piped to `moved` adaptor, it returns `moved_range`.
`moved_range` stores the following data:

* Moved rvalue range:
The rvalue range is moved and stored in `moved_range`.

* Applied adaptors:
When range adaptors are applied to`moved_range`, they are
not invoked immediately; they are stored in fusion vector.
The stored adaptors are invoked when `begin` or `end`
member functions of `moved_range` are called.
(To prevent repeated applications of the stored range adaptors,
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 17 Jun 2012 14:33
Picon

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

Michel Morin wrote:
> I implemented this approach as a range adaptor (with the aid of
> rvalue references and decltype C++11 features):
>
>     for (auto x : std::string("Hello world!") | moved | reversed) { /*...*/ }
>
> When an rvalue range is piped to `moved` adaptor, it returns `moved_range`.

Side note:

* There is also a fully automatic approach (i.e. when an rvalue range
is adapted,
`moved_range` is automatically used without piping it to `moved` adaptor).
But this approach incurs unnecessary overhead when passing them to functions,
because function arguments do not have the lifetime issue and we don't need
to use `moved_range`. So I prefer the "manual" approach.

* When the input is an **lvalue** range, `moved` adaptor does nothing
(it just returns the reference) in the current implementation:

    template <typename Range>
    inline Range& operator|(Range& rng, move_forwarder) { return rng; }

So `forwarded` might be better naming.
(I also found that Range Library Proposal (N1871) includes `moved` adaptor
for different purpose; `moved` adaptor in N1781 wraps iterators into
`move_iterator`.)

Regards,
Michel
(Continue reading)

Permalink | Reply |
headers
Dave Abrahams | 17 Jun 2012 21:48
Picon
Picon
Favicon
Gravatar

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


on Sun Jun 17 2012, Michel Morin <mimomorin-AT-gmail.com> wrote:

> Side note:
>
> * There is also a fully automatic approach (i.e. when an rvalue range
> is adapted,
> `moved_range` is automatically used without piping it to `moved` adaptor).
> But this approach incurs unnecessary overhead when passing them to functions,
> because function arguments do not have the lifetime issue and we don't need
> to use `moved_range`. So I prefer the "manual" approach.

Could you illustrate this with an example?  I'd like to understand the
trade-off you're making.

Thanks,

--

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Michel Morin | 18 Jun 2012 00:11
Picon

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

Dave Abrahams wrote:
>> Side note:
>>
>> * There is also a fully automatic approach (i.e. when an rvalue range
>> is adapted,
>> `moved_range` is automatically used without piping it to `moved` adaptor).
>> But this approach incurs unnecessary overhead when passing them to functions,
>> because function arguments do not have the lifetime issue and we don't need
>> to use `moved_range`. So I prefer the "manual" approach.
>
> Could you illustrate this with an example?  I'd like to understand the
> trade-off you're making.

Here is an example of the manual approach:

    template <typename Range> void f(Range&&);

    // No lifetime problem.
    f(std::string("Hello world!") | reversed);

    // `moved` is not necessary.
    f(std::string("Hello world!") | moved | reversed);

In the automatic approach, `std::string("Hello world!") | reversed` returns
`moved_range<std::string, boost::fusion::vector<reverse_forwarder> >`.
So there is unavoidable overhead (i.e. moving a temporary container
into range adaptors) in `f(std::string("Hello world!") | reversed);`.

Regards,
Michel
(Continue reading)

Permalink | Reply |
headers
Dave Abrahams | 22 Jun 2012 20:37
Picon
Picon
Favicon
Gravatar

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


on Sun Jun 17 2012, Michel Morin <mimomorin-AT-gmail.com> wrote:

> Dave Abrahams wrote:
>>> Side note:
>>>
>>> * There is also a fully automatic approach (i.e. when an rvalue range
>>> is adapted,
>>> `moved_range` is automatically used without piping it to `moved` adaptor).
>>> But this approach incurs unnecessary overhead when passing them to functions,
>>> because function arguments do not have the lifetime issue and we don't need
>>> to use `moved_range`. So I prefer the "manual" approach.
>>
>> Could you illustrate this with an example?  I'd like to understand the
>> trade-off you're making.
>
> Here is an example of the manual approach:
>
>     template <typename Range> void f(Range&&);
>
>     // No lifetime problem.
>     f(std::string("Hello world!") | reversed);
>
>     // `moved` is not necessary.
>     f(std::string("Hello world!") | moved | reversed);
>
> In the automatic approach, `std::string("Hello world!") | reversed` returns
> `moved_range<std::string, boost::fusion::vector<reverse_forwarder> >`.

As opposed to what?  You haven't shown me what it returns in the manual approach.
(Continue reading)

Permalink | Reply |
headers
Nathan Ridge | 23 Jun 2012 02:37
Picon
Favicon

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


> > Dave Abrahams wrote:
> >>> Side note:
> >>>
> >>> * There is also a fully automatic approach (i.e. when an rvalue range
> >>> is adapted,
> >>> `moved_range` is automatically used without piping it to `moved` adaptor).
> >>> But this approach incurs unnecessary overhead when passing them to functions,
> >>> because function arguments do not have the lifetime issue and we don't need
> >>> to use `moved_range`. So I prefer the "manual" approach.
> >>
> >> Could you illustrate this with an example?  I'd like to understand the
> >> trade-off you're making.
> >
> > Here is an example of the manual approach:
> >
> > template <typename Range> void f(Range&&);
> >
> > // No lifetime problem.
> > f(std::string("Hello world!") | reversed);
> >
> > // `moved` is not necessary.
> > f(std::string("Hello world!") | moved | reversed);
> >
> > In the automatic approach, `std::string("Hello world!") | reversed` returns
> > `moved_range<std::string, boost::fusion::vector<reverse_forwarder> >`.
>
> As opposed to what? You haven't shown me what it returns in the manual approach.

In the manual approach it would return the same thing it does now:
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 01:04
Picon

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

Nathan Ridge wrote:
>> > Here is an example of the manual approach:
>> >
>> > template <typename Range> void f(Range&&);
>> >
>> > // No lifetime problem.
>> > f(std::string("Hello world!") | reversed);
>> >
>> > // `moved` is not necessary.
>> > f(std::string("Hello world!") | moved | reversed);
>> >
>> > In the automatic approach, `std::string("Hello world!") | reversed` returns
>> > `moved_range<std::string, boost::fusion::vector<reverse_forwarder> >`.
>>
>> As opposed to what? You haven't shown me what it returns in the manual approach.
>
> In the manual approach it would return the same thing it does now:
> reversed_range<std::string>.
>
> Basically, the "automatic approach" is having every adaptor automatically wrap
> the range in a moved_range *just in case* it's used in a context where it needs
> to be moved, and the "manual approach" is having a "moved" adaptor that does the
> wrapping and needs to be used explicitly in such contexts, while leaving other
> adaptors unchanged.
>
> The tradeoff is between moving the container in contexts where it doesn't have
> to be moved (where the temporary range's lifetime is long enough) vs. having
> to remember to add " | moved" in contexts where it does have to be moved.

Exactly right. Thanks for the explanation, Nate!
(Continue reading)

Permalink | Reply |
headers
Thorsten Ottosen | 18 Jun 2012 10:59
Favicon

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

On 17-06-2012 14:33, Michel Morin wrote:
> Michel Morin wrote:
>> I implemented this approach as a range adaptor (with the aid of
>> rvalue references and decltype C++11 features):
>>
>>      for (auto x : std::string("Hello world!") | moved | reversed) { /*...*/ }
>>
>> When an rvalue range is piped to `moved` adaptor, it returns `moved_range`.
>
> Side note:
>
> * There is also a fully automatic approach (i.e. when an rvalue range
> is adapted,
> `moved_range` is automatically used without piping it to `moved` adaptor).
> But this approach incurs unnecessary overhead when passing them to functions,
> because function arguments do not have the lifetime issue and we don't need
> to use `moved_range`.

I'm not sure this is true, that is, that sub-expressions of function 
arguments are guaranteed not to be destroyed before the function ends.

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Michel Morin | 19 Jun 2012 01:20
Picon

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

Thorsten Ottosen wrote:
>> Side note:
>>
>> * There is also a fully automatic approach (i.e. when an rvalue range
>> is adapted,
>> `moved_range` is automatically used without piping it to `moved` adaptor).
>> But this approach incurs unnecessary overhead when passing them to
>> functions,
>> because function arguments do not have the lifetime issue and we don't
>> need
>> to use `moved_range`.
>
>
> I'm not sure this is true, that is, that sub-expressions of function
> arguments are guaranteed not to be destroyed before the function ends.

Temporary objects are valid until the end of the full-expression.
See 12.2 [class.temporary] p3 in the Standard.

Regards,
Michel

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 23 Jun 2012 09:26
Picon

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

On Sun, Jun 17, 2012 at 5:33 AM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Michel Morin wrote:
> > I implemented this approach as a range adaptor (with the aid of
> > rvalue references and decltype C++11 features):
> >
> >     for (auto x : std::string("Hello world!") | moved | reversed) {
> /*...*/ }
> >
> > When an rvalue range is piped to `moved` adaptor, it returns
> `moved_range`.
>
> Side note:
>
[...]

> * When the input is an **lvalue** range, `moved` adaptor does nothing
> (it just returns the reference) in the current implementation:
>
>    template <typename Range>
>    inline Range& operator|(Range& rng, move_forwarder) { return rng; }
>
> So `forwarded` might be better naming.
> (I also found that Range Library Proposal (N1871) includes `moved` adaptor
> for different purpose; `moved` adaptor in N1781 wraps iterators into
> `move_iterator`.)
>

I think moved and move_forwarder are confusing names as I would think they
would take a meaning similar to that in N1871/N1781/whatever (i.e.,
(Continue reading)

Permalink | Reply |
headers
Nathan Ridge | 23 Jun 2012 11:13
Picon
Favicon

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


By the way, my first thought when I encountered this problem
is that C++11  ought to have specified the range-based for loop
in such a way that the lifetime of temporaries in the range
expression is extended for the duration of the loop.

Does anyone share this opinion? Would there be any downsides
to this?

It is also interesting to note that boost::for_each together
with a lambda - a from to which any range-based for loop can
easily be converted - does not suffer from this problem. I think
this corroborates the fact that the range-base for loop is
suboptimally specified in the standard - after all the range-
based for loop was meant to replace things like boost::for_each.

Regards,
Nate 		 	   		  

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 23 Jun 2012 22:22
Picon

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

On Sat, Jun 23, 2012 at 2:13 AM, Nathan Ridge <zeratul976 <at> hotmail.com>wrote:

>
> By the way, my first thought when I encountered this problem
> is that C++11  ought to have specified the range-based for loop
> in such a way that the lifetime of temporaries in the range
> expression is extended for the duration of the loop.
>
> Does anyone share this opinion? Would there be any downsides
> to this?
>

I, too, was thinking along the lines of Dave:

"Well of course there would.  Extending the lifetime of a non-trivial
temporary
beyond what's needed creates inefficiencies (memory pressure, register
pressure, worse locality of reference...)"

So, I'm not sure, either.

> It is also interesting to note that boost::for_each together
> with a lambda - a from to which any range-based for loop can
> easily be converted - does not suffer from this problem. I think
> this corroborates the fact that the range-base for loop is
> suboptimally specified in the standard - after all the range-
> based for loop was meant to replace things like boost::for_each.
>

Maybe, like Dave suggested, there should be a language construct to
(Continue reading)

Permalink | Reply |
headers
Olaf van der Spek | 24 Jun 2012 14:46

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

On Sat, Jun 23, 2012 at 10:22 PM, Jeffrey Lee Hellrung, Jr.
<jeffrey.hellrung <at> gmail.com> wrote:
> On Sat, Jun 23, 2012 at 2:13 AM, Nathan Ridge <zeratul976 <at> hotmail.com>wrote:
>
>>
>> By the way, my first thought when I encountered this problem
>> is that C++11  ought to have specified the range-based for loop
>> in such a way that the lifetime of temporaries in the range
>> expression is extended for the duration of the loop.

Sounds like the simplest and most generic solution.
Does BOOST_FOREACH suffer from the same problem?

Olaf

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 02:09
Picon

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

Jeffrey Lee Hellrung, Jr. wrote:
> I think moved and move_forwarder are confusing names as I would think they
> would take a meaning similar to that in N1871/N1781/whatever (i.e.,
> wrapping the adapted range's iterators in move_iterators). Forwarded is
> better, but my suggestion is something along the lines of "by_value" and
> "by_value_if_rv":

I admit that moved and forwarded are confusing names.
I'm OK with any naming that is concise and clear ;)

> But I think the
> important semantic property about this wrapper is that it effectively
> signals the "range adaptor operator|" to adapt *by value*, and the fact
> that we move to achieve this is just consequence (i.e., most of the time,
> we could copy, it would just be less efficient).

Yep, move is just an optimization.

> Question: Why have the operator| on the moved_range return another
> moved_range, accumulating the adaptors explicitly in a Fusion sequence?

I don't fully understand the following

> Couldn't we just return the usual range adaptor types, with special
> metafunction logic to switch to by-value storage (rather than the default
> reference storage) of the adapted range when its a moved_range or an
> adaptation of a moved_range?

So my answer might not take your point..., but let me try.
(Continue reading)

Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 24 Jun 2012 02:23
Picon

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

On Sat, Jun 23, 2012 at 5:09 PM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
>
[...]

> > Question: Why have the operator| on the moved_range return another
> > moved_range, accumulating the adaptors explicitly in a Fusion sequence?
>
> I don't fully understand the following
>
> > Couldn't we just return the usual range adaptor types, with special
> > metafunction logic to switch to by-value storage (rather than the default
> > reference storage) of the adapted range when its a moved_range or an
> > adaptation of a moved_range?
>
> So my answer might not take your point..., but let me try.
>
> * At each pipe operator, the container should be moved.
> * Iterators might be invalidated by move.
>
> So all the range adaptors should be applied after (or at) the last pipe
> operator. I did this by explicitly accumulating the range adaptors.
>

What I mean is that currently,

r | reversed

returns a reverse_range<R> which stores its adapted range by reference
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 04:20
Picon

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

Jeffrey Lee Hellrung, Jr. wrote:
> What I mean is that currently,
>
> r | reversed
>
> returns a reverse_range<R> which stores its adapted range by reference
> (i.e., R&).

reverse_range<R> does not store the reference; it stores adapted iterators
(i.e. a pair of reverse_iterator<range_iterator<R>::type>).

> What if we introduced a metafunction that dictated what
> reverse_range<R> should store its adapted range by, either R& (most of the
> time) or R (in the case that the adapted range is a directly or indirectly
> a moved_range/by_value_range).

Do you mean reverse_range<R> stores reverse_forwarder and R
for the latter case?

Regards,
Michel

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 24 Jun 2012 10:36
Picon

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

On Sat, Jun 23, 2012 at 7:20 PM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
> > What I mean is that currently,
> >
> > r | reversed
> >
> > returns a reverse_range<R> which stores its adapted range by reference
> > (i.e., R&).
>
> reverse_range<R> does not store the reference; it stores adapted iterators
> (i.e. a pair of reverse_iterator<range_iterator<R>::type>).
>

Oh, my mistake! That was an implicit assumption based on an incomplete read
of the documentation :( In that case, my suggestion would be more radical
relative to the present implementation.

> What if we introduced a metafunction that dictated what
> > reverse_range<R> should store its adapted range by, either R& (most of
> the
> > time) or R (in the case that the adapted range is a directly or
> indirectly
> > a moved_range/by_value_range).
>
> Do you mean reverse_range<R> stores reverse_forwarder and R
> for the latter case?
>

Yes (I think so).
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 11:51
Picon

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

Jeffrey Lee Hellrung, Jr. wrote:
>> > What if we introduced a metafunction that dictated what
>> > reverse_range<R> should store its adapted range by, either R& (most of
>> > the time) or R (in the case that the adapted range is a directly or
>> > indirectly a moved_range/by_value_range).
>>
>> Do you mean reverse_range<R> stores reverse_forwarder and R
>> for the latter case?
>>
>
> Yes (I think so).

Then, compared to the current implementation of reverse_range,
the implementations of your reverse_range and my moved_range
are essentially the same, right?

> Now I'm curious: what are the advantages and disadvantages of implementing
> reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm being
> sloppy here, but based on your above assertion, this is the present
> implementation) versus as a wrapper around an R (held by reference or
> value) directly? In the latter case, for example, reverse_range<R>::begin
> would return reverse_iterator< R::iterator >(boost::end(r)) (where r is the
> wrapped range of type R).

Below, I say boost::begin(r) and boost::end(r) as the underlying iterators.

Your range adaptors are "lazy adaptors":
* Pipe operators does not adapt the underlying iterators in effect.
* The underlying iterators are adapted only when begin/end is called.
And each time begin/end of your range adaptors is called,
(Continue reading)

Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 24 Jun 2012 12:35
Picon

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

On Sun, Jun 24, 2012 at 2:51 AM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
> >> > What if we introduced a metafunction that dictated what
> >> > reverse_range<R> should store its adapted range by, either R& (most of
> >> > the time) or R (in the case that the adapted range is a directly or
> >> > indirectly a moved_range/by_value_range).
> >>
> >> Do you mean reverse_range<R> stores reverse_forwarder and R
> >> for the latter case?
> >>
> >
> > Yes (I think so).
>
> Then, compared to the current implementation of reverse_range,
> the implementations of your reverse_range and my moved_range
> are essentially the same, right?
>

More or less, modulo storage rules. Your moved_range always stores the
underlying range by value; my reverse_range would store by value or by
reference depending on some type property of the underlying range.

> Now I'm curious: what are the advantages and disadvantages of implementing
> > reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm
> being
> > sloppy here, but based on your above assertion, this is the present
> > implementation) versus as a wrapper around an R (held by reference or
> > value) directly? In the latter case, for example, reverse_range<R>::begin
> > would return reverse_iterator< R::iterator >(boost::end(r)) (where r is
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 25 Jun 2012 13:45
Picon

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

Jeffrey Lee Hellrung, Jr. wrote:
> On Sun, Jun 24, 2012 at 2:51 AM, Michel Morin <mimomorin <at> gmail.com> wrote:
>
>> Jeffrey Lee Hellrung, Jr. wrote:
>> >> > What if we introduced a metafunction that dictated what
>> >> > reverse_range<R> should store its adapted range by, either R& (most of
>> >> > the time) or R (in the case that the adapted range is a directly or
>> >> > indirectly a moved_range/by_value_range).
>> >>
>> >> Do you mean reverse_range<R> stores reverse_forwarder and R
>> >> for the latter case?
>> >>
>> >
>> > Yes (I think so).
>>
>> Then, compared to the current implementation of reverse_range,
>> the implementations of your reverse_range and my moved_range
>> are essentially the same, right?
>>
>
> More or less, modulo storage rules. Your moved_range always stores the
> underlying range by value; my reverse_range would store by value or by
> reference depending on some type property of the underlying range.

OK, now I can answer your original question:

> Question: Why have the operator| on the moved_range return another
> moved_range, accumulating the adaptors explicitly in a Fusion sequence?

Accumulating the adaptors is necessary, because I didn't change
(Continue reading)

Permalink | Reply |
headers
Neil Groves | 25 Jun 2012 14:06

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

OK, now I can answer your original question:
>> Question: Why have the operator| on the moved_range return another
>> moved_range, accumulating the adaptors explicitly in a Fusion sequence?
> Accumulating the adaptors is necessary, because I didn't change
> the implementation of the existing Boost.Range's range adaptors.
>
>> Couldn't we just return the usual range adaptor types, with special
>> metafunction logic to switch to by-value storage (rather than the default
>> reference storage) of the adapted range when its a moved_range or an
>> adaptation of a moved_range?
> The lifetime problem can be solved by your range adaptors.
> I chose to implement moved_range, just because adding moved_range
> is easier for me than changing each range adaptor implementation.
> Yeah, I'm lazy :-)

I understand the rationale entirely and normally this is something I 
would push for. In this case I believe we should be able to iterate upon 
your original solution and take advantage of building some optimizations 
into the range adaptors. I think we can then achieve a zero-cost under 
normal conditions implementation with opt-in explicit moving. I'm 
hacking up something to opt-in once and have the opt-in continue 
left-wise through the application of the | operator.

>
> Regards,
> Michel
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 26 Jun 2012 00:57
Picon

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

Neil Groves wrote:
> I understand the rationale entirely and normally this is something I would
> push for. In this case I believe we should be able to iterate upon your
> original solution and take advantage of building some optimizations into the
> range adaptors. I think we can then achieve a zero-cost under normal
> conditions implementation with opt-in explicit moving. I'm hacking up
> something to opt-in once and have the opt-in continue left-wise through the
> application of the | operator.

Hmm, I don't follow what you are trying to implement.
Could you elaborate more? For example, what's the difference between
yours and my implementation (attached in the first post), specifically?
Otherwise, I can't answer your question...

[...]
> Since you are ahead of me, in terms of the amount of work you have done on
> this, do you foresee any issue with my slight changes?

Regards,
Michel

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 25 Jun 2012 18:41
Picon

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

On Mon, Jun 25, 2012 at 4:45 AM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
> > On Sun, Jun 24, 2012 at 2:51 AM, Michel Morin <mimomorin <at> gmail.com>
> wrote:
> >
> >> Jeffrey Lee Hellrung, Jr. wrote:
> >> >> > What if we introduced a metafunction that dictated what
> >> >> > reverse_range<R> should store its adapted range by, either R&
> (most of
> >> >> > the time) or R (in the case that the adapted range is a directly or
> >> >> > indirectly a moved_range/by_value_range).
> >> >>
> >> >> Do you mean reverse_range<R> stores reverse_forwarder and R
> >> >> for the latter case?
> >> >>
> >> >
> >> > Yes (I think so).
> >>
> >> Then, compared to the current implementation of reverse_range,
> >> the implementations of your reverse_range and my moved_range
> >> are essentially the same, right?
> >>
> >
> > More or less, modulo storage rules. Your moved_range always stores the
> > underlying range by value; my reverse_range would store by value or by
> > reference depending on some type property of the underlying range.
>
> OK, now I can answer your original question:
>
(Continue reading)

Permalink | Reply |
headers
Neil Groves | 24 Jun 2012 12:52

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

On 24/06/12 10:51, Michel Morin wrote:

>> Now I'm curious: what are the advantages and disadvantages of implementing
>> reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm being
>> sloppy here, but based on your above assertion, this is the present
>> implementation) versus as a wrapper around an R (held by reference or
>> value) directly? In the latter case, for example, reverse_range<R>::begin
>> would return reverse_iterator< R::iterator >(boost::end(r)) (where r is the
>> wrapped range of type R).
> Below, I say boost::begin(r) and boost::end(r) as the underlying iterators.
>
> Your range adaptors are "lazy adaptors":
> * Pipe operators does not adapt the underlying iterators in effect.
> * The underlying iterators are adapted only when begin/end is called.
> And each time begin/end of your range adaptors is called,
> the underlying iterators needs to be adapted.

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 do not perceive a compensating 
advantage for this approach. Of course, I may well be missing the 
advantage and invite correction.

> But, in some range adaptors, adapting the underlying iterators
> is a bit expensive. For example
> * In filtered_range, adapting the begin iterator can be expensive,
> since it needs to advance the begin iterator to the first "unfiltered"
> iterator.
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 15:18
Picon

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

Neil Groves 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 do not perceive a compensating advantage for this approach. Of
> course, I may well be missing the advantage and invite correction.

But the lazy adaption is necessary to resolve the lifetime problem:

* To resolve the lifetime problem, each pipe operator
should move a temporary container.
* Since moving a container might invalidate iterators,
each range adaptors should be applied to the last moved container
(i.e. the moved container which is moved by the last pipe operator).
* We cannot distinguish the last pipe operator from other pipe operators.

So the only feasible timing for applying range adaptors is when
begin/end is (directly or indirectly) called.

Regards,
Michel

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Neil Groves | 25 Jun 2012 00:08

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


On 24 Jun 2012, at 14:18, Michel Morin wrote:

> Neil Groves 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 do not perceive a compensating advantage for this approach. Of
>> course, I may well be missing the advantage and invite correction.
> 
> But the lazy adaption is necessary to resolve the lifetime problem:
> 
> * To resolve the lifetime problem, each pipe operator
> should move a temporary container.
> * Since moving a container might invalidate iterators,
> each range adaptors should be applied to the last moved container
> (i.e. the moved container which is moved by the last pipe operator).
> * We cannot distinguish the last pipe operator from other pipe operators.
> 
> So the only feasible timing for applying range adaptors is when
> begin/end is (directly or indirectly) called.
> 

I see, I suspected I was missing the advantage. I currently do not have a better proposal and this does solve
the initial problem, but at what cost? Currently the impact of using the range syntax is close to zero,
sometimes in fact better than zero. Is it not possible to make the move operation explicit and the don't
move implicit?

I have not refined this idea, but intend to experiment in the next couple of days. I am wondering if we
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 24 Jun 2012 15:19
Picon

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

Neil Groves wrote:
> FWIW I like the proposed solution but strongly prefer the
> explicit move. My reasoning is that I prefer to apply the zero overhead
> principle,

The overhead in implicit move can be removed by explicitly
applying dont_move, which is described in
    http://thread.gmane.org/gmane.comp.lib.boost.devel/231687/focus=231947

> and that historically choosing implicit has been associated with
> more design errors.

This is a reasonable rationale, I think.

Regards,
Michel

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 24 Jun 2012 20:33
Picon

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

On Sun, Jun 24, 2012 at 3:52 AM, Neil Groves <neil <at> grovescomputing.com>wrote:

> On 24/06/12 10:51, Michel Morin wrote:
>
>  Now I'm curious: what are the advantages and disadvantages of implementing
>>> reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm
>>> being
>>> sloppy here, but based on your above assertion, this is the present
>>> implementation) versus as a wrapper around an R (held by reference or
>>> value) directly? In the latter case, for example, reverse_range<R>::begin
>>> would return reverse_iterator< R::iterator >(boost::end(r)) (where r is
>>> the
>>> wrapped range of type R).
>>>
>> Below, I say boost::begin(r) and boost::end(r) as the underlying
>> iterators.
>>
>> Your range adaptors are "lazy adaptors":
>> * Pipe operators does not adapt the underlying iterators in effect.
>> * The underlying iterators are adapted only when begin/end is called.
>> And each time begin/end of your range adaptors is called,
>> the underlying iterators needs to be adapted.
>>
>
> 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.
(Continue reading)

Permalink | Reply |
headers
Neil Groves | 25 Jun 2012 00:14

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


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> grovescomputing.com>wrote:
> 
>> On 24/06/12 10:51, Michel Morin wrote:
>> 
>> Now I'm curious: what are the advantages and disadvantages of implementing
>>>> reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm
>>>> being
>>>> sloppy here, but based on your above assertion, this is the present
>>>> implementation) versus as a wrapper around an R (held by reference or
>>>> value) directly? In the latter case, for example, reverse_range<R>::begin
>>>> would return reverse_iterator< R::iterator >(boost::end(r)) (where r is
>>>> the
>>>> wrapped range of type R).
>>>> 
>>> Below, I say boost::begin(r) and boost::end(r) as the underlying
>>> iterators.
>>> 
>>> Your range adaptors are "lazy adaptors":
>>> * Pipe operators does not adapt the underlying iterators in effect.
>>> * The underlying iterators are adapted only when begin/end is called.
>>> And each time begin/end of your range adaptors is called,
>>> the underlying iterators needs to be adapted.
>>> 
>> 
>> 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
(Continue reading)

Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 25 Jun 2012 03:38
Picon

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

On Sun, Jun 24, 2012 at 3:14 PM, Neil Groves <neil <at> grovescomputing.com>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> grovescomputing.com
> >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.
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 27 Jun 2012 02:12
Picon

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

Jeffrey Lee Hellrung, Jr. wrote:
> My rebuttal is that:
[...]
> (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.
[...]

I don't know what the consequence of the following fact is,
but it's worth noting:

Repeatedly adapted ranges might have **very** large size.
For example, on Mac OS X 10.7 with gcc-4.7,

    std::vector<int> v;
(Continue reading)

Permalink | Reply |
headers
Jeffrey Lee Hellrung, Jr. | 27 Jun 2012 02:22
Picon

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

On Tue, Jun 26, 2012 at 5:12 PM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Jeffrey Lee Hellrung, Jr. wrote:
> > My rebuttal is that:
> [...]
> > (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.
> [...]
>
> I don't know what the consequence of the following fact is,
> but it's worth noting:
>
(Continue reading)

Permalink | Reply |
headers
Dave Abrahams | 28 Jun 2012 13:57
Picon
Picon
Favicon
Gravatar

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


on Sun Jun 24 2012, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:

> 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?

The lazy case is actually able to perform some "optimizations" like
eliminating double-reverses.  It's not at all clear that these tricks
would improve performance in reality, though.

--

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Thorsten Ottosen | 29 Jun 2012 13:37
Favicon

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

On 28-06-2012 13:57, Dave Abrahams wrote:
>
> on Sun Jun 24 2012, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:
>
>> 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?
>
> The lazy case is actually able to perform some "optimizations" like
> eliminating double-reverses.  It's not at all clear that these tricks
> would improve performance in reality, though.

Well, I think we would be going too far if we tried to do that in the 
library. There is a difference between optimizing common use-cases and,
ahem, strange uses.

That said, with some effort, it might be possible to join certain 
adaptors into one compound adaptor. For example

   range | transformed( &Trans ) | filtered( &When )

may become one iterator type, hence simplyfying the task for the compiler.

Also, I'm inclined to think "lazy" is best for other reasons: it allows 
the cpu to work on one iterator object at a time, instead of 
interleaving construction of the two iterators all the time.
I guess it would be a problem if the iterators are not cached, but 
recomputed; probably not a problem in practice.
(Continue reading)

Permalink | Reply |
headers
Neil Groves | 4 Jul 2012 12:39

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

On 29/06/12 12:37, Thorsten Ottosen wrote:
> On 28-06-2012 13:57, Dave Abrahams wrote:
>>
>> on Sun Jun 24 2012, "Jeffrey Lee Hellrung, Jr." 
>> <jeffrey.hellrung-AT-gmail.com> wrote:
>>
>>> 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?
>>
>> The lazy case is actually able to perform some "optimizations" like
>> eliminating double-reverses.  It's not at all clear that these tricks
>> would improve performance in reality, though.
>
> Well, I think we would be going too far if we tried to do that in the 
> library. There is a difference between optimizing common use-cases and,
> ahem, strange uses.
>
> That said, with some effort, it might be possible to join certain 
> adaptors into one compound adaptor. For example
>
>   range | transformed( &Trans ) | filtered( &When )
>
> may become one iterator type, hence simplyfying the task for the 
> compiler.
>
I agree that there is almost certainly room for improvement in this area
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 6 Jul 2012 13:31
Picon

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

Neil Groves wrote:
> If we are pushing the laziness to the extreme whereby the begin()/end()
> calls create the iterators we are also changing the exception semantics be
> delaying throws. I therefore tend to think that we would be better having
> lazy range adaption by the adaptors creating a class convertible to a range
> that captures and hence triggers the adaptor evaluation via implicit
> conversion. I proposed this on the list a few weeks ago. I see no reason to
> break backward compatibility by loosening the performance guarantees of
> begin()/end().

Ah, now I understand what you're trying to do.
You're controlling the timing of range adaptor invocation
for lazy implementation, right?

For example, in the following code with your proposed implementation,

    reversed_range<...> rng = xxx | reversed;

reversed range adaptor is invoked when lazy adaptor `xxx | reversed`
is implicitly converted to reversed_range<xxx> `rng`,
instead of when begin/end to `rng` is called.

This solution does not work for auto-typed variables and function templates,
since no implicit conversion is applied in those cases.
So I think it would be better to provide a member function for
explicit invocation of range adaptors

    auto rng = (xxx | reversed).eval();

or a range adaptor
(Continue reading)

Permalink | Reply |
headers
Michel Morin | 17 Jun 2012 14:59
Picon

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

For compilers without the support of C++11 range-based for,
please use the attached codes in this mail.

Two files are attached.

* foreach.hpp
The current implementation of `BOOST_FOREACH` does not
use rvalue references to bind temporary ranges.
`BOOST_FOREACH` in this file implements such functionality
to deal with move-only types.

* moved.cpp
Includes the above foreach.hpp by`#include "foreach.hpp"` and
replaces C++11 range-based for with `BOOST_FOREACH`.

Regards,
Michel
Attachment (moved.zip): application/zip, 10 KiB

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Neil Groves | 17 Jun 2012 16:23

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

On Sun, Jun 17, 2012 at 1:59 PM, Michel Morin <mimomorin <at> gmail.com> wrote:

> Two files are attached.
>
> Thank you ever so much for taking the time to implement your suggestion. I
will make sure I review this code sometime this week. I'm sure that if
there are no breaking changes and no gotchas that we can get this into the
trunk soon.

 Regards,

> Michel
>
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Michel Morin | 18 Jun 2012 12:05
Picon

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

Neil Groves wrote:
> Thank you ever so much for taking the time to implement your suggestion.
> I will make sure I review this code sometime this week. I'm sure that if
> there are no breaking changes and no gotchas that we can get this into the
> trunk soon.

Thanks for your response, Neil.

[Some gotchas in the implementation]:
* C++11 features (rvalue references and decltype) are used.

* When applying range adaptors in `moved_range`,
a moved container is evaluated as **const lvalue reference**.
(This is because the implementation uses `boost::fusion::accumulate`
to apply range adaptors.)

* The pipe operator of an rvalue `moved_range` has higher priority than
the pipe operators for all other range adaptors (e.g. `reverse_forwarder`)
in overload resolution:

    template <typename Adaptor>
    moved_range<Container, typename meta::push_back<Adaptors, Adaptor>::type>
    operator|(moved_range<Container, Adaptors>&& rng, Adaptor const& adpt);

    template<typename Range>
    reversed_range<Range>
    operator|(Range& rng, reverse_forwarder);

So, when adding rvalue overloading to range adaptors in the future,
we need to avoid ambiguity on overload resolution for the pipe operator.
(Continue reading)

Permalink | Reply |

Gmane