[concurrency-interest] Asynchronous-nature of ConcurrentLinkedQueue

Vincent Gramoli vincent.gramoli at epfl.ch
Thu May 20 08:09:39 EDT 2010

> Date: Tue, 18 May 2010 08:17:46 -0400
> From: Doug Lea <dl at cs.oswego.edu>
> Subject: Re: [concurrency-interest] Asynchronous-nature of
> 	ConcurrentLinkedQueue
> To: concurrency-interest at cs.oswego.edu
> Message-ID: <4BF2856A.2020704 at cs.oswego.edu>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> On 05/18/10 08:03, Kai Meder wrote:
>> Hello
>> reading the Java-Docs of ConcurrentLinkedQueue I wonder what the
>> "asynchronous nature" mentioned in the size()-doc is?
>> "Beware that, unlike in most collections, this method is NOT a
>> constant-time operation. Because of the asynchronous nature of these
>> queues, determining the current number of elements requires an O(n)
>> traversal. "
> Because insertion and removal operations can occur concurrently
> (even while you are asking about the size), you generally
> don't want to ask about the size (although isEmpty is usually
> still useful). But if you do ask, the queue
> will provide an answer by counting up the elements. The
> answer it returns might not have much bearing to the actual
> number of elements upon return of the method.
> -Doug


I am currently working on some Software Transactional Memory solution for high-level Java abstractions that tolerate these issues. I have noticed that j.u.c.ConcurrentLinkedQueue.size() is not atomic. More precisely, even though the retuned value of the size method is not accurate at the time the method returns (as you mentioned), size() does not even provide the atomic snapshot semantics one would expect. I understand that its usage might be quite rare in practice, yet I was rather concerned by its "unexpected" semantics.

Consider the following example. If i threads run concurrently, each subsequently removing and inserting multiple times, say x times, while an (i+1)st tries to compute the size of the data structure, then the size may return in the worst case a value that has an offset error of i(x-1) even though the size experienced actually a variation of (more or less) i. I tested it.

Wouldn't it be clearer to add to the ConcurrentLinkedQueue.size() doc the sentence "Additionally, it is possible for the size to change during execution of this method, in which case the returned result will be inaccurate. Thus, this method is typically not very useful in concurrent applications." taken from ConcurrentSkipListMap.size().
Another reason is that this non-atomicity problem does not arise in ConcurrentHashMap.size() due to the stripping metadata, if I remember correctly.

Vincent Gramoli

More information about the Concurrency-interest mailing list