3 ms·

First sentence of the abstract: "Skiplists have become prevalent in systems." They have? I've always viewed them as a curiosity. They're a ton easier to unde

by ajross 3y ago

First sentence of the abstract: "Skiplists have become prevalent in systems." They have? I've always viewed them as a curiosity. They're a ton easier to understand than balanced trees and have the same performance behavior, which sounds great. But the allocation mess[1] makes them lose to RB or AVL trees in, basically every system I can think of. Is any major software using skiplists as a standard ordered container or map? [1] You either need to pay for Log2(N) pointers per item, or allocate them from a heap with variable header sizes. Both of those choices are really pessimal when compared with fixed-size metadata. Skiplists pretty much can't be intrusive, for example.

evdubs 3y ago
> Is any major software using skiplists as a standard ordered container or map? Java for concurrent navigable maps. https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/ConcurrentNavigableMap.html https://docs.oracle.com/en/java/javase/21/docs/api/java.base... > All Known Implementing Classes: ConcurrentSkipListMap Balancing binary search trees suffer from lock contention more than skip lists.
- ajross 3y ago
  > Balancing binary search trees suffer from lock contention more than skip lists. Hm... I guess the argument would be that the various list insertions can be independently synchronized? Certainly lookup is going to be a r/w lock or whatever and basically a wash. I vaguely buy that but would want to see numbers. But that said, the hash made of the heap due to the variable size nodes and lack of intrusivity is going to have exactly the opposite effect for any high performance implementation. Maybe Java doesn't play in that sandbox, I guess.
  - _benedict 3y ago
    Garbage collectors are really nice for concurrent data structures, making lock-free algorithms very practical. Java's skip list does not require any locks for write, and requires essentially no synchronisation at all for reads (just suitable platform-dependent memory barriers). I believe reads are also wait free. There is a locality penalty for lookups, although I don't think this is core to skip-lists, just an impracticality of the Java language and how you can use its standard libraries. The variable size of the nodes is not a problem for the Java heap, due to how compacting garbage collectors work.
fourthark 3y ago
Pretty sure I learned about skip lists as a lock-free data structure that is relatively easy to reason about (but it was a while ago and I’m not finding confirmation in a quick search).
- senderista 3y ago
  Skip lists are relatively simple to make lock-free, while lock-free (even unbalanced) binary search trees are an absolute nightmare. https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...
twoodfin 3y ago
SingleStore (née MemSQL) uses a skiplist as its foundational in-memory data structure.

by ajross 3y ago

evdubs 3y ago

> Is any major software using skiplists as a standard ordered container or map? Java for concurrent navigable maps. https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/ConcurrentNavigableMap.html https://docs.oracle.com/en/java/javase/21/docs/api/java.base... > All Known Implementing Classes: ConcurrentSkipListMap Balancing binary search trees suffer from lock contention more than skip lists.

ajross 3y ago
> Balancing binary search trees suffer from lock contention more than skip lists. Hm... I guess the argument would be that the various list insertions can be independently synchronized? Certainly lookup is going to be a r/w lock or whatever and basically a wash. I vaguely buy that but would want to see numbers. But that said, the hash made of the heap due to the variable size nodes and lack of intrusivity is going to have exactly the opposite effect for any high performance implementation. Maybe Java doesn't play in that sandbox, I guess.
- _benedict 3y ago
  Garbage collectors are really nice for concurrent data structures, making lock-free algorithms very practical. Java's skip list does not require any locks for write, and requires essentially no synchronisation at all for reads (just suitable platform-dependent memory barriers). I believe reads are also wait free. There is a locality penalty for lookups, although I don't think this is core to skip-lists, just an impracticality of the Java language and how you can use its standard libraries. The variable size of the nodes is not a problem for the Java heap, due to how compacting garbage collectors work.

fourthark 3y ago

Pretty sure I learned about skip lists as a lock-free data structure that is relatively easy to reason about (but it was a while ago and I’m not finding confirmation in a quick search).

senderista 3y ago
Skip lists are relatively simple to make lock-free, while lock-free (even unbalanced) binary search trees are an absolute nightmare. https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...

twoodfin 3y ago

SingleStore (née MemSQL) uses a skiplist as its foundational in-memory data structure.