5 ms·

Skip Lists: A Probabilistic Alternative to Balanced Trees

13 points by silentbicycle 18y ago

ntoshev 18y ago
It is a cool structure, but not a practical one because it is very cache-unfriendly. I'm surprised Wikipedia doesn't mention this.
- gaius 18y ago
  There are cases in which your dataset is larger than the cache, y'know.
  - seregine 18y ago
    That is the most common reason for using a cache in the first place, so you seem to be stating the obvious. Am I missing something? If I remember right, skip lists are unfriendly to caches (compared to balanced search trees) because they don't optimize locality of reference. This matters, for example, when your huge dataset is on disk and you're trying to cache the working set in memory. In a skip list, related elements don't end up on the same page as often, which means you have to read more data than you need from disk, and read from the disk more often.
    - gaius 18y ago
      Well yes, that is true, but if you happen to know upfront that you're going to be accessing your data randomly, and that for whatever reason you can't cache it all, then you should optimize for that case. If on the other hand, you know that you're going to have hotspots then you can size your cache accordingly. Choosing before you know (or have had a chance to observe) is a premature optimization.
      - johnm 18y ago
        But that's another argument of where skip list are not appropriate. Or do you have a real example?
        gaius 18y ago
        It is simply a matter of your cache hit ratio. If that is very low then you have two choices - increase the size of your cache, or use an algorithm that is less reliant on caching for predictable performance. The size of your cache is a pure price/performance calculation, "is it worth spending X to improve performance by Y%". By all means stick to caching/LRU/B*tree if that works for your application. A cache is a brute-force solution, tho', and it helps to have more than one tool in your bag.
        dreish 18y ago
        But by increasing the number of pointers by log n, you reduce your cache hit ratio, do you not? It would seem that the only time this doesn't matter is when you've long since blown past the CPU cache and your RAM cache hit ratio is going to be in the <5% range, with almost every access to the data structure resulting in disk accesses.
        gaius 18y ago
        Yes that is the case to which I am referring. I am often working with multi-terabyte datasets.
        johnm 18y ago
        You seem to be talking about something different than the skiplists and their effects on the cache. Unless you're building the actual chipsets, you don't get really any say in the amount and style of caching that your skiplist code is running on. Skiplists end up with a ton of pointer chasing and hence dramatically increase the pressure on the memory cache. There's no real, profitable way around that fact. You might want to look at the non-block hashtable work that I pointed to previously for a lot of information (and the actual code (in Java) is up on SF.net so you can actually try it out for yourself).
- johnm 18y ago
  In terms of cache friendly and massively scalable, check out Cliff's work on non-blocking hashtables: http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.h...
alexstaubo 18y ago
Skip lists are one of my favourite data structures. They're slower than balanced trees, but ridiculously simple to implement.
silentbicycle 18y ago
I meant to link to William Pugh's original paper when posting, but submit doesn't seem to take FTP links: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
BrandonM 18y ago
I've used a skiplist before to implement the "Six Degrees of Kevin Bacon" program in C++. It was easier to implement than a balanced tree, and it had similar performance, so it was pretty interesting and worthwhile. It took about 30 seconds to read in over 100K actors (if I remember correctly), but after that, searches were very fast. There are several negatives, however. One is that skiplists use about (lg n)/2 times as many pointers as a balanced tree, if you actually make your skiplist tall enough to be worthwhile. This could mean an extra MB or more of memory for a skiplist with 100K items in it. In some cases it could be that half of the memory consumed by the skiplist is the overhead involved in creating the skiplist. This is also true of hash tables that don't have many elements, of course, but with hash tables, the situation gets better as more items are added. With skiplists, the overhead remains high regardless of the number of items in the list. Another "problem" is that of standard libraries. Even C has a tsearch function (in search.h) that implements balanced search trees, and many other languages include balanced search trees as well. Balanced search trees have less overhead, both in terms of memory and performance. With a skiplist, you have to choose a few random numbers (on average) for every item added to the tree. Then with searches, you always have to start at the top (the "skippiest" part) with comparisons, working your way down towards the bottom until you figure out which node to jump to. With BSTs, it's just a single comparison and then a movement left or right. And of course, if your items are hashable, skiplists really lose out to hash tables, which have near-constant lookup time, very little overhead as the number of items in your table approaches the capacity, and implementations in nearly every language.
- silentbicycle 18y ago
  A constant time, yes, but that constant time may be significantly higher than expected. There are quite a few factors that can reduce hash tables efficiency. This post summarizes several potential problems with hash tables: http://enfranchisedmind.com/blog/2008/02/25/problems-with-hash-tables/ http://enfranchisedmind.com/blog/2008/02/25/problems-with-ha...
  - BrandonM 18y ago
    Okay, but which is slower, hashing a string and then looking into an array indexed at that position (possibly traversing a very short (2- or 3-item) list), or performing an average of 17 string comparisons (for the case of ~130,000 items)? In particular, the hashing approach gives similar lookup times for any item. The skiplist approach is dependent on the (random) structure of the built-up skiplist. A given item could be found after 2 pointer traversals, or it could take 30. Also disturbing is that as you get closer to the item you're looking for, the string comparisons take longer and longer (because the common prefixes are getting longer and longer). With a good hashing algorithm, similar strings will hash to different values. This means that even if 2 or 3 string comparisons have to be made (for strings that land in the same bucket), failing comparisons will be fast since they will likely fail on the first character.

13 points by silentbicycle 18y ago

It is a cool structure, but not a practical one because it is very cache-unfriendly. I'm surprised Wikipedia doesn't mention this.

gaius 18y ago
There are cases in which your dataset is larger than the cache, y'know.
- seregine 18y ago
  That is the most common reason for using a cache in the first place, so you seem to be stating the obvious. Am I missing something? If I remember right, skip lists are unfriendly to caches (compared to balanced search trees) because they don't optimize locality of reference. This matters, for example, when your huge dataset is on disk and you're trying to cache the working set in memory. In a skip list, related elements don't end up on the same page as often, which means you have to read more data than you need from disk, and read from the disk more often.
  - gaius 18y ago
    Well yes, that is true, but if you happen to know upfront that you're going to be accessing your data randomly, and that for whatever reason you can't cache it all, then you should optimize for that case. If on the other hand, you know that you're going to have hotspots then you can size your cache accordingly. Choosing before you know (or have had a chance to observe) is a premature optimization.
    - johnm 18y ago
      But that's another argument of where skip list are not appropriate. Or do you have a real example?
      - gaius 18y ago
        It is simply a matter of your cache hit ratio. If that is very low then you have two choices - increase the size of your cache, or use an algorithm that is less reliant on caching for predictable performance. The size of your cache is a pure price/performance calculation, "is it worth spending X to improve performance by Y%". By all means stick to caching/LRU/B*tree if that works for your application. A cache is a brute-force solution, tho', and it helps to have more than one tool in your bag.
        dreish 18y ago
        But by increasing the number of pointers by log n, you reduce your cache hit ratio, do you not? It would seem that the only time this doesn't matter is when you've long since blown past the CPU cache and your RAM cache hit ratio is going to be in the <5% range, with almost every access to the data structure resulting in disk accesses.
        gaius 18y ago
        Yes that is the case to which I am referring. I am often working with multi-terabyte datasets.
        johnm 18y ago
        You seem to be talking about something different than the skiplists and their effects on the cache. Unless you're building the actual chipsets, you don't get really any say in the amount and style of caching that your skiplist code is running on. Skiplists end up with a ton of pointer chasing and hence dramatically increase the pressure on the memory cache. There's no real, profitable way around that fact. You might want to look at the non-block hashtable work that I pointed to previously for a lot of information (and the actual code (in Java) is up on SF.net so you can actually try it out for yourself).
johnm 18y ago
In terms of cache friendly and massively scalable, check out Cliff's work on non-blocking hashtables: http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.h...

alexstaubo 18y ago

Skip lists are one of my favourite data structures. They're slower than balanced trees, but ridiculously simple to implement.

silentbicycle 18y ago

I meant to link to William Pugh's original paper when posting, but submit doesn't seem to take FTP links: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

BrandonM 18y ago

I've used a skiplist before to implement the "Six Degrees of Kevin Bacon" program in C++. It was easier to implement than a balanced tree, and it had similar performance, so it was pretty interesting and worthwhile. It took about 30 seconds to read in over 100K actors (if I remember correctly), but after that, searches were very fast. There are several negatives, however. One is that skiplists use about (lg n)/2 times as many pointers as a balanced tree, if you actually make your skiplist tall enough to be worthwhile. This could mean an extra MB or more of memory for a skiplist with 100K items in it. In some cases it could be that half of the memory consumed by the skiplist is the overhead involved in creating the skiplist. This is also true of hash tables that don't have many elements, of course, but with hash tables, the situation gets better as more items are added. With skiplists, the overhead remains high regardless of the number of items in the list. Another "problem" is that of standard libraries. Even C has a tsearch function (in search.h) that implements balanced search trees, and many other languages include balanced search trees as well. Balanced search trees have less overhead, both in terms of memory and performance. With a skiplist, you have to choose a few random numbers (on average) for every item added to the tree. Then with searches, you always have to start at the top (the "skippiest" part) with comparisons, working your way down towards the bottom until you figure out which node to jump to. With BSTs, it's just a single comparison and then a movement left or right. And of course, if your items are hashable, skiplists really lose out to hash tables, which have near-constant lookup time, very little overhead as the number of items in your table approaches the capacity, and implementations in nearly every language.

silentbicycle 18y ago
A constant time, yes, but that constant time may be significantly higher than expected. There are quite a few factors that can reduce hash tables efficiency. This post summarizes several potential problems with hash tables: http://enfranchisedmind.com/blog/2008/02/25/problems-with-hash-tables/ http://enfranchisedmind.com/blog/2008/02/25/problems-with-ha...
- BrandonM 18y ago
  Okay, but which is slower, hashing a string and then looking into an array indexed at that position (possibly traversing a very short (2- or 3-item) list), or performing an average of 17 string comparisons (for the case of ~130,000 items)? In particular, the hashing approach gives similar lookup times for any item. The skiplist approach is dependent on the (random) structure of the built-up skiplist. A given item could be found after 2 pointer traversals, or it could take 30. Also disturbing is that as you get closer to the item you're looking for, the string comparisons take longer and longer (because the common prefixes are getting longer and longer). With a good hashing algorithm, similar strings will hash to different values. This means that even if 2 or 3 string comparisons have to be made (for strings that land in the same bucket), failing comparisons will be fast since they will likely fail on the first character.