4 ms·

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