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

Bill Pugh pugh@cs.umd.edu
Mon, 21 Jun 2004 13:41:04 -0400


> 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