[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps

Joshua Bloch joshua.bloch@sun.com
Mon, 21 Jun 2004 11:39:13 -0700


   FYI, we left rank out of SortedMap because of its impact on the 
performance of various implementations (including red-black tree).  The 
only implementation on which it's pretty much free is splay tree, which 
(as you know) has other problems: read operations are mutative.



Bill Pugh wrote:

>> This is interesting. How much of a performance hit does it take to
>> maintain the fDistance on each of the links?
>> Assuming that there is an overhead you proposing to have this as an
>> option or in a subclass, or is it proposed that this will be in the base
>> implementation.
> We are still doing the base implementation, so we don't have 
> performance numbers
> yet on ranked skip lists. There are a couple of design and performance 
> challenges to
> doing an efficient implementation of skip lists in Java.
> But I suspect that if we did it, it would be a separate version. Maybe 
> not, it depends
> on the performance hit.
>     Bill
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest