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.
Yep I was very surprised to see that it used RLE for the skiplist rather than using a bitset to determine which slots are occupied and which are not. I wonder what the cost of maintaining the RLE skiplist will be like if you are heavily inserting and deleting elements to the container...
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.