[concurrency-interest] Asynchronous-nature ofConcurrentLinkedQueue

Péter Kovács peter.kovacs.1.0rc at gmail.com
Mon Aug 9 02:53:46 EDT 2010


Thank you, David!
Peter

2010/8/9 David Holmes <davidcholmes at aapt.net.au>

>  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
>
>  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/20100809/a20edb53/attachment-0001.html>


More information about the Concurrency-interest mailing list