What are skiplists good for? • Hacker News Board

Re: What are skiplists good for?

#41

Post by timeinput » Sun, Apr 19, 2026, 3:59 PM UTC

hakanderyal wrote: post #15

boricj wrote: post #13

Earlier quoted context omitted.

AI is like a genie: be careful what you wish for or you'll get what you asked for. Lately at work I've done C++ optimization tricks like inplace_map, inplace_string, placement new to inline map-like iterators inside a view adapter's iterators and putting that byte buffer as the first member of the class to not incur std::max_align_t padding with the other members. At a higher architecture level, I wrote a data model…

This is also the reason why we have two polar opposite views on AI. “Slop generator” vs “Next best thing since sliced bread”. With SOTA models it all depends on how you drive them.

All my old software before AI was self documenting and didn't need comments -- it just was obvious. Today my prompts never make slop. I'm a really good driver.

Re: What are skiplists good for?

#42

Post by ignoramous » Sun, Apr 19, 2026, 4:12 PM UTC

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…

> Skiplists also win over balanced BSTs when it comes to concurrent access.

Balanced Skiplists search better than plain Skiplists which may skew (but balancing itself is expensive). Also, I've have found that finger search (especially with doubly-linked skiplist with million+ entries) instead of always looking for elements from the root/head is an even bigger win.

> ConcurrentSkipListMap has been in the standard library since Java 6 for exactly this reason and it holds up well under high contention

An amusing observation I lifted from OCaml's implementation (which inturn quotes Donald Knuth): MSBs of PRNG values have more "randomness" than LSBs (randomness affects "balance"): https://github.com/ocaml/ocaml/blob/389121d3/runtime/lf_skip...

---

Some neat refs from our codebase:

- Skip lists: Done right (2016), https://ticki.github.io/blog/skip-lists-done-right / https://archive.is/kwhnG

- An analysis of skip lists, https://eugene-eeo.github.io/blog/skip-lists.html / https://archive.is/ffCDr

- Skip lists, http://web.archive.org/web/20070212103148/http://eternallyco... / https://archive.is/nl3G8

Re: What are skiplists good for?

#43

Post by nz » Sun, Apr 19, 2026, 4:47 PM UTC

ozgrakkurt wrote: post #26

Some more links that are inside the article: - More info about skiplists: https://arxiv.org/pdf/2403.04582 - Performance comparison with B-tree ?: https://db.cs.cmu.edu/papers/2018/mod342-wangA.pdf - Other blog from Anthithesis about writing their own db: https://antithesis.com/blog/2025/testing_pangolin/ Also I find it a bit hard to understand the performance outcome of this setup. I know formats like parquet and da…

Back in 2014, I did an analysis of (single threaded) CPU-efficiency and RAM-efficiency of various data-structures (skiplists, slablists, avl-trees, rb-trees, b-trees):

https://nickziv.wordpress.com/wp-content/uploads/2014/02/vis...

I used whatever I could find on the internet at the time, so the comparison compares both algorithm and implementation (they were all written in C, but even slight changes to the C code can change performance -- uuavl performs much better than all other avl variants, for example). I suspect that a differently-programmed skip-list would not have performed quite so poorly.

The general conclusion from all this, is that any data-structure that can organize itself _around_ page-sizes and cache-sizes, will perform very well compared to structures that cannot.

Re: What are skiplists good for?

#44

Post by random3 » Sun, Apr 19, 2026, 4:57 PM UTC

aaa_aaa wrote: post #22

Almost nothing. My friend and I used it once (in a rather obscure problem). Then used simple lists with some tricks with better performance because of the locality etc.

You and your friend seem to make a dream team.

Re: What are skiplists good for?

#45

Post by ozgrakkurt » Sun, Apr 19, 2026, 5:15 PM UTC

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.

If it has a constant stride then that stride can align with something upstream and result in horrible performance

Re: What are skiplists good for?

#46

Post by CyberDildonics » Sun, Apr 19, 2026, 5:42 PM UTC

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…

You're right, but it's not popular to go against the premise of a post.

Re: What are skiplists good for?

#47

Post by reitzensteinm » Sun, Apr 19, 2026, 5:45 PM UTC

carlsverre wrote: post #32

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

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

Re: What are skiplists good for?

#48

Post by ahartmetz » Sun, Apr 19, 2026, 5:59 PM UTC

torginus wrote: post #36

dwdz wrote: post #18

Earlier quoted context omitted.

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.

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".

Re: What are skiplists good for?

#49

Post by einpoklum » Sun, Apr 19, 2026, 6:00 PM UTC

> Every insert would need to write to both systems, and since we want to analyze the data online (while new writes are streaming in) keeping the two databases consistent would require something like two-phase commit (2PC).

Not convincing. One can write the bulk data which is at first unused - no need to sync anything. Then one writes to the tree DB using, where each node only stores a key to the relevant data.

Re: What are skiplists good for?

#50

Post by maerF0x0 » Sun, Apr 19, 2026, 6:53 PM UTC

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…

A source: https://stackoverflow.com/a/46841708