[concurrency-interest] Asynchronous-nature of ConcurrentLinkedQueue

Gregg Wonderly gregg at cytetech.com
Wed May 19 16:07:45 EDT 2010


David Holmes wrote:
> Greg,
> 
> Gregg Wonderly writes:
>> Doug Lea wrote:
>>> 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.
>> And I guess I am always curious why there is no "counter"
>> associated with the queue length.  It would provide the
>> same "rough" estimate as the "traversal" without the
>>  repeated overhead would it not?
> 
> Yes but at a cost to every queue operation to maintain that counter. This
> penalises the main queue operations to support another operation (size())
> that is for most intents and purposes completely useless.
> 
> The present code only penalises the misguided client that thinks they need
> to know the size.

I was guessing that it would be sufficient to use a volatile integer, and just 
live with the side effects of the data races, performing explicit zeroing when 
the queue was empty.

However, the very lose management of queue nodes and other optimizations that I 
see now after looking at the code, show that empty is not trivially detectable 
either.

Transactional CAS over multiple values would really be nice to have...

Gregg Wonderly


More information about the Concurrency-interest mailing list