5 ms·

Let's Talk SkipList

126 points by signa11 4y ago

keepquestioning 4y ago
vvern 4y ago
CockroachDB uses a skip list for its “timestamp cache” data structure, used to implement serializable isolation. The data structure records reads and exists to ensure that writes cannot rewrite history. This[1] library is the basis of the implementation in the database. [1] https://github.com/andy-kimball/arenaskl https://github.com/andy-kimball/arenaskl
KerrAvon 4y ago
Cold take: I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation. Also, most linked lists should actually be deques.
- dreamcompiler 4y ago
  A skip list is an ordered data structure with lookup time O[logn]. Hash tables are unordered, with lookup time O[1]. They serve different purposes.
- PotatoPancakes 4y ago
  > I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation. Skiplists are ordered. Perhaps without much advantage compared to, say, a balanced BST. But Hash tables aren't ordered, so they aren't as good for storing data when preserving order is important. > Also, most linked lists should actually be deques. Yep, for almost all purposes, so long as using the extra memory for the reverse pointers isn't an issue. Deques are more flexible and much easier to work with (and especially to debug) than singly-linked lists. Not much of a take, I think a large proportion of developers would vehemently agree with you there.
  - ignoramous 4y ago
    > Perhaps without much advantage compared to, say, a balanced BST. A balanced BST comparatively does more work than a SkipList. Its cousin, SplayTrees, on the other hand, might give SkipList a run for its money.
  - dietrichepp 4y ago
    You can typically insert into a skiplist in parallel with better performance than inserting into a balanced BST in parallel. So you may prefer a skiplist for concurrent write-heavy loads.
  - jongjong 4y ago
    Having implemented a SkipList and compared it to various binary tree implementations, my observation is that they're essentially equivalent in terms of performance for most operations. For insertion, my SkipList implementation was faster than most binary tree implementations but I found a Red-Black Binary Tree implementation which was faster. Still, my SkipList was much faster with batch-deletion of contiguous records. This is because a SkipList does not require re-balancing after each individual deletion; once you've found a starting point and ending point (which has O(log n) time complexity), the deletion of an arbitrarily large chunk of a SkipList can be done in constant time. Here is my implementation (Node.js/JavaScript) in case anyone is interested: https://www.npmjs.com/package/proper-skip-list https://www.npmjs.com/package/proper-skip-list
- idsout 4y ago
  Skip lists can be a good candidate for an ordered concurrent map implementation, outperforming an ordered map based on a bst/btree for instance.
nfgrep 4y ago
I remember implementing a skip-list in order to do some hacky ray-casting on the GPU. Pretty significant performance improvement, and fun to implement!
- nfgrep 4y ago
  Actually, the “skip list” I implemented wasn’t as general as the ones talked about here. I had the “skips” pre-computed at specific intervals to skip sometimes huge numbers of entries, sometimes just a few, it wasn’t equally distributed. Didn’t know there was a more general implementation, neat!
slyrus 4y ago
ISTR SkipLists being used by the NCBI toolkit for DNA/AA sequence data way back in the day. Of course now I can't find any reference to it, but did find this paper on SkipLists in multiple alignments from 2003: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC521198/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC521198/
rektide 4y ago
Go Terps (University of Maryland, College Park)! First described by Bill Pugh in 1989.
mbfg 4y ago
Is it me, or does the post not explain what the benefits are of a skiplist? Ok, maybe it's just "a here's how to implement" post, but seems strange.
- killingtime74 4y ago
  You’re right it didn’t. I believe the main benefit vs binary search in arrays is that it’s linked list like nature makes insertion and removal Faster
  - thesz 4y ago
    Please consider COLA: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec23.pdf http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/le... A hierarchy of sorted arrays, with merging when needed. Single access time is O(logN), scan is theoretically the fastest possible, inserts and deletes are also O(logN). Almost no pointer chasing.
- bodhiandphysics 4y ago
  Skip lists in practice are faster than balanced binary trees in insertion, since rebalancing is slow, while insert and delete in a sl are very fast (if you have a fast source of random or pseudorandom numbers). Skip list insertion is also very easily to parallelize. Insert on a bbt requires locking basically the whole tree.
  - thesz 4y ago
    If you can turn your keys into byte/bit sequences, and most of the time you can, you can use crit bit trees or binary Patricia trees. These are fast structures and support ordered traversal. They also do not rebalance and do not require locking the whole tree. Skip lists are built upon double linked lists, many of them. Parallelizing operations on double linked lists is not easy, it is quite easy to introduce potential deadlock.
    - Tyr42 4y ago
anfelor 4y ago
There is also a nice new datastructure called Zip Trees [1] which is isomorphic to skip lists in the sense that it performs exactly the same comparisons on insertion/deletion (but it can skip some redundant ones). I would expect zip trees to be faster than skip lists in practice. [1]: https://arxiv.org/abs/1806.06726 https://arxiv.org/abs/1806.06726
- ajross 4y ago
  Yeah, for those tempted in these directions, Zip trees seem like the clearly preferred tool. The variable-sized heap blocks of the skip list and the need for 4 pointers per entry (on average two doubly-linked list nodes) turn out to be real limitations in practice. At the end of the day, the only think skip lists really win on is code size. For those not tempted and wondering if they should be: no, stick with your existing (red/black or AVL) balanced trees. They're clunkier and harder to explain, but they work just as well.
  - mananaysiempre 4y ago
    Unless you absolutely require deletion of a node specified by pointer, why would you include backlinks? (Also, if you’re fine with resorting to randomized data structures, conventional treaps are quite good while being IMO easier to understand and code than either AVL or RB. The only reason I could imagine for not using them is adversarial input, although I’ve never seen an attack demostrated. Now that I’m reading the paper, zip trees seem quite nice and simple as well.)
infradig 4y ago
Nice. I have used unrolled SkipLists extensively in Trealla Prolog, where it is integral to fast performance on large (1M+) Prolog rule-sets.
pizlonator 4y ago
For what it’s worth, my crappy skip list implementation was a bit slower than my crappy red-black tree implementation at mixed read/write workloads, but it was faster to iterate sequentially, but that never mattered for me enough for it to be a net win. I ended up switching back to red-black trees. This is just one data point. I suspect I’ll try using them again next time I’m trying to squeeze perf out of an ordered search data structure.

126 points by signa11 4y ago

CockroachDB uses a skip list for its “timestamp cache” data structure, used to implement serializable isolation. The data structure records reads and exists to ensure that writes cannot rewrite history. This[1] library is the basis of the implementation in the database. [1] https://github.com/andy-kimball/arenaskl https://github.com/andy-kimball/arenaskl

KerrAvon 4y ago

Cold take: I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation. Also, most linked lists should actually be deques.

dreamcompiler 4y ago
A skip list is an ordered data structure with lookup time O[logn]. Hash tables are unordered, with lookup time O[1]. They serve different purposes.
PotatoPancakes 4y ago
> I remain unconvinced that skiplists cannot be better replaced in most cases with a good hash table/dictionary implementation. Skiplists are ordered. Perhaps without much advantage compared to, say, a balanced BST. But Hash tables aren't ordered, so they aren't as good for storing data when preserving order is important. > Also, most linked lists should actually be deques. Yep, for almost all purposes, so long as using the extra memory for the reverse pointers isn't an issue. Deques are more flexible and much easier to work with (and especially to debug) than singly-linked lists. Not much of a take, I think a large proportion of developers would vehemently agree with you there.
- ignoramous 4y ago
  > Perhaps without much advantage compared to, say, a balanced BST. A balanced BST comparatively does more work than a SkipList. Its cousin, SplayTrees, on the other hand, might give SkipList a run for its money.
- dietrichepp 4y ago
  You can typically insert into a skiplist in parallel with better performance than inserting into a balanced BST in parallel. So you may prefer a skiplist for concurrent write-heavy loads.
- jongjong 4y ago
  Having implemented a SkipList and compared it to various binary tree implementations, my observation is that they're essentially equivalent in terms of performance for most operations. For insertion, my SkipList implementation was faster than most binary tree implementations but I found a Red-Black Binary Tree implementation which was faster. Still, my SkipList was much faster with batch-deletion of contiguous records. This is because a SkipList does not require re-balancing after each individual deletion; once you've found a starting point and ending point (which has O(log n) time complexity), the deletion of an arbitrarily large chunk of a SkipList can be done in constant time. Here is my implementation (Node.js/JavaScript) in case anyone is interested: https://www.npmjs.com/package/proper-skip-list https://www.npmjs.com/package/proper-skip-list
idsout 4y ago
Skip lists can be a good candidate for an ordered concurrent map implementation, outperforming an ordered map based on a bst/btree for instance.

nfgrep 4y ago

I remember implementing a skip-list in order to do some hacky ray-casting on the GPU. Pretty significant performance improvement, and fun to implement!

nfgrep 4y ago
Actually, the “skip list” I implemented wasn’t as general as the ones talked about here. I had the “skips” pre-computed at specific intervals to skip sometimes huge numbers of entries, sometimes just a few, it wasn’t equally distributed. Didn’t know there was a more general implementation, neat!

slyrus 4y ago

ISTR SkipLists being used by the NCBI toolkit for DNA/AA sequence data way back in the day. Of course now I can't find any reference to it, but did find this paper on SkipLists in multiple alignments from 2003: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC521198/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC521198/

rektide 4y ago

Go Terps (University of Maryland, College Park)! First described by Bill Pugh in 1989.

mbfg 4y ago

Is it me, or does the post not explain what the benefits are of a skiplist? Ok, maybe it's just "a here's how to implement" post, but seems strange.

killingtime74 4y ago
You’re right it didn’t. I believe the main benefit vs binary search in arrays is that it’s linked list like nature makes insertion and removal Faster
- thesz 4y ago
  Please consider COLA: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec23.pdf http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/le... A hierarchy of sorted arrays, with merging when needed. Single access time is O(logN), scan is theoretically the fastest possible, inserts and deletes are also O(logN). Almost no pointer chasing.
bodhiandphysics 4y ago
Skip lists in practice are faster than balanced binary trees in insertion, since rebalancing is slow, while insert and delete in a sl are very fast (if you have a fast source of random or pseudorandom numbers). Skip list insertion is also very easily to parallelize. Insert on a bbt requires locking basically the whole tree.
- thesz 4y ago
  If you can turn your keys into byte/bit sequences, and most of the time you can, you can use crit bit trees or binary Patricia trees. These are fast structures and support ordered traversal. They also do not rebalance and do not require locking the whole tree. Skip lists are built upon double linked lists, many of them. Parallelizing operations on double linked lists is not easy, it is quite easy to introduce potential deadlock.
  - Tyr42 4y ago

anfelor 4y ago

There is also a nice new datastructure called Zip Trees [1] which is isomorphic to skip lists in the sense that it performs exactly the same comparisons on insertion/deletion (but it can skip some redundant ones). I would expect zip trees to be faster than skip lists in practice. [1]: https://arxiv.org/abs/1806.06726 https://arxiv.org/abs/1806.06726

ajross 4y ago
Yeah, for those tempted in these directions, Zip trees seem like the clearly preferred tool. The variable-sized heap blocks of the skip list and the need for 4 pointers per entry (on average two doubly-linked list nodes) turn out to be real limitations in practice. At the end of the day, the only think skip lists really win on is code size. For those not tempted and wondering if they should be: no, stick with your existing (red/black or AVL) balanced trees. They're clunkier and harder to explain, but they work just as well.
- mananaysiempre 4y ago
  Unless you absolutely require deletion of a node specified by pointer, why would you include backlinks? (Also, if you’re fine with resorting to randomized data structures, conventional treaps are quite good while being IMO easier to understand and code than either AVL or RB. The only reason I could imagine for not using them is adversarial input, although I’ve never seen an attack demostrated. Now that I’m reading the paper, zip trees seem quite nice and simple as well.)

infradig 4y ago

Nice. I have used unrolled SkipLists extensively in Trealla Prolog, where it is integral to fast performance on large (1M+) Prolog rule-sets.

pizlonator 4y ago

For what it’s worth, my crappy skip list implementation was a bit slower than my crappy red-black tree implementation at mixed read/write workloads, but it was faster to iterate sequentially, but that never mattered for me enough for it to be a net win. I ended up switching back to red-black trees. This is just one data point. I suspect I’ll try using them again next time I’m trying to squeeze perf out of an ordered search data structure.