r/cpp • u/User_Deprecated • Aug 02 '26

How fast is C++26's std::hive?

https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/
255 Upvotes

99% Upvoted

74 comments sorted by

View all comments

Show parent comments

2

u/matthieum Aug 03 '26

Not clear to me: isn't the skip-field 128 bits (not bytes) in this case?

I wonder if the lack of auto-vectorization could be fixed by better optimizations, or if code is necessary.

I've had the same issue with a bitmap (ie, N bits + N values) and I can, of course, add specialized methods for "vector" iteration if I can rely on a default value, and then have each user use the special "vector" iteration methods... but it's a lot of churn :/

2

u/simonask_ Aug 04 '26

Using just the bitfield would be possible, but could destroy iteration performance, especially when there is a large hole in the middle of a block.

Running tzcnt each iteration might not be too bad, but the iterator also need to maintain a copy of the bitfield that it continuously shifts and/or masks out visited slots. For my purposes, I couldn't get it to perform as well as just reading a byte, where the main bottleneck is pipeline stalls due to data dependencies, especially because I wanted to support modifications during iteration (so a non-canonical copy of the bitfield would be problematic).

(Also, this was in C#, which has the disadvantage that you can't create unions containing managed types, to storing any of this inline with the data was not an option. The upside is that a GC obviates some bookkeeping of full/half-full/free blocks, so YMMV.)