Re: Strange OutOfMemory Exception

Hans.Deutsch@googlemail.com wrote:


Let's break down how that uses space. You have an array of 31125 references to
byte[][] arrays. Each of those byte[][] arrays holds 1632 references to byte[]
arrays. Each if those 31125 * 1632 byte[] arrays holds 2 booleans. The
details of how much space each array requires is dependent on the JVM
implementation, but I'll assume a current 32-bit JVM from Sun.

First off, consider the 31125*1632 byte[] arrays. Each of those arrays holds 2
Booleans. Typically a JVM will represent Booleans (in arrays) as 1 byte each.
In addition, each array is a full object, and so it has an 8-byte object header
(which is not visible from Java code) and a 4-byte record of how big it is. So
that makes a total of
    31125 * 1632 * (12 + 2) == 711144000
bytes. I.e, about 700 MBytes.

That's just for the byte[] arrays themselves. There are also 31125 arrays
which hold references /to/ those arrays (the byte[][] arrays). Each of those
has 1632 4-byte slots, plus the 12 bytes of object header/size, making (1632 *
4) + 12 bytes each. So these total
    31125 * ((1632 * 4) + 12) == 203557500
bytes. I.e. around 200 MBytes.

Lastly there's the byte[][][] array itself. That has 31125 slots of 4 bytes
each, plus the usual 12-byte array header, making
    (31125*4) + 12 == 124512
bytes. Pretty trivial ;-)

So the sum total is:
    711144000 + 203557500 + 124512 == 914826012
bytes. Or nearly a Gigabyte.

So you run out of space...

The simplest way to avoid this blow-up is to use a single byte instead of each
array of two Booleans (plus some bit-twiddling). That wastes 6 out of the 8
possible bits, but it is relatively simple. If you do that then the array
creation expression would be:
    byte[][] packedMatrix = new byte[31125][1632];
which takes up a /lot/ less space. In fact there would be an array of 31125
references to byte[] arrays (making 12452 bytes, as above), plus 31125 byte[]
arrays, each of which held 1632 bytes. So they would total:
    31125 * (1632 + 12) == 51169500
bytes. So the whole thing takes around 52 MBytes.

If you are willing to do a bit more work, then you could represent the whole
structure as a single array of
    31125 * 1632 * 2
bits, where you pack each 32 bits into an int. The allocation expression would
be

    int[] packedMatrix = new int[31125*1632*2/32];
(ignoring rounding). And that would take up only 12 MBytes, but the code to
access each bit will be a little more complicated (but faster as well as more
space efficient).

In fact you could probably use a java.util.BitSet instead of an int[] array,
and let Java do some of the work for you:
    BitSet packedMatrix = new BitSet(31125*1632*2);
You'd still have to do /some/ work yourself to convert three-level indexes into
integer offsets, but at least the BitSet would look after the bit-twiddling
(which not everybody is comfortable with). On the other hand, it might be
slower than a hand-coded implementation. If that matters to you then try it
both ways and see which is quicker.

    -- chris