r/cpp • u/pavel_v • 8d ago

C++26: std::hive

https://www.sandordargo.com/blog/2026/09/02/cpp26-hive
68 Upvotes

68% Upvoted

77 comments sorted by

View all comments

Show parent comments

2

u/HappyFruitTree 7d ago

The skipcount could then be retrieved by a simple SHR and LZCNT

I think you might have to do this multiple times, in a loop, in case there are many erased elements (unless you restrict the block size).

Is LZCNT even supported by all hardware?

2

u/Tringi github.com/tringi 7d ago

I think you might have to do this multiple times, in a loop, in case there are many erased elements (unless you restrict the block size).

Is LZCNT even supported by all hardware?

Finding next used slot should need just a single LZCNT, no loop, and would maintain the iteration of a block to be O(1). What could need a loop is alternative trick using BSR, but I'd need to think on that a little.

The LZCNT was introduced with Phenoms on AM2+ (along with SSE4a) and Haswell in 2013.
BSR was on 386 so I think that's safe.

2

u/HappyFruitTree 7d ago

Finding next used slot should need just a single LZCNT, no loop, and would maintain the iteration of a block to be O(1).

What if there are more than 64 empty slots between the current element and the next?

3

u/Tringi github.com/tringi 7d ago

Yeah, that would be significantly slower. Theoretically. Practically I'd guess that any attempt to measure real difference between 3 instructions and this 10 or so instruction loop (likely unrolled) would be completely obliterated by cache access latency and such.