[concurrency-interest] Multi consumer queue

David Holmes davidcholmes at aapt.net.au
Tue Apr 7 01:03:53 EDT 2009

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

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.

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