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

Martin Buchholz martinrb at google.com
Wed Feb 5 15:28:04 EST 2014


I'm leaning towards Benedict's view that iterating over the elements in a
data structure like CLQ is reasonable.  The List API is concurrency-hostile
because access by index doesn't really make sense.  But remove indexes and
use a concurrency-friendly iterator instead and you have something that
should be useful for "concurrent list processing".

If you implement a CLQ.ConcurrentIterator with boolean tryRemove(), then a
hypothetical takeIfFirst can be trivially implemented using the
ConcurrentIterator.

Note that for CLQ and CLD we know how to implement concurrent interior
removal, but not concurrent interior insertion.

Perhaps methods like takeIfFirst didn't make it for the usual reason that
us library folks have the urge to generalize, and that leads us to waiting
for lambdas.  But lambdas are finally here, so it is time to reconsider all
of those old API proposals for future JDKs.


On Wed, Feb 5, 2014 at 6:13 AM, Benedict Elliott Smith <
belliottsmith at datastax.com> wrote:

> 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
>>
>
>
> _______________________________________________
> 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/a0356b22/attachment.html>


More information about the Concurrency-interest mailing list