4 ms·

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 l

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

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