[concurrency-interest] Skip Lists, Concurrent Skip Lists and
Concurrent Sorted Maps
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
> 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.
> Concurrency-interest mailing list