[PATCH 1/2] libstdc++: Introduce notion of segmented iterators

[Yuao Ma]

On Wed, Jul 15, 2026 at 8:39 PM Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
>
> On Wed, Jul 15, 2026 at 2:17 PM Yuao Ma <addr2line@gmail.com> wrote:
>>
>> On Wed, Jul 15, 2026 at 3:02 PM Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> > On Tue, 14 Jul 2026, 15:56 Tomasz Kaminski, <tkaminsk@redhat.com> wrote:
>> >>
>> >>>
>> >>>
>> >>> fold_right{, _last} could use backward iteration, but it can also be
>> >>> implemented with reverse iterators.
>> >>
>> >> Is there a big benefit from iterating over segments, versus the whole range
>> >> for fold? And other algorithms that visit all elements. I was thinking mostly
>> >> about cases like distance (where we can compare iterators), or copy
>> >> (when we could `memcpy` the segment).
>> >
>> > Right, there are certainly algorithms that iterate backwards (copy_backward for an obvious example!) but I don't think they benefit from having contiguous or random access iterators, rather than just bidirectional. So I don't think optimising for segments matters.
>> >
>>
>> Based on my experience with libc++, I believe at least some algorithms
>> would benefit from segmented iterators.
>>
>> ref: https://github.com/llvm/llvm-project/issues/102817
>
> Would algorithms like fill/fold/transform benefit from for_each primitive?
> I.e. something that iterates over all elements and invokes the provided callback.
> Because such operation can be implemented with a lot less code for views like
> filter/transform or also join.
>
> I see the value of segmented iterator, in situations where the algorithm can
> process some kind of ranges: sized for distance or contiguous for memcopy
> in a more efficient manner (in bulk) rather than element wise.
>
> Or the changes work in tandem with other optimizations? Like using an
> SIMD implementation of fold, when applying it on the segment?
>

They could definitely benefit from for_each-like primitives. In fact,
if you look at the original paper
(https://lafstern.org/matt/segmented.pdf), the primary performance
gain seems to come from eliminating unnecessary bounds checking by
introducing a hierarchical structure.

>>
>>
>> >
>> >>>
>>