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

61–70 of 75 posts

Re: What are skiplists good for?

#61

Post by ahartmetz »

torginus wrote: post #56
ahartmetz wrote: post #48

Earlier quoted context omitted.

I think it was more about binary size. There are a few sentences in the Qt containers documentation about them being "optimized to minimize code expansion".

I mean that could mean a lot of things. By default, in C++, an std::vector and std::vector are two entirey separate classes with distinct methods getting compiled, even though in this particular the methods would be identical. Moreover, since templates are in headers, every object file gets their own compiled copy. I'm sure there's some cleverness in there to mitigate the problem somewhat, but the problem still funda…

Well, you can do two or three main things:

- Use an algorithm and implementation that needs a small amount of code for each instance (that is where the skip list is useful)

- Have a shared "out of line" (not inline) implementation for bulky parts of the implementation, where possible

- Support the compiler + linker feature to merge identical functions by making code identical between template instantiations of similar enough types

Re: What are skiplists good for?

#62

Post by oersted »

mrjn wrote: post #3

skiplists form the basis of in-memory tables used by LSM trees, which are themselves the basis of most modern DBs (written post 2005).

Not sure if it's true that LSM trees are so dominant, it was a bit of a fad a few years ago during the NoSQL hype. They can be a good default for concurrent write-heavy workloads like analytics or logging, but they can be tricky to tune.

The good-ol' copy-on-write memmapped B-Tree is still widely used, even on newer key-value stores like redb (I am more familiar with the Rust ecosystem), and it claims to outperform rocksdb (the go-to LSM-tree kvs) on most metrics other than batch writes [1] (although probably biased).

LMDB is still widely used (one of the main classic B-tree kvs), and Postgres, SQLite and MongoDB (WiredTiger), among others, are still backed by B-Tree key-value stores. The key-value storage backends tend to be relatively easy to swap, and I don't know of major efforts to migrate popular databases to a LSM tree backend.

[1] https://www.redb.org/post/2023/06/16/1-0-stable-release/

Re: What are skiplists good for?

#64

Post by senderista »

torginus wrote: post #34

>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…

Lock-free BSTs or b-trees exist only in research papers, but lock-free skiplists are straightforward to implement.

Re: What are skiplists good for?

#65

Post by senderista »

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…

Treaps can handle parallel set operations very efficiently:

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf

Re: What are skiplists good for?

#66

Post by nulltrace »

cremer wrote: post #16

Redis sorted sets are probably the most widely deployed example. Redis uses a skiplist for range queries and ordered iteration paired with a hash table for O(1) lookups. Together they cover the full API at the right complexity for each operation Skiplists also win over balanced BSTs when it comes to concurrent access. Lock-free implementations are much simplier to reason about and get right. ConcurrentSkipListMap has…

Rebalancing is what really kills you. A CAS loop on a flat list is pretty straightforward, you get it working and move on. But rotations? You've got threads mid-insert on nodes you're about to move around. It gets ugly fast. Skiplists just sidestep the whole thing since level assignment is basically a coin flip, nothing you need to keep consistent. Cache locality is worse, sure, but honestly on write-heavy paths I've never seen that be the actual bottleneck.

Re: What are skiplists good for?

#67

Post by akoboldfrying »

torginus wrote: post #37
akoboldfrying wrote: post #21

Earlier quoted context omitted.

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.

You don't really have to pre-guess the number of rungs -- you can just have a linked list of them and add a new rung "on top" when necessary, because you always start at the top rung, and only ever move sequentially along a rung, or step down to the rung immediately below. The overhead of pointer chasing is pretty small because there will only be O(log n) rungs; you move between rungs roughly often as you move along them.

Also you can freely choose the "compaction rate" (base of that logarithm) to be something other than 2 -- e.g., choosing 4 means half as many rungs (but ~twice as much wandering along each rung).

Re: What are skiplists good for?

#68

Post by outpost_mystic2 »

torginus wrote: post #56
ahartmetz wrote: post #48

Earlier quoted context omitted.

I think it was more about binary size. There are a few sentences in the Qt containers documentation about them being "optimized to minimize code expansion".

I mean that could mean a lot of things. By default, in C++, an std::vector and std::vector are two entirey separate classes with distinct methods getting compiled, even though in this particular the methods would be identical. Moreover, since templates are in headers, every object file gets their own compiled copy. I'm sure there's some cleverness in there to mitigate the problem somewhat, but the problem still funda…

Sorry if this is a dumb question but wouldn't vector and vector generate different code on get/set? Since floats go in different registers/need different instructions to load/store them to memory? Or is it something like, actually all of the std::vector functions technically operate on T&, and manipulating the pointers can use the same code, and really it's the optimizer that has to think about float vs int registers or something

Re: What are skiplists good for?

#69

Post by EGreg »

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…

Actually, prolly trees are probably best for intersections. You can use bloom filters as a first pass

Re: What are skiplists good for?

#70

Post by mananaysiempre »

senderista wrote: post #65
marginalia_nu wrote: post #20

Earlier quoted context omitted.

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…

Treaps can handle parallel set operations very efficiently: https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf

Maestro Tarjan tells us skiplists and treaps are very nearly the same thing: https://arxiv.org/abs/1806.06726. I don’t see how to transpose TFA’s extension of the former to the latter, though.
Post reply on HN