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

71–75 of 75 posts

Re: What are skiplists good for?

#71

Post by krackers »

torben-friis wrote: post #17

Could someone provide intuitive understanding for why the "express lanes" in a skip list are created probabilistically? My first instinctive idea would be that there is an optimal distance, maybe based on absolute distance or by function of list size or frequency of access or whatever. Leaving the promotion to randomness is counter intuitive to me.

Maybe for very high-level intuition, it's vaguely similar to other randomized algorithms that you want to minimize the worst-case on expectation and the easiest way to do so is to just introduce randomness (think quicksort, which is N^2 worst case with a badly chosen pivot). Your idea of there being an optimal distance is similar to the concept of "derandomization" maybe, e.g. in Quicksort there are deterministic pivot selection algorithms to avoid the worst case. But all of those require much more effort to compute and require an algorithm whose output is a function of the input data. Whereas randomly picking a pivot or randomly creating express lanes is simpler and avoids the data dependency (which is important since unlike sorting, the data isn't fixed ahead of time).

Re: What are skiplists good for?

#72

Post by namibj »

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…

B(+)Trees do actually admit a fast intersection (they offer a way more powerful projected-to-shared-keyspace mutual index join, technically it's even able to do antijoin but that'll actually modify iteration more than a very genericalized inner join; basically whenever you look at a key in any one of the involved indices you project it to a shared keyspace before doing the comparison-based-search things):

You get cache locality from the upper layers, and for navigation basically `let mut head = keyspace.min(); 'outer: while(!cursors[0].finished()){ for(&mut cursor in cursors.iter_mut()) { let new_head = cursor.seek_to_target_or_next_after_if_none_match(head); if (head != new_head) {continue 'outer; }} /* passed all without seeking past target on any one */ output_fun(head, cursors.iter().map(|x| x.val())); }`. If you want you can do the inner loop's seeks concurrently, which helps if those are IO latency bound and you can afford to waste absolute IOPS on eagerly doing that. You'll want to locally compute the max() of those returned and assign that to `head`. Imagine the cursors are lambda-parametrized to feel like they operate on the projected shared keyspace.

If the keys are a bitstring prefix suited to a binary prefix trie you can actually intersect that way, it's beyond worst case optimal when multiple key columns are involved. Sadly any simple implementation strategies of those algorithms have prohibitive external-memory-machine coefficients for their nominally poly-logarithmic IOPS, due to involvement of combinatorial explosion / curse of dimensionality in search tree/trie structures. They do work though. C.f. "Tetris-LoadBalanced"/"Tetris-Reordered".

The latter even tames one index containing "all" even numbers and the other "all" odd numbers, well, matters more if you involve 3+ columns :D

Re: What are skiplists good for?

#73

Post by reitzensteinm »

carlsverre wrote: post #55
reitzensteinm wrote: post #47

Earlier quoted context omitted.

At the intersection of these two topics, does Antithesis have any capabilities around simulating memory ordering to validate lock free algorithms?

We support thread-pausing via instrumentation. This can cause threads to observe different interleavings, which can help uncover bugs in concurrent algorithms. At this time, we don't perform specific memory model fault injection or fuzzing.

I wrote a library called Temper, which simulates the Rust/C++ memory model with atomics in a similar way to Loom. But it goes much deeper on that narrow domain, and to my knowledge it's the most accurate library of its kind with the largest set of test cases.

If you simulate using mock CPU instructions like memfence or LL/CS there's no guarantee your model fits your ultimately executed program.

Unless of course, you do something like antithesis and directly test what compiled. It's an interesting alternative world.

I've taken the liberty of adding you to LinkedIn - would love to grab a drink next time you're in the SF Bay area.

https://github.com/reitzensteinm/temper

Re: What are skiplists good for?

#74

Post by zelphirkalt »

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…

Binary search trees, at least the ones I am thinking of, have known purely functional, and therefore lock free implementations. I am currently looking into AVL trees and they don't seem that complicated of an implementation for example.

Re: What are skiplists good for?

#75

Post by zelphirkalt »

senderista wrote: post #64
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.

Mainly functional paradigm languages disagree with this.
Post reply on HN