Segmented iterators

[Morwenn]

More than once, Matt Austern raised awareness of segmented data structures such as std::deque. The standard algorithms are currently suboptimal for these data structures, while they could be way better if they new that the given iterators correspond to a segmented structure (some standard library implementations already have specific algorithm overloads for std::deque iterators).

Sorting algorithms could take advantage of segmented iterators if they knew about it. For example, if an std::deque uses fixed arrays of only 32 elements, then some kind of bottom-up mergesort could start by sorting each subarray, then it would merge them. It would probably increase data locality and thus performance.

The Meeting C++ 2015 presentation contains some ideas about how the mechanism could be implemented. While it would probably require some standard library support, it is highly unlikely that standard support for segmented iterators will make it into the standard in the next few years (there aren't even official proposals about them), so we might as well start reimplementing those ideas locally.

A CppCon2016 presentation by Patrick Niedzielski gives more insights and ideas for segmented iterators. Moreover, it also defines the SegmentedIterator concept and a few other things that could serve as a base for a library.

[vendethiel]

I would probably increase data locality and thus performance.

You're so good :P. (I remember reading these slides and kinda going "uh?" at them)

[Morwenn]

I would have to time things of course, but the main selling point of the papers is that things can go faster without changing the algorithms interface. On the other hand, without even modifying the sorting algorithms themselves, I already have many standard library reimplemented in cpp-sort (to handle projections and proxy iterators), so just modifying them could make the sorting algorithms faster.

Anyway, I don't think I will start working on that one before a while :p