[concurrency-interest] Multi consumer queue

Brett Bernstein brett.bernstein at gmail.com
Tue Apr 7 20:21:51 EDT 2009


Sometimes a slightly larger cost each time can be better (particularly with 
a low latency requirement) than a GC every so often, even if the total cost 
of the allocations + the GC is less.  To the point that certain 
implementations are better in certain scenarios, I feel like having the 
option of using a non-allocating lock would be very useful.  In the 
multithreaded applications I write these days I would never use anything 
else.
-Brett
----- Original Message ----- 
From: "David Holmes" <davidcholmes at aapt.net.au>
To: "Brett Bernstein" <brett.bernstein at gmail.com>
Cc: <concurrency-interest at cs.oswego.edu>
Sent: Tuesday, April 07, 2009 1:03 AM
Subject: RE: [concurrency-interest] Multi consumer queue


> Brett Bernstein writes:
>> I could be entirely wrong on this, but to me it seems wasteful
>> that I could have a program with 2 threads and 1 lock, do a bunch
>> of locking and releasing over the course of the program, and as a result
>> allocate millions of Nodes in the addWaiter method of
> AbstractQueuedSynchronizer.
>> It feels like there could be a much more efficient implementation here.
>> For example, if I wanted to build a low latency network application that
> never garbage
>> collected it becomes much harder when the best locking tools allocate
> aggresively.
>
> For a particular application scenario a more efficient implementation is
> nearly always possible. But in general, allocation is dirt cheap (99% of 
> the
> time from the thread-local allocation buffer) and short-lived objects are
> easily reclaimed by the GC from the young generation. And you only get
> millions of allocations if you get millions of contentions on the lock -
> which is likely to be more of a problem with regards to performance and
> latency than the allocation itself.
>
> One alternative would be to have each Thread have it's own pre-defined
> Node - given that a Thread can only block on one synchronizer at a time.
> However this also has implications for the queuing algorithms as it means
> that dequeuing has to be precise (so the Node can't end up on more than 
> one
> queue), where presently some dequeuing (for timeouts/cancellation) is done
> lazily - and so could impact performance of individual operations. A
> practical constraint on this approach is that Thread is not part of j.u.c 
> so
> (until Java 7 modules arrive) AQS would have to use some hackery to get
> access to the Thread's Node.
>
> Object pooling for Nodes could also be used but the cost of CASing a Node
> out of the freelist might be more than the cost of a TLAB allocation; and
> CASing it back into the freelist is much more expensive than simply 
> dropping
> the Node as garbage - of course you don't get GC running (just for Nodes)
> but perhaps GCing a million garbage Nodes is cheaper than a million 
> freelist
> adds? And of course freelists have other management issues that can impact
> the worst-case cost.
>
> Cheers,
> David Holmes
>>
>>
>> ----- Original Message -----
>> From: "Doug Lea" <dl at cs.oswego.edu>
>> To: "Brett Bernstein" <brett.bernstein at gmail.com>
>> Cc: <concurrency-interest at cs.oswego.edu>
>> Sent: Sunday, February 22, 2009 7:14 PM
>> Subject: Re: [concurrency-interest] Multi consumer queue
>>
>>
>> > Brett Bernstein wrote:
>> >> As a side note, I have a bit of a qualm with ReentrantLock.
>> Specifically
>> >> the fact that waiting on the lock requires new to be called, which in
>> >> some apps/situations I try to avoid.
>> >
>> > I assume you mean internal queue nodes constructed when threads block
>> > waiting for locks? Of course the same thing happens inside
>> builtin locks,
>> > but uses the JVM's internal memory management, which in most JVMs does
>> > not have the benefit of sitting on a high-performance garbage 
>> > collector.
>> >
>> > There are a bunch of situations in (concurrent) programming where
>> > allocating memory is a bad idea, but waiting for locks is not
>> > often among them. But if you would like to trade off more time
>> > spinning rather than  allocating and blocking, you can precede
>> > calls to lock() with some number of calls to tryLock.
>> >
>> > -Doug
>> >
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> 



More information about the Concurrency-interest mailing list