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