# Memory allocation

Discussion in 'Java' started by Momo, Jun 5, 2007.

1. ### MomoGuest

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

Momo, Jun 5, 2007

2. ### Kai SchwebkeGuest

Momo wrote:
> 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.

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

Kai Schwebke, Jun 5, 2007

3. ### Patricia ShanahanGuest

Kai Schwebke wrote:
> Momo wrote:
>> 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

Patricia Shanahan, Jun 5, 2007
4. ### MomoGuest

On Jun 5, 1:37 pm, Kai Schwebke <> wrote:
> Momo wrote:
> > 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

Momo, Jun 5, 2007