[concurrency-interest] Asynchronous-nature ofConcurrentLinkedQueue

David Holmes davidcholmes at aapt.net.au
Sun Aug 8 19:03:15 EDT 2010

Hi Peter,

I should have said "need to know the size for correctness". There are times when queries like this can be useful for performance heuristics as you describe. 

>From the usage you describe you seem to be supplanting the blocking-queue semantics with your own - in which case a customized wait/notify strategy may well perform better than the general one behind put/take. 

David Holmes 

 -----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Péter Kovács
Sent: Sunday, 8 August 2010 10:04 PM
To: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Asynchronous-nature ofConcurrentLinkedQueue


  > 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.


  On Wed, May 19, 2010 at 12:35 AM, David Holmes <davidcholmes at aapt.net.au> wrote:


    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.


    > 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100809/60f28bc3/attachment.html>

More information about the Concurrency-interest mailing list