Re: [hub] on the specialized iteration over elements

El 17/04/2026 a las 10:33, Joaquin M López Muñoz via Boost escribió:
> 
> 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.

Right. The local iterator must do the same bitmask trick, which is 
highly optimized (congrats Joaquín).

The only advantage is that we could have constant-time local iterator 
distance (using popcount or similar), the classic STL-like algorithm 
does not take advantage of, but I have ideas on how this could be used 
to implement some hand-made unrolling in some algorithms. For instance, 
std::ranges have this "sized_range" concept that has weaker requirements 
than a full random-access_iterator, and I've found some algorithms can 
be a bit faster just knowing the distance between the iterator range 
without having random-access functions (e.g. you can optimize a bit 
things like count_n and other xxx_n algorithms for forward/bidirectional 
iterators if additionally you can calculate the distance between to 
iterators (which is possible for hub local iterators because after some 
masking popcount-like intrinsic operators can count the number of "1s" 
in the bit mask quite fast.

Also, I managed to convert the hub local_iterator into a random-access 
iterator (implementing operator += inside the block in constant-time), 
but the random-access operations were not fast enough (I'm not expert on 
bit-handling optimizations, I must admit) to make the local iterator 
noticealy faster vs the general iterator. The segmentation iteration has 
also some overhead that must be compensated with a lighter local 
iterator and I could not achieve this for the hub-like data structure.

I'll try to describe my experiments with a hub-like port in another 
thread, although I'm spoiling my own review effort. The goal of this 
experiment was to deeply analyze the design of hub and alternative 
design decisions (spoiler, Joaquín's design seem to be the right one) 
for my own review, but maybe I can describe a bit more the experiment to 
analyze if there is interesting work to do in that line...

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/TFONJ2WLGRGFNJ7GKEYV2YQ5XQVG73HR/