Neoclassical C++ (2): Exploring input-output segmented algorithms – template

" Feed" href="https://boostedcpp.net/feed/" /><br>" Comments Feed" href="https://boostedcpp.net/comments/feed/" /><br>" Neoclassical C++ (2): Exploring input-output segmented algorithms Comments Feed" href="https://boostedcpp.net/2026/08/06/neoclassical-c-2-exploring-input-output-segmented-algorithms/feed/" />

" />

Skip to content

Neoclassical C++ (2): Exploring input-output segmented algorithms

From one segmented range to two

In the first installment of this series we revisited Matt Austern’s Segmented Iterators and Hierarchical Algorithms paper and measured what a modern compiler can do when a single-range, single-pass algorithm (find, fill, count, for_each, …) is decomposed into per-segment flat loops. The results were encouraging: once the per-element block-boundary check disappears from the inner loop, auto-vectorisers wake up and speedups of 3×-6× (with 17× corner cases) appear on small trivially-comparable types.

This second installment moves one step up in difficulty: algorithms that read from one range and write to another one, such as copy, copy_n, copy_if, remove_copy, remove_copy_if, swap_ranges and transform. Now there are two ranges in play and each of them may be segmented, may be flat, or both at the same time.

The good news is that the two ranges are independent: the input walks forward, the output walks forward, and neither influences the shape of the other. The bad news is that the output side is not symmetrical to the input side, and this asymmetry is where all the interesting problems (and all the interesting performance results) of this article come from.

Challenges with the output range

Iterating the output to obtain segment bounds

Austern’s original scheme decomposes a range [first, last) into its segments: you need both endpoints (first + last) to discover the (potentially recursive) segment boundaries . His paper’s worked example is hierarchical_fill, and its shape is the template that every single-range hierarchical algorithm follows:

hierarchical_fill(first, last, value):<br>sfirst = segment(first) // segment containing the first element<br>slast = segment(last) // segment containing the one-past-last

if sfirst == slast: // whole range lives in one segment<br>fill_dispatch(local(first), local(last), value)<br>else:<br>fill_dispatch(local(first), end(sfirst), value) //first segment: partial

for seg = sfirst + 1 while seg != slast, ++seg: // middle segments: full<br>fill_dispatch(begin(seg), end(seg), value)

fill_dispatch(begin(slast), local(last), value) // last segment: partialCode language: C++ (cpp)

The three fill_dispatch calls need a local_iterator range ; if that local_iterator is itself segmented, fill_dispatch calls hierarchical_fill again until the local iterator is flat, at which point it calls the classic STL-like fill. However, the STL output interface provides only a single output iterator (std::copy(first, last, result)) with no result_end argument and thus no segment(result_end) to compute and follow Austern’s decomposition. result is assumed unbounded .

State of the art for segmented outputs

This is less well charted than the input segmentation side, but there are some interesting implementations. Some examples:

libstdc++ specializes output iterator segmentation for deque in bits/deque.tcc. Its destination overload of __copy_move_a1 walks deque blocks, but it needs a random-access input and, since it targets deque specifically, it is neither recursive nor extensible.

libc++ internally implements Austern’s protocol and copy.h has specialized code for a single-level segmented output iterator when the input a non-segmented random-access iterator.

HPX offers a public traits framework (segmented_iterator_traits) and the segmented_copy algorithm supports single-level segmented output iterators. The implementation requires equally segmented source and destination (same partition sizes, same offset for first and dest).

This article will try to outline a scheme that is simultaneously generic and recursive , and that supports independent segmentation on both sides , together with the problems encountered and the benchmark results.

Handling the missing bound for output iterators

The proposal is a two-phase approach that handles the unbounded output iterator and discovers (recursively) its segment boundaries.

Phase 1: Unbounded, outermost level : We ask for the segment it belongs to (result_seg = segment(result)) and obtain the end of that segment (end(result_seg)). We do know that there should be enough segments to hold the number of elements to be written. When this top-level segment is processed, we advance to the next segment (++result_seg) and continue processing. This level is enough to handle single-level segmented types like deque .

Phase 2: Bounded, inner levels : Once we have a bounded output range [local(result), end(result_seg)), then we can use Austern’s pattern. The inner...