[concurrency-interest] ConcurrentLinkedQueue CAS-like poll/iterator remove

Benedict Elliott Smith belliottsmith at datastax.com
Wed Feb 5 09:13:58 EST 2014


>
> It has always been non-blocking. Maybe you are thinking of a different
> Queue?


My mistake, sorry.


> But considering that nearly all Queue iterators are intrinsically slow
> anyway (processing the internal items of a concurrent queue is an
> unnatural act),


There are two problems with this:

1) it is much slower still, making iterating and removing potentially an
O(n^2) operation, as opposed to O(n), if you need to do it; and
2) it is not accurate: the same item by equality may potentially be
inserted/removed in the intervening time, or occur multiple times in the
same queue, so it would not be semantically equivalent.

I fail to understand your assertions that "Queue iterators are
intrinsically slow" or that "processing the internal items of a concurrent
queue is an unnatural act"; sure, the latter is atypical, but hardly
unnatural, and it is not appreciably slower than iterating any linked data
structure, nor algorithmically slower than iterating any data structure.




On 5 February 2014 13:47, Doug Lea <dl at cs.oswego.edu> wrote:

> On 02/04/2014 11:48 AM, Benedict Elliott Smith wrote:
>
>> This may be a bit on the late side for inclusion in JDK8,
>>
>
> No chance. JKD8 is completely frozen except for show-stopper bugs.
>
>
>   but I noticed that
>> ConcurrentLinkedQueue has moved to a non-blocking algorithm,
>>
>
> It has always been non-blocking. Maybe you are thinking of a different
> Queue?
>
>
>
>> However, it would be particularly nice to get a pollIfHead(item) method,
>> which
>>
>
> Yes, we initially contemplated a takeIfFirst(Object x) method. Sorry
> that I have no recollection of why this never made it into Queue API.
> It would be nearly impossible to add it to interface since there is
> no reasonable default implementation, but easy to add to CLQ and some
> others. I cannot think of a reason not to do this for JDK9.
>
>
>
>  possibly an extension of
>> Iterator that supports atomicRemove() (returning success/failure) or
>> similar.
>>
>
> I agree that it would have been nice for Iterator.remove to return a
> boolean (like Collection remove does). But considering that nearly
> all Queue iterators are intrinsically slow anyway (processing
> the internal items of a concurrent queue is an unnatural act),
> the argument for not just forcing people needing this to use
> queue.remove(x) is not all that compelling given that we would
> need to define a special Iterator subinterface and class
> just to expose this.
>
> -Doug
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140205/48bbe189/attachment-0001.html>


More information about the Concurrency-interest mailing list