[concurrency-interest] Re: Unbounded blocking queues -memory consumption

Doug Lea dl at cs.oswego.edu
Sat Oct 8 09:25:59 EDT 2005


Calum MacLean wrote:
> Hi Doug
> I was thinking of implementations other than linked-list style.  For 
> example, there's an ArrayBlockingQueue, which would presumably take up less 
> memory, but that's fixed capacity.
> I'm wondering if there's any middle ground - unbounded, but minimal memory.
> 


I think that Dawid Kurzyniec might have once put together something
along these lines but I don't see it anywhere offhand.

But it is on average unlikely that an array will save memory:

On a 32 bit machine, an array will have 4bytes per
POTENTIAL item, while a Node { E item, Node next; }
will have minimally 8bytes, possibly 12bytes (one word
object header), and often in practice (because of alignment
or multiword header) 16 bytes per ACTUAL item. This means that an array
will take less space only when it is more than 1/2, 1/3, or 1/4
full, depending on the exact node size.

Statistically (read up on queuing theory for details),
unbounded BlockingQueues used in producer-consumer designs
are likely to be almost-always nearly empty. If they weren't, then they
would on average eventually grow without bound and exhaust all memory.
This means that in practice, an array-based version is likely
to be less than even 1/4 full. Sometimes it will transiently
have many more elements. But in that case, it is usually better
to stick with a linked version that can release nodes and let GC
reclaim space rather than keeping so many unused array slots around.

There are various special cases where you might know more
about usage patterns to do better than this, but I don't
think that they are very common, and I think that most of them are so
special that you would end up writing a custom implementation
anyway if you really needed to minimize footprint.

-Doug


More information about the Concurrency-interest mailing list