On 07-11-2013 15:52, Eric Niebler wrote:

On 11/7/2013 3:31 PM, Neil Groves wrote:

...

On Thu, Nov 7, 2013 at 2:20 PM, Eric Niebler wrote:

...

I wrote an article describing the "fat" std::istream_iterator and how it can be slimmed down by giving it an owning istream_range[1]. I see there

[snip] Historical note: Some years ago, one of the adaptors I wrote returned a range object where the iterators kept a reference to the range. I can't remember if Neil replaced it or if its still in use. It had obvious life-time issues if the iterator was extracted from a locally constructed range, but I thought 99.9% of all use would be in loops and with range adapters. So, as others have pointed out, do we want a design where iterators can't outlive the range, even when the range is constructed from, say, a vector that is kept alive?

Forget streams. Think of something like this:

rng | filtered([=](xxx y){ I reference local vars; })

Now you have a pair of filter_iterators, each of which has a copy of the lambda, and each lambda has a copy of all the local variables the lambda captures. Copying those iterators makes a copy of all the locals captured by the lambda. Am I wrong? That's pretty bad.

It seems bad. FWIW, I'd be happy with a range library that required the range to be kept alive as long as the iterator. Remark on your article: did you benchmark your new design in terms of speed and size? regards -Thorsten

On 07-11-2013 22:33, Eric Niebler wrote:

On 11/7/2013 8:29 PM, Thorsten Ottosen wrote:

...

Remark on your article: did you benchmark your new design in terms of speed and size?

I didn't measure performance, I admit. Non-locality is a valid concern. I have no doubt that it's possible to construct cases where one implementation is faster than the other. Lies, damn lies, and benchmarks, you know.

Sometimes. Genereated assembler would be another way to measure. Let's assume a range that generates the iterators in your fashion. Then in template< class Rng > void foo_algo( Rng& rng ) { std::foo_algo( begin(rng), end(end) ); } how much can we expect the optimizer? Both iterators will store a reference to the range, and then might have some additional information. Can the compiler see that the stored reference to the range is the same and avoid one of them? If not, may we should think about how to inprove the language to make this happen? -Thorsten

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. 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. -- Eric Niebler Boost.org http://www.boost.org

On Thursday 07 November 2013 18:29:58 Neil Groves wrote:

On Thu, Nov 7, 2013 at 5:37 PM, Eric Niebler 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?

On 2013-11-07 21:49, Jonathan Wakely wrote:

On 7 November 2013 17:27, Nathan Ridge wrote:

...

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?

That's beautiful!

My solution to the temporary range problem is simpler, but as mentioned in Jeffrey's patch to the docs, for ranges that store an iterator pair it wastes the space of a reference member in the lvalue case, and doesn't vanish to nothing in C++03 mode:

template<typename R> class adaptor { R r; // R is a range or an lvalue-reference-to-range

public: explicit adaptor(R&& r) : r(std::forward<R>(r)) { }

// ... };

template<typename R> adaptor<R> adapted(R&& r) { return adaptor<R>{std::forward<R>(r)}; }

I generally make use of this solution (i.e. in general and for things other than ranges), but after trying it for ranges I balked and switched to storing decayed copies. The reason is that a range abstraction provides an 'indirection' at least in a moral sense, if not in actuality. So you get aliasing issues: some_range r; auto a = adapted(r); auto b = adapted(r); // consume a: for(auto&& item: a); // now r has been touched! // likely to do the wrong thing for(auto&& item: b); While there is the option of doing adapted(decay(r)) to express 'construct an adapted range from r that stores its own copy' (similarly to uses of ref and reference_wrapper in C++03 code, although inverted), my concern is that aliasing is not the most useful default for ranges. (Strictly from a semantics point of view, I've never checked the impact on the generated code.)

On 11/8/2013 4:59 AM, TONGARI J wrote:

2013/11/7 Eric Niebler

...

I wrote an article describing the "fat" std::istream_iterator and how it can be slimmed down by giving it an owning istream_range[1]. I see there already is an istream_range in Boost.Range, but it suffers from the fat-iterator problem I describe there. Is there a compelling reason why the implementation of boost::istream_range shouldn't be changed to be more like the one I describe? Also, as a commented pointed out, the same problem exists for the filtered range and the transformed range, too.

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?

Is it time for Boost.Range 3.0?

[1]: http://ericniebler.com/2013/11/07/input-iterators-vs-input-ranges

That reminds me of the question I asked years ago (no one answered):

http://lists.boost.org/boost-users/2011/08/70121.php

That's an interesting example, thanks. I hadn't considered the problem of iterator invalidation.

Surely all approaches have tradeoffs...

About the lifetime problem, could it be solved(?) with the approach Fusion used? (i.e. the distinction between 'view' & 'sequence').

I feel that the Fusion approach is a stop-gap, since when Fusion was designed there were no rvalue references. Fusion::is_view is an imperfect heuristic for determining when to store a copy. I think rval refs makes the distinction between views and sequences moot.

I'm willing to have a reusable range, rather than a disposable one. The problem of a disposable one also described in my question.

And I wonder, if we could have 2-phase construction. phase 1: A lazy range builder w/o begin/end phase 2: A range w/ begin/end and probably do some work at construction, as Eric suggested.

And there have to be a trait like:

template<class Range> struct range_type { typedef Range& type; };

And specialized for those have 2 phases.

To implement the algorithms:

template<class Range> void some_algo(Range const& rng, ...) { typename range_type<Range const>::type r(rng); some_algo(begin(r), end(r), ...); }

For range adaptors, they also store phase 1 object, and make the underlying phase 2 object on the fly.

What do you think?

I'm not sure what problem you're solving with 2-phase construction of ranges. Can you clarify? -- Eric Niebler Boost.org http://www.boost.org

On 11/12/2013 8:21 AM, Evgeny Panasyuk wrote:

12.11.2013 19:41, Eric Niebler:

...

I've now built a filter_range, transform_range, and an istream_range in this vein. Initial results are looking promising, but I haven't benchmarked performance, yet. A commenter on my blog claims to have benchmarked perf of istream_range, with good results, which is encouraging.

While new "slim" istream_range is faster than version with "fat" iterators, it is still not the fastest possible. In particular, it does two comparisons per cycle iteration: one is "!rng_->next()", and another is comparison of iterators, like "it != last". <snip>

The commenter on my blog claims this extra check is optimized away by a smart compiler like gcc. He says[^1]:

Your istream_range solution is pretty awesome. I tested the generated assembly on gcc.godbolt.org and compared it to plain old while() looping and D-style iteration http://coliru.stacked-crooked.com/a/d22192e264e59715

Incredibly, the conditional nulling-out inside your iterator increment() appears to be optimized away altogether. It’s very surprising that the compiler can prove that a nullptr value will be compared to the other nullptr value lurking inside the end() iterator. Essentially the same assembly is generated for all 3 approaches.

It remains to be seen how well compilers can optimized several stacked range adapters, but at least in the simple cases we don't have to accept compromise. [^1]: http://ericniebler.com/2013/11/07/input-iterators-vs-input-ranges/#comment-1... -- Eric Niebler Boost.org http://www.boost.org

On 11/12/2013 10:44 AM, Daniel James wrote:

On 12 November 2013 17:13, Eric Niebler wrote:

...

On 11/12/2013 8:21 AM, Evgeny Panasyuk wrote:

...

12.11.2013 19:41, Eric Niebler:

...

I've now built a filter_range, transform_range, and an istream_range in this vein. Initial results are looking promising, but I haven't benchmarked performance, yet. A commenter on my blog claims to have benchmarked perf of istream_range, with good results, which is encouraging.

While new "slim" istream_range is faster than version with "fat" iterators, it is still not the fastest possible. In particular, it does two comparisons per cycle iteration: one is "!rng_->next()", and another is comparison of iterators, like "it != last". <snip>

The commenter on my blog claims this extra check is optimized away by a smart compiler like gcc. He says[^1]:

Regardless of efficiency, a range adaptor could make implementing input and forward ranges much easier.

Agreed. I've implemented such an adaptor, but I'm not yet happy with it so I haven't committed it yet. I think we can take a page out of Boost.Iterator's book and have range_adaptor and range_facade. With some thought, we should have a good answer for the folks who just want to write something like the D range interface. -- Eric Niebler Boost.org http://www.boost.org

On 12-11-2013 16:41, Eric Niebler wrote:

I've now built a filter_range, transform_range, and an istream_range in this vein. Initial results are looking promising, but I haven't benchmarked performance, yet. A commenter on my blog claims to have benchmarked perf of istream_range, with good results, which is encouraging.

If anybody wants to take a peek, you can find the code here:

https://github.com/ericniebler/range-v3

I'm making no effort to maintain source compatibility, going instead with the design that seems right to me for C++11.

Good. I totally agree that r-value refs change things completely. Some small comments (applies for transform_range as well): A. For filter_range, you should inherit from the predicate if possible to enable EBO. I don't know if lambdas complicate this? B. For the constructor filter_range(Rng && rng, Pred pred) then maybe it would be beneficial that empty predicates are constructed via filter_range(Rng && rng) ? I guess it needs benchmarking though, but the compiler will have to elide a series of moves vs. default construct an empty class. C. I can't quite figure out your use of filterer::filterer1. Do you really have to store the predicate here also? -Thorsten

On 12-11-2013 18:19, Eric Niebler wrote:

On 11/12/2013 8:38 AM, Thorsten Ottosen wrote:

...

On 12-11-2013 16:41, Eric Niebler wrote:

I should use EBO, but that's not the right place for it. It adds a bunch of associated namespaces to the filter_range type. Rather, the predicate and the adapted range should be in a compressed pair. I have this working locally already. The space savings are worth it: a filtered, filtered, transformed range goes from 24 bytes to 16.

Nice.

So yes, it needs to store the pred. One of my breaking changes is to allow the "filter" name to be reused such that these two are equivalent:

vec | filter(pred) filter(vec, pred)

I want this. I never liked "filtered" or the adaptors namespace.

Sounds reasonable. Your implementation looks good. regards -Thoorsten