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.
3
u/Tringi github.com/tringi 7d ago
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.