Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What are skiplists good for?

antithesis.com

Post reply on HN
Print view View original

31–40 of 75 posts

Re: What are skiplists good for?

#32

Post by carlsverre »

(I used to work at SingleStore, and now work at Antithesis)

SingleStore (f.k.a. MemSQL) used lock-free skiplists extensively as the backing storage of their rowstore tables and indexes. Adam Prout (ex CTO) wrote about it here: https://www.singlestore.com/blog/what-is-skiplist-why-skipli...

When SingleStore added a Columnar storage option (LSM tree), L0 was simply a rowstore table. Since rowstore was already a highly optimized, durable, and large-scale storage engine, it allowed L0 to absorb a highly concurrent transactional write workload. This capability was a key part of SingleStore's ability to handle HTAP workloads. If you want to learn more, take a look at this paper which documents the entire system end-to-end: https://dl.acm.org/doi/10.1145/3514221.3526055

Re: What are skiplists good for?

#34

Post by torginus »

>What are skiplists good for

In practice, I have found out, nothing much. Their appeal comes from being simpler to implement than self-balancing trees, while claiming to offer the same performance.

But they completely lack a mechanism for rebalancing, and are incredibly pointer heavy (in this implementation at least), and inserts/deletes can involve an ungodly amount of pointer patching.

While I think there are some append-heavy access patterns where it can come up on top, I have found that the gap between using a BST, a hashtable, or just putting stuff in an array and just sorting it when needed is very small.

Re: What are skiplists good for?

#35

Post by torginus »

marginalia_nu wrote: post #20
bob1029 wrote: post #11

On practical machines they aren't good for much. To access a value in a skip list you have to dereference way more pointers than in a b+ tree. On paper they're about the same, but in practice the binary tree will tend to outperform. You get way more work done per IO operation.

Skiplists are designed for fast intersection, not for single value lookup (assuming a sane design that's not based on linked lists, that's just an educational device that's never used in practice). They are extremely good at intersections, as you can use the skip pointers in clever ways to skip ahead and eliminate whole swathes of values. You can kinda do that with b-trees[1] as well, but skip lists can beat them out…

I don't understand how they differ in this regard from range trees, which they essentially are, just their method of construction is different.

Things like BSP trees are very good at intersections indeed, and have been used for things since time immemorial, but I think the skiplist/tree tradeoff is not that different in this domain.

Re: What are skiplists good for?

#36

Post by torginus »

dwdz wrote: post #18
ahartmetz wrote: post #2

Skiplists have some nice properties - the code is fairly short and easy to understand, for one. Qt's QMap used to be skip list based, here's the rationale given for it: https://doc.qt.io/archives/qq/qq19-containers.html#associati...

It seems like Qt went from red-black tree to skip list in Qt4 and back to red-black tree in Qt5.

yeah it turns out that complex code, when its properly encapsulated and implemented in a bug-free manner, is not such a cost after all.

A correct skiplist is easier to NIH than a correct red-black tree (which for me was the final boss of the DS class in college), but has performance edge cases a red-black tree doesnt, if you treat it like a search tree.

Re: What are skiplists good for?

#37

Post by torginus »

akoboldfrying wrote: post #21
locknitpicker wrote: post #4

FTA: > Skiplists to the rescue! Or rather, a weird thing we invented called a “skiptree”… I can't help but wonder. The article makes no mention of b-trees if any kind. To me, this sounded like the obvious first step. If their main requirement was to do sequential access to load data, and their problem was how to speed up tree traversal on an ad-hoc tree data structure that was too deep, then I wonder if their problem…

IIUC, the tree structure is the very thing they're trying to store and query -- it's not merely an artefact of a data structure that they're using to store something else (the way a B+ tree or binary tree used to store, say, a set of product names would be). If their tree has long paths, it has long paths.

The nice thing with skip lists, is all 'rungs' of the list are stored in an array for a given node, so there's a lot less pointer chasing.

The not so nice thing about it is that you have to pre-guess how deep your tree will be and allocate as many slots, or otherwise itll degrade into a linked list when you run out of rungs, or you end up wasting space.

Post reply on HN