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

Skip Lists Done Right

ticki.github.io

Post reply on HN
Print view View original

51–60 of 87 posts

Re: Skip Lists Done Right

#51

Post by qwertyuiop924 »

andars wrote: post #41
qwertyuiop924 wrote: post #38

Skip Lists. Seem handy for increasing access times on ordered lists... Any Lispers care to comment?

what's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.

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

Re: Skip Lists Done Right

#52

Post by mfukar »

bogomipz wrote: post #28

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

In the context of a DHT, F2F stands for friend-to-friend, i.e. authenticated nodes.

Re: Skip Lists Done Right

#53

Post by malisper »

gtrubetskoy wrote: post #25
catwell wrote: post #22

Earlier quoted context omitted.

Data 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/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.

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

Elaborating on gtrubetskoy comment, ziplists are doubly linked lists (of integers and strings) encoded into an array of bytes that stores the size of both the next and previous element so you can quickly find the location of the next/previous element. This makes ziplists space efficient and have great cache efficient, but expensive to insert into since you need to reallocate the array and shift a potentially large number of elements over every time you inset/delete. These properties make ziplists useful when they are small, but not so as they get larger, so Redis will switch to different implementations once the ziplists reach a certain size.

Interestingly, Redis lists are implemented as a double linked list of ziplists, where the size of each ziplists is bounded. This gives you good caching as the quicklist is being traversed, while limiting the cost of an insertion. Redis will also compress ziplists not near the edge in order to save space.

Re: Skip Lists Done Right

#54

Post by jychang »

reynoldsbd wrote: post #35

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

Berkeley did cover skip lists, along with a lot of other algorithms, both practical and esoteric.

Re: Skip Lists Done Right

#55

Post by nishs »

reynoldsbd wrote: post #35

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

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

Re: Skip Lists Done Right

#56

Post by nishs »

Java 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/concurre...

[2] http://people.csail.mit.edu/shanir/publications/LazySkipList...

Re: Skip Lists Done Right

#57

Post by vardump »

falcolas wrote: post #33
ComputerGuru wrote: post #7

Earlier quoted context omitted.

>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)?

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

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

To add, also memory access happens in chunks. Currently chunk (cache line) size is 64 bytes on almost all x86 and ARM CPUs. It's the smallest quantity of data you can read from or write to RAM.

CPUs can also efficiently prefetch when they detect sequential access patterns, so accessing large contiguous blocks of memory is preferable to achieve high performance.

Re: Skip Lists Done Right

#58

Post by Glyptodon »

reynoldsbd wrote: post #35

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

It was part of my normal university computer science data structures course. Was actually one of the structures we had to implement. Also, for all the "hard to get right" comments I remember them being much easier to write than RB Trees or B Trees.

Re: Skip Lists Done Right

#59

Post by bogomipz »

FroshKiller wrote: post #29
bogomipz wrote: post #28

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

My guess is friend-to-friend, i.e. a private peer-to-peer network.

I see - P2P, so something like Chord. Thanks.
Post reply on HN