1. 55

  2. 13

    I have an ISC-licensed skiplist library for C.

    Also, I can confirm that unrolling skiplists makes them significantly more time and memory-efficient. I started working on a library for that (called “skiparray”; I was thinking of it as a B-Tree-like skiplist), but got sidetracked into working on the property-based testing library (theft) I was using to test it.

    I haven’t figured out yet if it’s faster to unroll the skiplist into blocks of key/value pairs, or into only keys and forward pointers, and put all the values in a bottom layer (roughly analogous to B Trees vs. B+ Trees). It may be beneficial to store more keys and forward pointers per node, and group the bottom key/value pairs into a block with a different size than the upper layers.

    1. 2

      Surprisingly, there was another article about skip lists posted today.

      1. 1

        It both amuses and pleases me that the code backing this article was written in Python :)

        Everybody loves to rant and roar about it, but at the end of the day a lot of excellent work gets done despite the syntactic whitespace or whatever else your favorite hobby horse complaint is.