Re: [Boost-users] [Range] Strange!

Subject: Re: [Boost-users] [Range] Strange!
From: Eric Niebler (eniebler_at_[hidden])
Date: 2014-08-29 18:55:53

On 8/29/2014 10:08 AM, Neil Groves wrote:
> 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.

We could drum up a trait, is_contiguous_iterator, and specialize it on
std::string::iterator. I understand how unsatisfactory that is, but if
all you care about is strings, it works.

> 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 that might make this or that particular use compile and do the
"right" thing, it's unprincipled and fragile, in addition to being
non-standard as you point out below.

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

True. :-(

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

I'd love it if there were an painless fix. I haven't found one, and I've
thought about this quite a bit as a result of my range work. Part of me
feels we should live with the pain of the current constraints in the
hopes that the pain will be so intense that Someone does Something about it.

It's been tried before. I'm very curious what ever became of N1640 [1].
Did it die in committee? Ditto for N2758 [2], which doesn't separate
traversal from access but does weaken the requirements on the reference
type of Forward, Bidirectional and RandomAccess iterators. Did it simply
die with C++0x Concepts?

[^1]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1640.html
[^2]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2758.pdf

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

That would be an interesting research project.

> It would allow easier use of segmented
> iterators etc. without having to rewrite each individual algorithm.

The most important segmented data structure, std::deque, could never
(portably) make use of any hierarchical algorithm you write because it
requires access to the deque's internal segments, which we don't get
access to. I'd put segmented iterators on the back-burner.

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

In my range work, I've punted on the new-style iterator categories, not
because I think it's not worthy, but because I'm focusing my energy
elsewhere. I don't expect we'll be duplicating much work. It would be
HUGE if you could contribute algorithms that make use of the new-style
iterator categories.

\e