[concurrency-interest] Re: Unbounded blocking queues -memoryconsumption

Dawid Kurzyniec dawidk at mathcs.emory.edu
Mon Oct 10 13:08:59 EDT 2005


Doug Lea wrote:

> 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.
>
dynamically growing array-based blocking queue, DynamicArrayBlockingQueue:

http://dcl.mathcs.emory.edu/util/#concurrent

http://dcl.mathcs.emory.edu/cgi-bin/viewcvs.cgi/software/util/src/edu/emory/mathcs/util/concurrent/DynamicArrayBlockingQueue.java?rev=1.6&view=markup

> But it is on average unlikely that an array will save memory:
> (...)

This is true, but the array-based implementation can save the day if you 
care only about the peek memory usage, not the average one. For 
instance, if you have occassional bursts and you want to avert 
catastrophic OutOfMemoryErrors.

Also, it is possible to modify the DynamicArrayBlockingQueue so that it 
shrinks back when emptied; this requires reasonable application-specific 
heuristics though so I didn't put that functionality in the general 
version. Perhaps the "compact()" method would do?

DynamicArrayBlockingQueue does not allow concurrent reads and writes, so 
it is more prone to congestion than LinkedBlockingQueue. I am guessing 
this should not happen a lot in a single-producer-single-consumer 
scenario though, since the accessor methods are very brief. But I did 
not measure this.

Both LinkedBlockingQueue and DynamicArrayBlockingQueue have a practical 
capacity limit of 2^31-1. Current implementation of 
DynamicArrayBlockingQueue may not handle overflow past that value 
gracefully. (Although you would almost surely see OutOfMemoryError first).

Regards,
Dawid



More information about the Concurrency-interest mailing list