[concurrency-interest] RE: ConcurrentSkipList issues:

Yechiel Feffer yechielf at gigaspaces.com
Mon Apr 25 09:37:19 EDT 2005


"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.)
"
Yes, I can wrap nulls, but surly you agree that the more "natural" (and
nice) way of doing it is in the CSL and not in every calling app' 


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

Hmmm...
I cant see the real diff' between a user traversing an iterator when the
iteration set is subject to concurrent moditications ( deletions etc -like
the case in CSL), and between supplying a handle. A handle (which can be
node(s) information of the element) is just a way of saving an index scan,
and in terms of consistency seems to me quite equivalent to "Next" operation
on a concurrent iterator where the "current" position might have been
deleted between the prev' "next" call to the next "next" call.
but if its impossible to implement in CSL- we will have to do without it 

Yechiel   

-----Original Message-----
From: Doug Lea [mailto:dl at cs.oswego.edu]
Sent: Monday, April 25, 2005 14:11
To: Yechiel Feffer
Cc: concurrency-interest at altair.cs.oswego.edu
Subject: Re: ConcurrentSkipList issues:


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

-Doug
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20050425/5477c93d/attachment.htm


More information about the Concurrency-interest mailing list