[concurrency-interest] Re: ConcurrentSkipList issues:

Doug Lea dl at cs.oswego.edu
Mon Apr 25 08:11:17 EDT 2005

Yechiel Feffer wrote:
> Hi
> I am considering the usage of ConcurrentSkipList (here CSL) - it will be 
> (once mustang is released) the only "ordered" concurrent set.

(You can also put read/write locks around a TreeMap, which
is sometimes a good alternative, depending on usage patterns.)

> I have some questions/wishes regarding it
> #1) Iterators: they are weakly consistent, which is fine. But the point 
> I want to clarify is: When I create an iterator, am I guaranteed to get 
> all the elements which were part of the iteration set when the iterator 
> was created and are still valid (- not deleted) when I exhaust the 
> iteration set ? 

Yes, this is exactly what weakly consistent iterators (of
all kinds) guarantee.

> #2) null values- why cant they be used ? 

Because I refuse to support the use of nulls in sorted maps/sets!
Allowing nulls makes no conceptual sense and makes things slower.

(Digressing: The dubious virtue of allowing nulls in some other
collections like HashMap makes all users pay (a little, but still
noticeable) for a "feature" that I think does more harm than good,
by masking what are almost always usage errors. Allowing nulls was also
the source of bugs and anomolies in TreeMap and TreeSet, which
do allow them, over my objections. All this reinforces my belief
that only those users who want special handling for nulls should
have to pay for it, by wrapping nulls themselves, which is one
form of the Null Object Pattern, which you might consider using.)

> #3) wishful performance optimization- is it possible to create an 
> additional set of apis to the CSL which will return a "handle" from the 
> put api . The handle will be a direct "pointer" to the CSL so when I 
> want to remove a key from the CSL (assuming I keep the handles) I can 
> render this handle and  spare the need for a redundant search . Same is 
> true for replace.

I/We thought about this. But there's not a good plan of attack
for supporting it. In a concurrent class, any such handles
would need to be consistency-checked to deal with asynchronous
updates and deletions. And all approaches I know for doing
this in ConcurrentSkipLists would require at least as much time
as just retraversing. (Skip lists are not special about this. The
same issue arises in most concurrent data structures.)


More information about the Concurrency-interest mailing list