[concurrency-interest] General Question on queue-size

Doug Lea dl at cs.oswego.edu
Mon May 31 14:21:42 EDT 2010


On 05/31/10 10:51, Kai Meder wrote:
> Hello,
>
> there was a discussion about the ConcurrentLinkedQueue regarding a
> proper size implementation. One Point was that offer and poll would
> fight for an atomic Counter, resulting in a huge performance penalty.
> Another Point was the general "asynchronous" nature of the offer- and
> poll-operations, so the size would only be a rough estimate.
>
> However is the following not possible either?
> - offer increments an offerCounter
> - poll increments a pollCounter
> - estimatedSize = offerCounter - pollCounter
>
> Is this practicable?

Not especially, although it depends on expected producer and
consumer loads.

Usually the best solution along these lines is to include a
serial number in each node, and arrange serial for each node is
one plus its predecessor (recomputing on missed attempts to link). You
can then determine length as last.serial - head.serial.

We don't do it by default for the usual reason that we
don't want to waste time and space overhead for an operation
that is of dubious utility.


> I am looking for a way to implement a BoundedQueue where the producer is
> stopped after the buffer is full (bounded). However I am not able to use
> the existing Queues as they are blocking. I experiment with
> Continuation-Passing-Style (reset/shift) in Scala and must not use any
> traditional Thread-blocking-operations.
>

You might however need to make the decision to create continuation
atomically, requiring locks at some level.

-Doug


More information about the Concurrency-interest mailing list