Memory allocation

[Momo]

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

 

[Kai Schwebke]

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

 

[Patricia Shanahan]

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.

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

 

[Momo]

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.

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