ArrayDeque constructor thread safety

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

ArrayDeque constructor thread safety

Martin Buchholz


[hidden email] wrote:

>>>On 7/21/06, R?mi Forax <[hidden email]> wrote:
>>>
>>>>To josh, perhaps i am tired, but for me,  allocateElements() always
>>>>allocates
>>>>a power of two size.
>>>
>>>Fair enough...
>>>
>>>>The other invariant is that head and tail must be
>>>>different
>>>>if the size is not empty, it seems to be the case.
>>>>So i continue to think that this implementation is valid.
>>>
>>>No.   Sun decided to make all collection "copy-constructors" robust to
>>>concurrent modification of the argument.  This is wise, in light of
>>>the fact that we now have true concurrent collections that cannot be
>>>globally locked.  So Martin's objection is valid.
>>sorry about my answer to martin, it was stupid.
>>ok, i understand now.
>>perhaps the third paragraph of java.util.Collection doc
>>can contain a line saying that copy constructor must rely on
>>the iterator of the collection taken as parameter.

If you look for tools that automatically find concurrency bugs
in Java, their No. 1 target was Vector(vector).  I was actually
more ambitious than relying on the iterator of the argument collection,
which is safe if the argument is a "concurrent" collection, but not
if it is a traditional "thread-safe" collection like Vector, since
the lock is not held while iterating.  The most reliable way to
get a snapshot of the elements in a collection with unknown concurrency
properties is to call its toArray method, and this is the
approach taken by Vector and ArrayList constructors.

ArrayDeque is still not safe in that sense.  ArrayDeque(vector)
may throw ConcurrentModificationException.  It's a bug.  Maybe.
Workaround: ArrayDeque(new ArrayList(vector))
Of course, we can easily fix ArrayDeque....if we don't care about
its performance.

Martin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ArrayDeque constructor thread safety

Remi Forax
Martin Buchholz a écrit :

> [hidden email] wrote:
>  
>>>> On 7/21/06, R?mi Forax <[hidden email]> wrote:
>>>>
>>>>        
>>>>> To josh, perhaps i am tired, but for me,  allocateElements() always
>>>>> allocates
>>>>> a power of two size.
>>>>>          
>>>> Fair enough...
>>>>
>>>>        
>>>>> The other invariant is that head and tail must be
>>>>> different
>>>>> if the size is not empty, it seems to be the case.
>>>>> So i continue to think that this implementation is valid.
>>>>>          
>>>> No.   Sun decided to make all collection "copy-constructors" robust to
>>>> concurrent modification of the argument.  This is wise, in light of
>>>> the fact that we now have true concurrent collections that cannot be
>>>> globally locked.  So Martin's objection is valid.
>>>>        
>>> sorry about my answer to martin, it was stupid.
>>> ok, i understand now.
>>> perhaps the third paragraph of java.util.Collection doc
>>> can contain a line saying that copy constructor must rely on
>>> the iterator of the collection taken as parameter.
>>>      
>
> If you look for tools that automatically find concurrency bugs
> in Java, their No. 1 target was Vector(vector).  I was actually
> more ambitious than relying on the iterator of the argument collection,
> which is safe if the argument is a "concurrent" collection, but not
> if it is a traditional "thread-safe" collection like Vector, since
> the lock is not held while iterating.  The most reliable way to
> get a snapshot of the elements in a collection with unknown concurrency
> properties is to call its toArray method, and this is the
> approach taken by Vector and ArrayList constructors.
>  
Another solution is to change the problem i.e. add a way to obtain
concurrency property at runtime
using an interface like RandomAccess or perhaps better using a runtime
visible annotation.

public enum ConcurrencyProperty **{
    NONE,
    SYNCHRONIZED,
    CONCURRENT
  }

  @Documented
  @Target(ElementType.TYPE)
  @Retention(RetentionPolicy.RUNTIME)
  public @interface ThreadSafe {
    ConcurrencyProperty value();
  }

In this case, "copy constructor" can choose to use AddAll or
toArray depending on the collection taken as argument.

I don't know if obtaining the value of an annotation at runtime
can be a performance bottleneck.

Another advantage of this solution is that a collection
marked with this annotation clearly documents
if a collection is or not thread safe.
Furthermore the compiler can try to
reports error in case of bad concurrency code
like with one

public void f() {
  Vector<String> v=new Vector();
  for(String s:v) {
     ...
  } // forget to synchronized the loop
} // the method is public.

Note that this solution also partially solve bug 6323374.

> ArrayDeque is still not safe in that sense.  ArrayDeque(vector)
> may throw ConcurrentModificationException.  It's a bug.  Maybe.
> Workaround: ArrayDeque(new ArrayList(vector))
> Of course, we can easily fix ArrayDeque....if we don't care about
> its performance.
>  
other workaround : use the annotation described above :)
> Martin
Rémi Forax

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest