[concurrency-interest] ArrayDeque constructor thread safety

Rémi Forax forax at univ-mlv.fr
Mon Jul 24 05:00:40 EDT 2006

Martin Buchholz a écrit :
> concurrency-interest-request at cs.oswego.edu wrote:
>>>> On 7/21/06, R?mi Forax <forax at univ-mlv.fr> 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 **{

  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

More information about the Concurrency-interest mailing list