Re: [hub] on the specialized iteration over elements

El 17/04/2026 a las 8:26, Ion Gaztañaga via Boost escribió:
> 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).


Exactly, hub doesn't have a local iterator per se, and intrablock visit 
resolves to (simplified pseoducode):

   auto mask = pb->mask; // pb is a pointer to the block
   while(mask) {
     int n = std::countr_zero(mask);
     f(pb->data[n]);
     mask &= mask - 1; // clear least significant one
   }

which, I presume, any local iterator abstraction wouldn't optimize to 
unless the compiler is extremely smart, though I can work with you Ion 
to see if we can get close.


Joaquín M López Muñoz

_______________________________________________
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/Z45FB4JVWOIG2ZT5E7RRJD7MP6ETRKAU/