Unbounded blocking queues - memory consumption

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Unbounded blocking queues - memory consumption

Calum
Hi

My application is producing a large unbounded quantity of objects which are
being put into a BlockingQueue for consumption by some other thread.
I'm currently using LinkedBlockingQueue, as it's unbounded.
However, I'm seeing that the LinkedBlockingQueue.Node objects take up a fair
bit of memory - around about 16 bytes each according to my profiler.
So, while I'm not 100% sure, I'm a bit worried about the memory consumption,
as it's a large number of objects which are being produced.

Are there any other alternatives for unbounded BlockingQueue implementations
which maybe take up less memory than LinkedBlockingQueue?

Thanks for your help,
Calum



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Unbounded blocking queues - memory consumption

Doug Lea
Calum MacLean wrote:

> Hi
>
> My application is producing a large unbounded quantity of objects which are
> being put into a BlockingQueue for consumption by some other thread.
> I'm currently using LinkedBlockingQueue, as it's unbounded.
> However, I'm seeing that the LinkedBlockingQueue.Node objects take up a fair
> bit of memory - around about 16 bytes each according to my profiler.
> So, while I'm not 100% sure, I'm a bit worried about the memory consumption,
> as it's a large number of objects which are being produced.
>
> Are there any other alternatives for unbounded BlockingQueue implementations
> which maybe take up less memory than LinkedBlockingQueue?
>

I don't believe there is any way to reduce overhead for any
linked structure down and further -- the nodes only have item
and next fields; plus the usual Java per-Object header etc.
If you really need the space and are in full control of the
kinds of elements, you might be able to make a custom version.
If for example, each element is of class Element, you can add
a "next" link to the Element class, used only by the queue, and
then copy-paste-hack LinkedBlockingQueue to directly use it
rather than wrapping each item in a Node. This is not recommended
unless you are desparate though.

-Doug



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Unbounded blocking queues -memory consumption

Calum
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.
Thanks,
Calum


"Doug Lea" <[hidden email]> wrote in message
news:[hidden email]...

> Calum MacLean wrote:
>> Hi
>>
>> My application is producing a large unbounded quantity of objects which
>> are being put into a BlockingQueue for consumption by some other thread.
>> I'm currently using LinkedBlockingQueue, as it's unbounded.
>> However, I'm seeing that the LinkedBlockingQueue.Node objects take up a
>> fair bit of memory - around about 16 bytes each according to my profiler.
>> So, while I'm not 100% sure, I'm a bit worried about the memory
>> consumption, as it's a large number of objects which are being produced.
>>
>> Are there any other alternatives for unbounded BlockingQueue
>> implementations which maybe take up less memory than LinkedBlockingQueue?
>>
>
> I don't believe there is any way to reduce overhead for any
> linked structure down and further -- the nodes only have item
> and next fields; plus the usual Java per-Object header etc.
> If you really need the space and are in full control of the
> kinds of elements, you might be able to make a custom version.
> If for example, each element is of class Element, you can add
> a "next" link to the Element class, used only by the queue, and
> then copy-paste-hack LinkedBlockingQueue to directly use it
> rather than wrapping each item in a Node. This is not recommended
> unless you are desparate though.
>
> -Doug



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: Unbounded blocking queues -memory consumption

Doug Lea
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
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: Unbounded blocking queues -memoryconsumption

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

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest