Re: [hub] on the specialized iteration over elements

El 17/04/2026 a las 1:16, Peter Dimov via Boost escribió:
> Andrzej Krzemienski wrote:
>> First, should we draw from this a more general observation that iterators are
>> an abstraction with overhead, and other containers (deque?) would also
>> benefit from this inversion-of-control approach?
> 
> This is called "segmented iterators" (originally motivated by std::deque as the
> best known segmented data structure); Matt Austern coined the name in
> 
> https://lafstern.org/matt/segmented.pdf
> 
> and libc++ has been doing work on it (under the hood), e.g.
> 
> https://github.com/llvm/llvm-project/blob/main/libcxx/include/__iterator/segmented_iterator.h
> https://github.com/llvm/llvm-project/issues/102817
> 
> When I last looked at this I had some ideas how it can be improved and possibly
> standardized, but I've forgotten everything already. :-)
> 
> This might be a good opportunity for Boost to add a segmented iterator API.

You can find the experiments that I'm doing with segmented iterators and 
several algorithms (some are more complicated to implement, if you want 
to support recursively segmented iterators or input and output iterator) 
that the Austern's std::fill example). Here the experimental 
implementation of several segmented algorithms using Austern's traits:

Prototype implementations:

https://github.com/boostorg/container/tree/develop/include/boost/container/experimental

Some tests and a general bench agains std:

https://github.com/boostorg/container/tree/develop/experimental

If the vectorizer is activated (deque is the best example, as the 
local_iterator can be a raw pointer) you can get 5x-10x performance 
improvement in some scenarios. You can have worse performance in some 
cases. I haven't investigate those.

I tried to design efficient segmented iterators for a hub-like container 
but I didn't have success (the hub segmente is relatively small, 64 
elements, and the local iterator is not a sufficiently simpler iterator 
than the general iterator that Joaquín has designed).

I'm currently trying to make all those algorithms support recursively 
segmented iterators, including also dual segmented input and output 
iterators (say, for std::copy).

If results are consistent across compilers and in a broad ranges of 
types, as those obtained in these preliminary tests, maybe I should try 
to present this sutff as a new Boost library...

If you could use your local brain prompt to recover those lost ideas...

Best,

Ion
_______________________________________________
Boost mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/N73UEBVUBJMQVTVYHGG34CGKKIJG363H/