On 28 August 2014 22:22, Neil Groves wrote:

The counting_range instance is a unnamed temporary,,,,

So the earlier lines are flawed too, just working by chance? - Rob.

On 28 August 2014 22:35, Krzysztof Czainski <1czajnik@gmail.com> wrote:

2014-08-28 23:29 GMT+02:00 Robert Jones :

On 28 August 2014 22:22, Neil Groves wrote:

...

...

The counting_range instance is a unnamed temporary,,,,

So the earlier lines are flawed too, just working by chance?

Yes, combinations of counting_range with reversed. But not because counting_range is a temporary.

You are completely right in this instance. I've seen too many functions return a collection by value and then be used as the left-most operand in a chain of range adaptors! This is not applicable here.

I think the problem is counting_iterator returns a reference to an int it owns. Iterators shouldn't do that.

This is exactly what is causing the issue.

Iterators should either: - return a reference to something they don't own, or - return by value.

Your logic for return type makes a lot of sense. Unfortunately there are conflated requirements upon the return type of dereference operations for the various iterator traversals. See http://www.boost.org/doc/libs/1_56_0/libs/multi_array/doc/iterator_categorie.... I imagine that this is why the counting_iterator is implemented to return a true reference. This leaves us with rather a thorny problem, a counting_iterator can't have the dereference operator return by value and model the Bidirectional Iterator Concept. Therefore if counting_iterator were to return by value we wouldn't be allowed to reverse (if we constrained ourselves to the Standard iterator traversal categories). It might be that there is room for improvement while working with the Boost traversal tags rather than the iterator traversal tags.

Regards, Kris

Thanks for pointing this out, I hadn't spotted this issue with the counting_iterator. After giving this some more thought I shall raise a ticket for Boost.Iterator. Regards, Neil Groves

On 29 August 2014 04:04, Eric Niebler wrote:

...

On 28 August 2014 22:35, Krzysztof Czainski wrote: I see no conflated requirements. In Boost.Iterators (as opposed to the standard iterator categories), iterator *traversal* deals only with

On 8/28/2014 3:49 PM, Neil Groves wrote: traversal (++, --, +=, -=, etc) and says nothing about the return type of the dereference operation.

I perhaps used poor language. I believe that we are actually in complete agreement. The Boost.Iterator Traversal Concepts are perfect and do not have any problem. I was attempting to suggest that we could make improvements for code that uses this idiom. My concern was for interoperability with the standard algorithms (and therefore the Boost.Range algorithms). The conflation of return type and traversal in the standard definition for iterators is an issue we are clearly both aware of.

Krzysztof is right, though. The dereference operation should return an rvalue. That would make the counting_iterator a Readable iterator in the new-style categories. "Readable" is orthogonal to the iterator traversal.

So IMO, counting_iterator should be a Readable Iterator and a Random Access Traversal Iterator. When this is mapped to one of the standard iterator categories, it becomes std::input_iterator_tag (because of the requirements on Forward Iterators in the standard).

I see where you are coming from, I might even agree, but the impact upon standard algorithms would be horrific. I don't find O(N) for std::distance of a counting iterator upon integers to be acceptable. Clearly I can make the Boost.Range boost::distance O(1) by altering the implementation to not forward to the standard implementation. This would be required for almost all of the standard algorithms, hence I'd have to rewrite them all. Even with this effort the result would be sub-optimal since there are many internal details within standard algorithm implementations to optimise for various standard containers e.g. __niter.

...

I imagine that this is why the counting_iterator is implemented to return a true reference.

No, I think this is a bug, plain and simple. Fixing it is likely to cause trouble though. :-(

I agree that it is a bug. The defect is simple, but the best solution isn't. Your suggestion is valid, but it falls short of being an acceptable solution. I was hoping to find a cunning way to keep the counting_iterator random access while solving the lifetime issue. I've not spent enough effort to convince myself that this is not possible yet.

...

This leaves us with rather a thorny problem, a counting_iterator can't have the dereference operator return by value and model the Bidirectional Iterator Concept. Therefore if counting_iterator were to return by value we wouldn't be allowed to reverse (if we constrained ourselves to the Standard iterator traversal categories). It might be that there is room for improvement while working with the Boost traversal tags rather than the iterator traversal tags.

If Boost.Range were made aware of the Boost new-style iterator categories -- which make traversal and access independent -- the reversed view could still work with counting_iterator. The resulting view's iterators would also be Random Access Traversal and Readable.

Boost.Range uses the Boost.Iterator traversal idioms extensively. The Boost.Range Concepts are defined to avoid the reference type conflation with traversal for example. Sadly, this doesn't help when the result is fed into a Boost.Range algorithm that forwards to a standard algorithm. The state of play is that Boost.Range prefers the Boost.Iterator idioms but does not reimplement the standard parts and hence falls foul of the standard issues.

Making all of Boost.Range aware of the new-style iterators would be a piece of work, though.

I believe that most of Boost.Range (aside from the standard algorithms) does fully support the Boost.Iterator idioms. I'm completely willing to invest the time to modify any issue in Boost.Range related to this. At the moment I don't see a good solution for the standard algorithms. I am definitely open to suggestions. At the moment I am keen to at least reimplement boost::distance, but this does seem hopelessly incomplete.

...

Thanks for pointing this out, I hadn't spotted this issue with the counting_iterator. After giving this some more thought I shall raise a ticket for Boost.Iterator.

Indeed. Please include this discussion in the bug report.

I'll wait for your response before raising the ticket.

Eric

Regards, Neil Groves

...

I see where you are coming from, I might even agree, but the impact upon standard algorithms would be horrific. I don't find O(N) for std::distance of a counting iterator upon integers to be acceptable.

Are people passing counting_iterators to std::distance? Yes, it's a problem, but taking too long to get the right answer doesn't seem as bad as the random garbage the current behavior is giving.

Yes.

...

Clearly I can make the Boost.Range boost::distance O(1) by altering the implementation to not forward to the standard implementation. This would be required for almost all of the standard algorithms, hence I'd have to rewrite them all.

Yes. IMO, Boost.Algorithm should have versions of ALL the standard library algorithm, rewritten to work with the new-style iterator categories. And yes, it's a lot of work, but not as much as you might think. I should know, I'm just about finished my own complete reimplementation of the algorithms for my range work.

This is certainly something that can be done. I find it disappointing that it will be a reimplementation not simply because it is additional work, but because there doesn't appear to be progress in making the Standard better in this respect. It would clearly be a better end result if we could make the existing standard algorithms work in this manner. I also respect that we might want to do something in the library in the interim to get results before 2018!

...

Even with this effort the result would be sub-optimal since there are many internal details within standard algorithm implementations to optimise for various standard containers e.g. __niter.

Not a big problem in practice, IMO.

It is for my use-cases. The __niter iterator extraction creates very substantial performance gains. I appreciate that not everything is performance-critical, but a lot of the work I do is. If it adds overhead I often simply can't use it. The benefits when a string iterator is extracted to a pointer yields 2x performance gains in several algorithms in my tests, because it often selects contiguous pointer overloads for sub-algorithms.

...

I agree that it is a bug. The defect is simple, but the best solution isn't. Your suggestion is valid, but it falls short of being an acceptable solution. I was hoping to find a cunning way to keep the counting_iterator random access while solving the lifetime issue. I've not spent enough effort to convince myself that this is not possible yet.

You prefer undefined behavior to a perf bug? Undefined behavior is exploitable. It's a security issue.

I am clearly not stating that we should do nothing. I wanted to consider alternatives to immediately conceding that the demotion to input iterator category was the best we could achieve. I understand the ramifications of the defect. Having thought about the various trade-offs I am starting to believe it would be worth considering returning by const value and having the iterator category map to std::random_access_iterator_category. The return by const value rather than value avoids an issue where a lifetime issue if an algorithm uses auto& for the dereferenced result within the calling function. While this would be non-compliant, it seems that the cases where this would actually cause a problem are rather theoretical. I have noticed that there is an int_iterator hidden in boost/iterator/detail that works in exactly this proposed fashion. It would be interesting to see how well this has worked. The demotion to input iterator does not merely create a performance bug. Standard algorithms (and user algorithms that use the standard iterator categories) that require more than an input iterator will no longer compile with the resultant counting_iterator. Therefore code will not only break, there won't be an obvious adjustment to make to repair the client code. Again, I'm not arguing that your proposal is not necessarily the optimal one. I just feel that the ramifications of the change are sufficiently abhorrent that we should ensure we have considered as many alternatives as we can muster.

...

Boost.Range uses the Boost.Iterator traversal idioms extensively. The Boost.Range Concepts are defined to avoid the reference type conflation with traversal for example. Sadly, this doesn't help when the result is fed into a Boost.Range algorithm that forwards to a standard algorithm. The state of play is that Boost.Range prefers the Boost.Iterator idioms but does not reimplement the standard parts and hence falls foul of the standard issues.

Great! Then only the algorithms need to be reimplemented. ;-) And actually, only those that require anything more than input iterators. That should cut the work load in half, or better.

I think an optimal implementation requires the reimplementation of each algorithm that could attain performance benefit from traversal tag dispatch? I don't think the difference matters much. I also believe there are other significant potential advantages to defining a core set of iteration algorithm primitives, and then implementing the remaining algorithms in terms of these. It would allow easier use of segmented iterators etc. without having to rewrite each individual algorithm. I am therefore leaning toward writing the algorithms anyhow. I'll avoid hijacking this thread further on this subject, and contact you directly to optimise how we proceed avoiding duplication as much as possible. Regards, Neil

On 29/08/14 17:16, Eric Niebler wrote:

...

Clearly I can make the Boost.Range boost::distance O(1) by altering the implementation to not forward to the standard implementation. This would be required for almost all of the standard algorithms, hence I'd have to rewrite them all. Yes. IMO, Boost.Algorithm should have versions of ALL the standard

On 8/29/2014 1:21 AM, Neil Groves wrote: library algorithm, rewritten to work with the new-style iterator categories. And yes, it's a lot of work, but not as much as you might think. I should know, I'm just about finished my own complete reimplementation of the algorithms for my range work.

Hello, Although I 'm not familiar with the problem you discuss, reimplementing algorithms seems against avoiding duplication. I have a pull request on Boost.Algorithm arguing the opposite for any_of: https://github.com/boostorg/algorithm/pull/3 The optimizations STL implementers may have come up with and the user's choice of an implementation are thrown out of the window. Am I missing something? Albert

On 09/09/2014 12:06 PM, Eric Niebler wrote:

std::istream_iterator and its ilk really should go away. Could you please elaborate on why they are bad [honest curious question].

Cheers, -- Peter Johansson

On 09/09/14 03:06, Eric Niebler wrote:

...

On 29/08/14 17:16, Eric Niebler wrote:

...

...

Clearly I can make the Boost.Range boost::distance O(1) by altering the implementation to not forward to the standard implementation. This would be required for almost all of the standard algorithms, hence I'd have to rewrite them all. Yes. IMO, Boost.Algorithm should have versions of ALL the standard

On 8/29/2014 1:21 AM, Neil Groves wrote: library algorithm, rewritten to work with the new-style iterator categories. And yes, it's a lot of work, but not as much as you might think. I should know, I'm just about finished my own complete reimplementation of the algorithms for my range work. Hello,

Although I 'm not familiar with the problem you discuss, reimplementing algorithms seems against avoiding duplication. I have a pull request on Boost.Algorithm arguing the opposite for any_of:

https://github.com/boostorg/algorithm/pull/3

The optimizations STL implementers may have come up with and the user's choice of an implementation are thrown out of the window. Am I missing something?

On 9/8/2014 7:53 AM, Albert Yiamakis wrote: 0) In my case, it's necessary research for my standardization proposal, which represents a non-trivial rethink of how the algorithms work.

A) Nobody would be forced to use the new versions of the algorithms, either mine or Boost.Algorithms's. I imagine folks would prefer the std:: versions *when they meet their needs*.

i) The new algorithms would meet the needs of people using the new-style iterator categories, and have forward-or-better traversal, but only only readable access -- which maps to std::input_iterator_tag, and prevents the sequence from being used with many std:: algorithms. These people currently have no recourse.

a) My rewrite is to accommodate both ranges and sentinels, and obviates the need to implement iterators with dummy sentinels and complicated state and logic. std::istream_iterator and its ilk really should go away.

Thanks for the comprehensive reply. Although it's true we 're not forced to use the Boost libraries, I would hope it's possible to use - and already do so wherever I can - Boost.Range as an elegant substitute to STL. Ideally, a _complete_ substitute until ranges are standardised, without worrying that certain algorithms are inferior. I 'm also curious as to why istream_iterator should go away. Surely it is a fascinating aspect of the STL, being able to read straight from input into an algorithm - ie integers into accumulate. I can imagine it making an elegant range though, the one operating on cin called STDIN; then we can write something like accumulate(STDIN<int>, 0); Albert