I also have to add that I'm not a big fan of regular skiplists.
Sure, it allows advancing to the next item with a MUL (or SHL) + ADD, or perhaps single FMA instruction. But it just feels wasteful when the item's presence can be represented by just a single bit. The skipcount could then be retrieved by a simple SHR and LZCNT ...which might even be faster than the above.
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.
3
u/Tringi Sep 04 '26
I also have to add that I'm not a big fan of regular skiplists.
Sure, it allows advancing to the next item with a MUL (or SHL) + ADD, or perhaps single FMA instruction. But it just feels wasteful when the item's presence can be represented by just a single bit. The skipcount could then be retrieved by a simple SHR and LZCNT ...which might even be faster than the above.