10 ms·
Skip Lists Done Right
- gressquel 10y agoExcellent article, I really love algorithm and datastructure. if anyone else is interested like me, I recommend this book https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844 https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
- estomagordo 10y agoIt is also very handy if you need to flatten a small (< 2 kg) household pet.
- signa11 10y ago> It is also very handy if you need to flatten a small (< 2 kg) household pet. or your ego :)
- deleted 10y ago[deleted]
- StavrosK 10y agoOn the upside, it is really cheap by weight.
- johnlbevan2 10y agoIt would be bad to have a book about multiple trees which implemented less than 1 tree in its printed form.
- OJFord 10y agoImplemented? I don't think it implements tree, so much as inherits from tree.
- phhlho 10y agoI always say college was very practical learning as at different points in time I was able to kill a mouse with both algorithms (this very book) and computer architecture.
- alexhutcheson 10y agoIt took you 2 books to kill 2 mice, but I'm sure with more observations it would have been obvious that your approach was actually O(logN).
- ufo 10y agoI'm not a big fan of that book. For all its weight its still surprisingly informal.
- based2 10y agohttps://www.reddit.com/r/programming/comments/5iu8bd/an_analysis_of_skip_lists/ https://www.reddit.com/r/programming/comments/5iu8bd/an_anal...
- qznc 10y ago> I can't seem to find my favorite trick: deterministic (ie. without rng) skipping by linking on traversal instead of insert/delete. Says one comment. Can anyone explain that?
- mfukar 10y agoI initially thought it might be referring to deterministic skip lists (Munro, Papadakis, Sedgewick, http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/det...), but the "linking on traversal" part stumps me. Maybe it's referring to the top-down approach in section 3 of the paper.
- mac01021 10y agoIt sounds like they mean that, if you have all the data you want for your skiplist and all you need going forward is a read-only data structure for doing lookups, then you can put your data in order in a regular list and then build up the towers of skip links in deterministic fashion to get an optimally balanced distribution. Doesn't seem like much of a trick, though. If you can do that, then you can just stick it all in an array and bsearch to find things.
- jabr 10y agohttp://dl.acm.org/citation.cfm?id=139478 http://dl.acm.org/citation.cfm?id=139478 http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf http://www.cs.ucsb.edu/~ravenben/research/CS252/252Paper.pdf I have an old implementation (in C) of paged, deterministic skip lists here: https://github.com/jabr/olio/blob/master/skiplist.c https://github.com/jabr/olio/blob/master/skiplist.c https://github.com/jabr/olio/blob/master/skiplist.h https://github.com/jabr/olio/blob/master/skiplist.h
- brongondwana 10y agoLooks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip-and-beyond/ https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip... (except for the level choice. Which is a bit meh to me, because a write will probably trigger 3 fsyncs, so the cost of level choice is very low) That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk.
- ComputerGuru 10y ago>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?
- rawnlq 10y agoB-trees, LSM trees, or any data structure that's actually designed to be cache friendly. I think his claim that his optimizations can beat a b-tree is bullshit otherwise he would've shown benchmarks.
- brongondwana 10y agoI haven't written it yet. I suspect I can't beat b-tree in entirely random read workloads.
- falcolas 10y agoAdding to rawnlq's comments: Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks. The requirements for writing out a B-Trees to disk is in line with writing out chunks of data, which makes them very popular (and performant) with database implementations. And this doesn't cover how performant CPUs are at performing operations over a contiguous list of data. The complexity may be O(n), but the implementation introduces a fractional constant which can outperform a O(log(n)) algorithm which involves cache misses.
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- quinnftw 10y agoSomething to note: you state that BST's have logarithmic time in order successor, but many implementations use threaded binary trees which provide an amortized constant successor operation. Great article though.
- grifter 10y agoRedis uses a skip list (doubly linked) implementation for sorted sets, here are antirez's (BDFL) comments as to why from 7 years ago: There are a few reasons: 1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees. 2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees. 3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
- catwell 10y agoData structures in Redis have evolved a bit in the last 7 years. One of the main workhorses is indeed something called a "ziplist". The implementation (especially the format description at the top) is worth a read: https://github.com/antirez/redis/blob/90a6f7fc98df849a9890ab6e0da4485457bf60cd/src/ziplist.c https://github.com/antirez/redis/blob/90a6f7fc98df849a9890ab... For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
- gtrubetskoy 10y agoI have not looked at Redis code in eons, but I think it's not exactly true - all the structures are there, it's just that redis will favor ziplist for the very small ones. A ziplist is a list of compact varying length integers (or strings) where only the bits that make a difference are stored (I contributed the 24-bit version to Redis[1]). The argument is that a sequential search over a small data structure always wins over more complex things like hash tables, skiplists, etc. As you get more data, Redis will switch to using skiplists or whatever - there is a config setting for that (-max-ziplist-entries and -max-ziplist-value). [1] https://github.com/antirez/redis/commit/5a86ab47995586f0a0ef18472eafd6e9131644c1#diff-b109b27001207a835769c556a54ff1b3 https://github.com/antirez/redis/commit/5a86ab47995586f0a0ef...
- LeandroLovisolo 10y ago[Shameless plug] I've written a skip list implementation you can play with from the browser: http://leandro.me/MyDataStructures/#/data-structures/skip-list http://leandro.me/MyDataStructures/#/data-structures/skip-li... Tip: click "Insert a random item" a bunch of times to populate the (initially empty) skip list.
- airesQ 10y agoSkip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness). Funnily enough, for my case, I managed to do without a RNG just fine. I just have an element that is of tallness 'k' every 2^(k*3) insertions (e.g. every 8th insertion is 1 level tall; every 64th insertion is 2 levels tall; and so on). For my particular pattern of insertions, this proved to be more than enough, and and simplified things a little bit.
- OskarS 10y ago> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is the premise of the linked article, after all). Using a skip list is frequently the better choice for performance and memory reasons (especially if you're iterating through the list), but they are not necessarily simpler data structures.
- airesQ 10y agoI did a brief survey before deciding to go with skip lists, and found them to be easier to grasp and reason about. (e.g. there is no need to balance trees; a skip list is very similar to a linked list, and linked lists are very simple). I remember somebody saying that "in a sane world skip lists would always have been discovered before red-black trees". This historical accident (skip lists were only discovered 1989; while rb-trees date back to the 1970s) is probably the reason why skip list use is not more widespread, and seen as somewhat exotic at times. (AVL and Splay-trees also predate skip lists.)
- kazinator 10y agoSkip lists are just B+ trees in disguise. Look at the basic diagram here. https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree See how there is an "express lane" containing just (3 5), and the lower layer contains the entire (1 2 3 4 5 6 7) list? The main difference is that it's a combination of arrays and links rather than parallel lists.
- dreamcompiler 10y agoAnother nice thing about skip lists is that you can traverse them backwards without adding backpointers with a recursive algorithm and an O[logn] size stack.
- jonstewart 10y agoAren't skip lists more-or-less essential for indexed search engines? I wouldn't say they're uncommon considering how much indexed search surrounds us. e.g., http://lucene.apache.org/core/6_3_0/core/org/apache/lucene/codecs/MultiLevelSkipListReader.html http://lucene.apache.org/core/6_3_0/core/org/apache/lucene/c...
- _wmd 10y agoMost interesting aspect of the article was the last section and first comment, linking to SkipNet: http://research.microsoft.com/en-us/um/people/alecw/usits-2003.pdf http://research.microsoft.com/en-us/um/people/alecw/usits-20... Ideas like SkipNet are what differentiates a hack like me from genuinely smart people who can look at the definition of in-memory data structure and spot properties useful to an Internet-sized system
- bogomipz 10y agoThe author states in the "Extra Remarks" section: "Performance is mostly about the same, but skip lists are more DoS resistant if you make sure that all links are F2F." Can someone tell me what F2F stands for? I am not familiar with this acronym.
- FroshKiller 10y agoMy guess is friend-to-friend, i.e. a private peer-to-peer network.
- bogomipz 10y agoI see - P2P, so something like Chord. Thanks.
- mfukar 10y agoIn the context of a DHT, F2F stands for friend-to-friend, i.e. authenticated nodes.
- manigandham 10y agoMemSQL (distributed relational database with in-memory tables) uses skip lists: http://blog.memsql.com/the-story-behind-memsqls-skiplist-indexes/ http://blog.memsql.com/the-story-behind-memsqls-skiplist-ind...
- bogomipz 10y agoSo my takeaway is that two main use cases for this DS are: 1: as an alternative to a distributed hash tables 2: as an alternative to a self-balancing tree such AVL tree etc. Are there any other common uses cases for skip lists?
- phpnode 10y agoSome memory allocators use them for tracking free blocks because insertions/removals are cheap and they're good at best-fit style searches.
- reynoldsbd 10y agoSkip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic. It's a shame that universities (or at least mine) don't teach more interesting algorithms like this... it would make the algorithms/data structures coursework so much more interesting.
- nishs 10y agoUT Austin's multicore computing course had an optional project to benchmark concurrent skip lists or implement faster skip list algorithms. My group aimed to improve element access times by boosting the height of frequently accessed elements.
- ragnatest001 10y agoWUSTL does teach Skip List. We spent a good two weeks learning about it. Intro, analysis, lab, test about Skip List. It's very cool and hard to get right.
- pspeter3 10y agoYeah, I was just thinking about that 241 lecture. I do feel like we did the naive version though
- woodruffw 10y agoMy University (UMD) does, but that might only be because Bill Pugh teaches/taught here.
- superdaniel 10y agoGeorgia Tech definitely teaches it in the intro data structures and algorithms course. I don't remember if we had to implement it, but it definitely came up in lecture.
- BenTheElder 10y agoWe had to implement them when I took it with Dr. Waters at least (Summer 2015). CS 1332 is a pretty good intro course.
- cryptarch 10y agoArchived: https://archive.fo/H7F9e https://archive.fo/H7F9e The site doesn't work without scripts and trips up links2, so you can use the archive link instead (it works without scripts).
- qwertyuiop924 10y agoSkip Lists. Seem handy for increasing access times on ordered lists... Any Lispers care to comment?
- andars 10y agowhat's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.
- qwertyuiop924 10y agoSkip lists allow for that, sort of. In Lisp, most people would just, you know, not use a list for that. You can do that, you know... The only reason I asked about lispers is that lispers really like lisps, and I was curious if any of them had implemented skip lists for some reason, and if so, how.
- andars 10y ago> ... just, you know ... you know ... Yes, I know. Do you? You made the suggestion that skip lists are inferior to ordered lists, not me. (good for "increasing access times on ordered lists") I'm still perplexed as to your rationale for that statement.
- qwertyuiop924 10y agoNo, I didn't, AFAIK. I'm baffled as to where you drew that from...
- cronjobber 10y agoMaybe because you wrote "increasing access times", which could be read as "skip lists are slower." Not what you meant, probably.
- andars 10y ago
- TimonKnigge 10y agoThe pseudocode + example given for the initial implementation of 'insert' doesn't seem right, no 'below' connection is made between the two '13' nodes. The way to fix this would be to let 'insert' return the node inserted at the given level. There already are a few returns in the 'insert' pseudocode right now, but it doesn't seem like anything is being returned right now. Something like this: -- Recursive skip list insertion function. define insert(elem, root, height, level): if right of root < elem: return insert(elem, right of root, height, level) else: if level = 0: new ← makenode elem old ← right of root right of root ← new right of elem ← old return new else: if level ≤ height: new ← makenode elem old ← right of root right of root ← new right of elem ← old below new ← insert(elem, below root, height, level - 1) return new else: return insert(elem, below root, height, level - 1) Or more simply: define insert(elem, root, height, level): if right of root < elem: return insert(elem, right of root, height, level) elif level > height: return insert(elem, below root, height, level - 1) else: new ← makenode elem old ← right of root right of root ← new right of elem ← old if level > 0: below new ← insert(elem, below root, height, level - 1) return new
- ddebernardy 10y agoMight anyone familiar with both data structures be able to briefly explain how this actually differs from a B-tree?
- aidenn0 10y agoThere are a lot of differences; here's a couple: A skip list node contains one key and has a random fanout; a B-tree node contains 1-N keys and has fanout equal to <number of keys> - 1. A B-tree is guaranteed amortized log(N) lookup/insert/delete time, a skip-list has a high probability of a log(N) lookup/insert/delete time, but does not guarantee it. The advantage of skip lists over b-trees is that they can have a smaller constant-factor, and are more cache friendly under many workloads.
- JoKer_handsome 10y agoI was set to do some effects on After Effects anyone about this experience yourself more questions. Here are some things I can do (https://goo.gl/Ada79j https://goo.gl/Ada79j)
- hoprocker 10y agoI just came across skip lists as part of a sliding-window aggregator in Apache Samza's metrics system[0]. So cool! Being able to work with a range of values in somewhere between O(1)and O(log n) time, while still providing ordered key/value mappings, is great. Dug through java.util.concurrent looking for more structures, but this seems to be the most interesting of the bunch. [0] https://github.com/apache/samza/blob/master/samza-api/src/main/java/org/apache/samza/metrics/SlidingTimeWindowReservoir.java https://github.com/apache/samza/blob/master/samza-api/src/ma...
- nishs 10y agoJava has a lock-free concurrent skip list in the ConcurrentSkipListMap class [1]. Herlihy et al. claim that existing skip list algorithms (including the Java implementation) are complicated, and instead provide a supposedly faster implementation [2]. The two techniques they use are: - Optimistic traversal of lists without grabbing a lock: Only when it arrives at the item being seeked, it grabs the lock and validates that the list is unchanged. - Lazy deletion: marking a node as deleted and removing it from the list later. [1] https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html https://docs.oracle.com/javase/8/docs/api/java/util/concurre... [2] http://people.csail.mit.edu/shanir/publications/LazySkipList.pdf http://people.csail.mit.edu/shanir/publications/LazySkipList...
- asimjalis 10y agoWhat framework are you using to publish the blog?
- reynoldsbd 10y agoFooter says that Hugo is being used. https://gohugo.io/ https://gohugo.io/
- clarkmoody 10y agoLooks like Hugo[1] running the Bleak[2] theme. [1] http://gohugo.io/ [2] https://github.com/zenithar/hugo-theme-bleak
- gct 10y agoMaybe off-topic, but thanks for putting what tools you used to do your illustrations with, always happy to see what people are using for that.
- nickpeterson 10y agoDia and TiKZ, they make the diagrams I produce seem a bit..rough..
- CountHackulus 10y agoWhile I really do like this article and the really interesting techniques it showed me, I'm bothered by the fact that they constantly mention performance but there's not a single benchmark on that page. It's not that I don't believe that these are huge theoretical gains, it's just that I'd like to see how these perform in practice compared to other approaches.
- rw 10y agoI've read this page before, and again today, and I still don't understand how these unrolled lists are supposed to work in practice. Based on the author's example at https://i.imgur.com/FYpPQPh.png https://i.imgur.com/FYpPQPh.png, how do you take an unrolled skiplist that has a bottom row like this: [1,2,3] -> [4,5,_] -> [7,8,9] And insert 2.5? An inevitable tree restructuring would have to occur, which vastly complicates the insertion logic.
- eternalban 10y agoThat first chunk will get split, 3 will get copied to new chunk, and list is restructured. I think the selling point here is you paid this price but get dividends on reduced cache misses in the future.
- rw 10y agoInteresting. Whether that approach is efficient depends entirely on the workload. That complicates the analysis. (And one of the major benefits of skiplists is that the analysis is supposed to be simple.)