Memory allocation

Thread view:

Momo - 05 Jun 2007 17:51 GMT

Hi,

    Something was puzzling me about when I will run out of memory. I have
a simple program, that does nothing but take size as the input, and
then allocates a boolean array with x=new boolean[size]. I throw an
OutOfMemoryError when size is greater than about 6*10^7.

    If I then change the program to allocate a boolean array with y=new
boolean[size][4], I get the Error when size is greater than about
3*10^6. I would have thought that double-scripting the array to be
length 4, I would make the maximum value of size roughly 1/4th as
large. But instead it changes by a factor of 20. Why such a big
change?

    This is not an actual problem for me, since I just increased the size
of the java heap space. But I'd like to understand where the factor of
20 comes from.

Momo

Reply to this Message

Kai Schwebke - 05 Jun 2007 18:37 GMT

> large. But instead it changes by a factor of 20. Why such a big
> change?

boolean[n] consumes (most likely) c + n bytes.

boolean[n][4] is one array of n references to n arrays of 4 bytes.

Arrays are instances of class Array and consume (most likely)
from 12 to 16 bytes{1}. The reference may need additional 4 bytes.
All of this n times, leading to a quite high overhead.

You may consider using a bitset and a calculated index
(e.g. index = 4*a + b) to reduce the required heap space
to c + n/8 bytes.

Kai

{1} see http://martin.nobilitas.com/java/sizeof.html

Reply to this Message

Patricia Shanahan - 05 Jun 2007 19:27 GMT

>> large. But instead it changes by a factor of 20. Why such a big
>> change?
[quoted text clipped - 10 lines]
> (e.g. index = 4*a + b) to reduce the required heap space
> to c + n/8 bytes.

Transposing would be simpler, and get most of the memory reduction.
boolean[4][n] is one array of four references to four arrays of n booleans.

Patricia

Reply to this Message

Momo - 05 Jun 2007 19:53 GMT

> > large. But instead it changes by a factor of 20. Why such a big
> > change?
[quoted text clipped - 6 lines]
> from 12 to 16 bytes{1}. The reference may need additional 4 bytes.
> All of this n times, leading to a quite high overhead.

Thank you!

> You may consider using a bitset and a calculated index
> (e.g. index = 4*a + b) to reduce the required heap space
> to c + n/8 bytes.

I changed it to four Bitsets a few days ago, so it turns out that I
fixed it, I just didn't know why I fixed it.

Momo

Reply to this Message

Memory allocation

Free Magazines