Re: [boost] [range] fat iterators?

Subject: Re: [boost] [range] fat iterators?
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2013-11-07 14:19:05

On Thursday 07 November 2013 18:29:58 Neil Groves wrote:
> On Thu, Nov 7, 2013 at 5:37 PM, Eric Niebler <eniebler_at_[hidden]> wrote:
> > On 11/7/2013 6:27 PM, Nathan Ridge wrote:
> >>>> The trick, of course, will be keeping intermediate temporary ranges
> >>>> alive long enough to avoid lifetime issues when we chain adaptors and
> >>>> assign the result to a local variable. I think a range library that's
> >>>> sensitive to the value category of range objects and makes copies of
> >>>> rvalue ranges would solve this problem. Thoughts?
> >>> 
> >>> This is definitely something that needs to be added. The challenge is
> >>> merely finding sufficient time to do so.
> >> 
> >> Jeffrey Yaskin posted a candidate design, implemented for
> >> filter_iterator,
> >> here: https://svn.boost.org/trac/boost/ticket/7630
> >> 
> >> What do you think about this design?
> > 
> > It's a step in the right direction, but it still is essentially an
> > iterator_range of filter_iterators. Each filter_iterator is fat; they
> > both store a copy of the filter predicate. Rather, filter_range should
> > store the predicate, and the iterators returned from filter_range should
> > just hold a pointer to the range. That's what I'm suggesting.
> 
> I definitely like the idea. I'd like to measure the impact in some
> use-cases to determine the impact of the worsened locality-of-data. I
> don't believe it is always a performance win. If I get some
> performance numbers I think we can combine the approaches optimally. I
> would have thought that we should, under some scenarios, be using EBO
> for the filter predicate since they are often stateless.
> 
> > And to answer Neil's objection, it necessarily means the iterators can't
> > outlive the range, but IMO it's wrong to assume otherwise. Nobody
> > expects a vector iterator to outlive the vector, after all. It will most
> > certainly be a breaking change, which is why I suggest we ship a C++11
> > range library in parallel with the existing C++98 one.
> 
> I'm not objecting. I'm concerned that using iterators from a range
> after a range has died is a significant design change. It isn't at all
> silly or an unusual use-case. It is commonly required when using
> ranges in your own code and interfacing to a library that only uses
> iterators. With the new requirements I would no longer be able to use
> ranges at all if I wanted to continue using the library. That's a big
> drawback. We can provide a new interface and define that as "wrong"
> but it most certainly isn't wrong at the moment. It's useful. However
> I'm not objecting. I'm pointing out that there are some significant
> drawbacks to consider. I think we can put a new interface together and
> perhaps this is the correct trade-off for a new interface. From my
> perspective the reduction in interoperability with iterator-based
> libraries is a significant drawback. I wonder if we can be clever and
> solve this with something cunning?
> 
> A vector not outliving it's iterators has always been a requirement.
> This requirement had no practical disadvantage to interoperability on
> common use-cases. This is not true for range lifetime. The range has
> often had a shorter lifetime than the container in many practical
> use-cases. It has always been a disposable wrapper. Adding a
> dependency from iterator to range has significant implications. I
> think the idea is worthy of exploration. It's just not completely
> obvious to me that the initial proposal is obviously exactly the way
> forward. I think this proposal is a move toward making the ranges
> primitives in themselves and I wonder if we should be thinking
> slightly more broadly. In particular Andrei's work might be a source
> of inspiration.

I agree with Neil that iterator ranges often have a shorter lifetime than the 
iterators, if it is known that the range refers to an external storage. That 
said, the benefit of Eric's suggestion is also obvious, at least in terms of 
object size and probably performance. So why don't we have both? We already 
have iterator_range that implements the first approach. Why don't we implement 
specialized range types for streams/transforms/filters that follow Eric's 
suggestion?