[concurrency-interest] Asynchronous-nature of ConcurrentLinkedQueue

Péter Kovács peter.kovacs.1.0rc at gmail.com
Sun Aug 8 08:04:17 EDT 2010


David,

> The present code only penalises the misguided client that thinks they need
to know the size.

Is there a simple, abstract way to demonstrate one shouldn't need this
information? (But not too formal, please. :-) )

I have a scenario where I found useful knowing an approximate size of a
LinkedBlockingQueue:

A number of worker threads

   1. put an empty result-holder object on the LBQ,
   2. take their input from a producer,
   3. do some processing and
   4. put the result into the empty result-holder object.

The first two steps are executed in a synchronized block, so the order of
results on the LBQ reflects that of the corresponding inputs.

The LBQ is consumed by a single thread.

I found that

   1. having the worker wait in step#1, when the LBQ is full ( if
   (!lbq.offer(resultHolder)) { wait(); } )  and
   2. notifying workers waiting, when lbq.size() < maxLbqSize * 4 / 5

gives about 15% improvement in throughput -- as opposed to the algorithm,
where I let workers block in lbq.put(resultHolder).

My naive hypothesis to explain the gain is that having -- during *each
*lbq.take()
-- to constantly manage the threads which block in lbq.put() might be more
expensive than having workers wait and notifying them *less frequently*.

I've been having the haunting feeling that this queue-size-checking trick is
just a hack to compensate for some non-trivial design (or implementation)
flaw elsewhere. But I haven't been able to find a(n easy) way to either
prove or refute my hypothesis.

I'd be grateful if you could offer some thoughts on this.

Thanks
Peter

On Wed, May 19, 2010 at 12:35 AM, David Holmes <davidcholmes at aapt.net.au>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.
>
> David
>
> >
> > Gregg Wonderly
> > _______________________________________________
> > 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/20100808/42707146/attachment.html>


More information about the Concurrency-interest mailing list