[concurrency-interest] A question about ConcurrentLinkedQueue.remove()

Dave Clausen daveclausen at gmail.com
Mon Jun 8 15:40:36 EDT 2009


FYI I filed a bug report with Sun a while back that basically covers
the same ground as this thread:

http://bugs.sun.com/view_bug.do?bug_id=6785442

There's not really any new information there.  I'm only mentioning it
so you can close out the ticket when you make the fix.  I apologize if
you've already got it covered.

Thanks,
Dave Clausen

On Fri, Feb 27, 2009 at 12:35 PM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
> I agree that poll should be coded as:
>
>    if (item != null && first.casItem(item, null)) {
>        return item;
>    }
>
> That's how I read "equivalently" in the spec.
>
> Note that this remove method is specified by Collection, and the two
> phrasings were equivalent before concurrent collections arrived on the
> scene.  The object was either present *and* removed, or it wasn't, or there
> was a ConcurrentModificationException.
>
> The proposed implementation is also more testable.  It should be the case
> that the number of items inserted is equal to the number of successful polls
> plus the number of successful removals.
>
> Joe
>
> On Fri, Feb 27, 2009 at 3:55 AM, Doug Lea wrote:
>
>> James Gan wrote:
>>
>>>
>>> Let's consider following scenario. Assume thread A is removing the element
>>> inside first node and thread B is popping, it seems to me that both of them
>>> can succeed.
>>>
>>
>> This is a byproduct of a spec decision that is worth
>> revisiting. The question is: What should be the return value
>> of remove when the item was present on entry but not on return
>> of the method? The spec is a little vague ...
>>
>>  Returns true if this queue contained the specified element (or
>>  equivalently, if this queue changed as a result of the call).
>>
>> ... especially since the "equivalently" clause is not exactly
>> equivalent under most people's interpretations! If the item was in
>> the process of being polled, then you might (and you did!) conclude
>> that the queue did not change as a result of the remove call but
>> of the poll. As David mentioned, your interpretation, which
>> is probably more common, could be ensured by using
>> casItem in poll. We probably ought to do this, and then strengthen
>> and clarify the spec/javadoc.
>>
>> While I'm at it: jsr166y.LinkedTransferQueue, which can be used as
>> a plain ConcurrentLinkedQueue, not only doesn't have this
>> issue, but also includes an internal node cleanup algorithm,
>> which prevents the accumulation of embedded cancelled/removed nodes,
>> so is always preferable if you do this a lot. In fact, for Java7.
>> there is no reason not to replace the internals of CLQ by delegating
>> to LTQ, so we will probably do this.
>>
>> -Doug
>



More information about the Concurrency-interest mailing list