5 ms·

An interesting resource. Just this past day, I prototyped a Skip List backing a sorted key/value store, and it was super simple to do so (as compared to AVL /

An interesting resource. Just this past day, I prototyped a Skip List backing a sorted key/value store, and it was super simple to do so (as compared to AVL / Red Black). B-Trees are notorious for their complexity, and so SingleStore (memSQL) reasoned that their move to use Skip Lists to back their tables was justified: https://archive.is/Qhpgn https://archive.is/Qhpgn It would be interesting to see the author attempt faster Skip Lists, as their expertise in this topic seems deep enough.

ot 5y ago
Note that the article is exclusively about static data. The vast majority of the complexity of B-trees comes from supporting updates, but constructing a balanced B-tree from a sorted list is relatively straightforward.
marcosdumay 5y ago
Why does the article benchmark indexes on full scan operations?
Comevius 5y ago
Skip lists are so simple conceptually, I'm managing to make them concurrent, verifiable and even persistent. For reference this is a concurrent skip list that a high school student could implement. It's beautiful. https://people.csail.mit.edu/shanir/publications/LazySkipList.pdf https://people.csail.mit.edu/shanir/publications/LazySkipLis...
- sadiq 5y ago
  If anyone wants one based on Herlihy et al's "The Art of Multiprocessor Programming" there's a well reviewed, tested and heavily commented concurrent lock-free one in OCaml's runtime now: https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplis... It's used to manage code fragments that need to be accessed in signal handlers.
  - ignoramous 5y ago
    Thanks, I used that neat knuth coin-flip trick from your code. Why does the comment on the file say that its lock-free implementation is half as slow as compared to 'sequential' one? Where does the slowness come from? Is it all those while(1) loops waiting to race atomic operations?
    - sadiq 5y ago
      So that was in some quick benchmarks against the sequential one in the runtime: https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c I haven't done a huge amount of investigation but I suspect the cost comes from the extra indirection in the lock-free one.
- vanderZwan 5y ago
  > a high school student could implement I agree it's a beautiful data structure, but this imagined high school student would be one who is comfortable with (learning about) pointers and locks. Those exist of course, in fact we probably both qualified back in the day. My point however is that that implies some major selection bias towards high school students who love programming for programming's sake, not some average high-school student who learned a bit of Python and JavaScript in their introduction to computer science class or because they want to write a game (which is a totally valid reason to learn programming). I don't really see why B-trees as a data structure would be that much more difficult to grok if we're already talking about that type of student?
josephg 5y ago
I’ve been wondering something similar. I recently published a rust rope library based on skip lists. (Ropes are “fat strings” optimized for efficient insertion and deletion of arbitrary characters.) My rope is backed by a skip list, where each node in the skip list has a gap buffer. Even without the gap buffer my skip list is ~1.5x faster than the next fastest library on cargo (ropey - which is b-tree based). With gap buffers the resulting code is 4x faster. My library is also significantly smaller, both in lines of code and compiled size. I’ve got another b-tree library I’ve been using for CRDT editing in Diamond Types. Based on this result I’m considering rewriting my btree as a skip list to see how it compares. It’d be a direct apples to apples comparison - I’ve already tuned my btree well as I can. I’m very curious how performance would change. https://crates.io/crates/jumprope https://crates.io/crates/jumprope
- afranchuk 5y ago
  Cool! I was surprised to see ropey as a dependency, I agree those utility functions should be inlined. I'm currently using ropey to keep the server side state of documents in an LSP server. I recommend you add at least a slice type, as that's typically desirable. But looks great otherwise!
  - josephg 5y ago
    Yeah those utility methods will be inlined anyway by the compiler. But copy+paste (with a comment for attribution) is still probably the right tool here. I like the idea of adding a slice type. What use case do you have in mind for that?
    - afranchuk 5y ago
      I don't know about other people, but my tokenizer is parameterized over string slice types. So I tokenize from a slice (be it &str or ropey's RopeSlice) and some of the returned tokens have subslices. This allows tokenization to do no heap allocation.
- twotwotwo 5y ago
  Wow, jumprope is really cool! I'd had, but never gotten at all close to implementing, this idea of something like a a mutable RRB tree (think https://docs.rs/im/latest/im/struct.Vector.html https://docs.rs/im/latest/im/struct.Vector.html but, again, mutable) with somewhat chunky (say, few-KB) gap buffers as the leaves. The tree gives you asymptotically not-terrible behavior with zillions of items, and the gap buffers could help practical performance when there's a lot of locality in your accesses. I figure merging two lists of items or filtering some items out of a list might have the sort of locality of edits gap buffers handle well, and largish gap buffers could allow iteration to mostly spend time walking through contiguous chunks. I still don't know how well something like that applies to a non-rope use case, but it's incredibly cool to see you actually did the work to build a hybrid structure out, validated it, and it does very well.
CamperBob2 5y ago
What's the advantage of a skip list over a simple hash map?
- Someone 5y ago
  They’re ordered, so - in-order iteration over the items is possible - Searches such as “the smallest item greater than n” are efficient
  - avinassh 5y ago
    What about cache locality which is offered by B Trees
    - ignoramous 5y ago
      Read the memSQL blog I linked to; it talks about why not B-Trees for their workloads. It also points out that the concurrent and lock-free nature of Skip Lists was overall a win, despite cache-locality (and other such) concerns. Though, if one can tame allocs (ref: https://archive.is/kwhnG https://archive.is/kwhnG), then they may have cache-locality (just don't expect it to be at Judy Array levels).
avinassh 5y ago
> B-Trees are notorious for their complexity Can you tell me more?
- adrianN 5y ago
  The rebalancing operations are fairly complex to implement.
  - xemul 5y ago
    I wouldn't say RB-tree rebalancing is much simpler. On the other hand, in B-trees there's a whole lot of poorly documented nuances, binary trees are more intuitive. But in the end of the day the implementation effort perfectly worth it. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/ https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree...
    - adrianN 5y ago
      Yeah, balanced trees of any kind are fairly complex compared to skip lists.

ot 5y ago

Note that the article is exclusively about static data. The vast majority of the complexity of B-trees comes from supporting updates, but constructing a balanced B-tree from a sorted list is relatively straightforward.

marcosdumay 5y ago

Why does the article benchmark indexes on full scan operations?

Comevius 5y ago

Skip lists are so simple conceptually, I'm managing to make them concurrent, verifiable and even persistent. For reference this is a concurrent skip list that a high school student could implement. It's beautiful. https://people.csail.mit.edu/shanir/publications/LazySkipList.pdf https://people.csail.mit.edu/shanir/publications/LazySkipLis...

sadiq 5y ago
If anyone wants one based on Herlihy et al's "The Art of Multiprocessor Programming" there's a well reviewed, tested and heavily commented concurrent lock-free one in OCaml's runtime now: https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplis... It's used to manage code fragments that need to be accessed in signal handlers.
- ignoramous 5y ago
  Thanks, I used that neat knuth coin-flip trick from your code. Why does the comment on the file say that its lock-free implementation is half as slow as compared to 'sequential' one? Where does the slowness come from? Is it all those while(1) loops waiting to race atomic operations?
  - sadiq 5y ago
    So that was in some quick benchmarks against the sequential one in the runtime: https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c I haven't done a huge amount of investigation but I suspect the cost comes from the extra indirection in the lock-free one.
vanderZwan 5y ago
> a high school student could implement I agree it's a beautiful data structure, but this imagined high school student would be one who is comfortable with (learning about) pointers and locks. Those exist of course, in fact we probably both qualified back in the day. My point however is that that implies some major selection bias towards high school students who love programming for programming's sake, not some average high-school student who learned a bit of Python and JavaScript in their introduction to computer science class or because they want to write a game (which is a totally valid reason to learn programming). I don't really see why B-trees as a data structure would be that much more difficult to grok if we're already talking about that type of student?

josephg 5y ago

I’ve been wondering something similar. I recently published a rust rope library based on skip lists. (Ropes are “fat strings” optimized for efficient insertion and deletion of arbitrary characters.) My rope is backed by a skip list, where each node in the skip list has a gap buffer. Even without the gap buffer my skip list is ~1.5x faster than the next fastest library on cargo (ropey - which is b-tree based). With gap buffers the resulting code is 4x faster. My library is also significantly smaller, both in lines of code and compiled size. I’ve got another b-tree library I’ve been using for CRDT editing in Diamond Types. Based on this result I’m considering rewriting my btree as a skip list to see how it compares. It’d be a direct apples to apples comparison - I’ve already tuned my btree well as I can. I’m very curious how performance would change. https://crates.io/crates/jumprope https://crates.io/crates/jumprope

afranchuk 5y ago
Cool! I was surprised to see ropey as a dependency, I agree those utility functions should be inlined. I'm currently using ropey to keep the server side state of documents in an LSP server. I recommend you add at least a slice type, as that's typically desirable. But looks great otherwise!
- josephg 5y ago
  Yeah those utility methods will be inlined anyway by the compiler. But copy+paste (with a comment for attribution) is still probably the right tool here. I like the idea of adding a slice type. What use case do you have in mind for that?
  - afranchuk 5y ago
    I don't know about other people, but my tokenizer is parameterized over string slice types. So I tokenize from a slice (be it &str or ropey's RopeSlice) and some of the returned tokens have subslices. This allows tokenization to do no heap allocation.
twotwotwo 5y ago
Wow, jumprope is really cool! I'd had, but never gotten at all close to implementing, this idea of something like a a mutable RRB tree (think https://docs.rs/im/latest/im/struct.Vector.html https://docs.rs/im/latest/im/struct.Vector.html but, again, mutable) with somewhat chunky (say, few-KB) gap buffers as the leaves. The tree gives you asymptotically not-terrible behavior with zillions of items, and the gap buffers could help practical performance when there's a lot of locality in your accesses. I figure merging two lists of items or filtering some items out of a list might have the sort of locality of edits gap buffers handle well, and largish gap buffers could allow iteration to mostly spend time walking through contiguous chunks. I still don't know how well something like that applies to a non-rope use case, but it's incredibly cool to see you actually did the work to build a hybrid structure out, validated it, and it does very well.

CamperBob2 5y ago

What's the advantage of a skip list over a simple hash map?

Someone 5y ago
They’re ordered, so - in-order iteration over the items is possible - Searches such as “the smallest item greater than n” are efficient
- avinassh 5y ago
  What about cache locality which is offered by B Trees
  - ignoramous 5y ago
    Read the memSQL blog I linked to; it talks about why not B-Trees for their workloads. It also points out that the concurrent and lock-free nature of Skip Lists was overall a win, despite cache-locality (and other such) concerns. Though, if one can tame allocs (ref: https://archive.is/kwhnG https://archive.is/kwhnG), then they may have cache-locality (just don't expect it to be at Judy Array levels).

avinassh 5y ago

> B-Trees are notorious for their complexity Can you tell me more?

adrianN 5y ago
The rebalancing operations are fairly complex to implement.
- xemul 5y ago
  I wouldn't say RB-tree rebalancing is much simpler. On the other hand, in B-trees there's a whole lot of poorly documented nuances, binary trees are more intuitive. But in the end of the day the implementation effort perfectly worth it. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/ https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree...
  - adrianN 5y ago
    Yeah, balanced trees of any kind are fairly complex compared to skip lists.