Out of memory error in java

Question

I am getting OutOfMemoryError: java heap

snippets of the method:

{
// step 1: I am creating a 2 dim array
  int totalCombination = (int) Math.pow(2.0, (double) vowelCount);
// here vowelCount > 10

// step2: initializing my array
// step3: and using that array
}

My Question:

each time this method is called, that array is getting created. Is it possible that the array is not getting released .

In windows taskmanager i can see memory used by java is purely incremental. So it is not that at a point heap size is less, but memory is repetitively used and not released somehow.

Please let me know if you need more detal.

Please help to debug the error.

Anuj

The part of the code which might be causing the error:

int totalCombination = (int) Math.pow(2.0, (double) vowelCount);

    int lookupArray[][] = new int[totalCombination][vowelCount];

    // initialize lookupArray

    for (int i = 0; i < totalCombination; i++) {
        for (int j = 0; j < vowelCount; j++) {
            lookupArray[i][j] = 0;
        }
    }

    // populate lookupArray
    //vowelCount : number of vowels in a word
    // if count is 2, then array will contain 00,01,10,11

    for (int i = 1; i < totalCombination; i++) {
        for (int c = 0; c < vowelCount; c++) {
            lookupArray[i][c] = lookupArray[i - 1][c];
        }
        boolean flag = true;
        for (int j = vowelCount - 1; j >= 0 && flag; j--) {
            if (lookupArray[i - 1][j] == 1) {
                lookupArray[i][j] = 0;
            } else if (lookupArray[i - 1][j] == 0) {
                lookupArray[i][j] = 1;
                flag = false;
            }
        }
    }


  // this part total combination of a word having different combination of vowels in it.


    for (int i = 0; i < totalCombination; i++) {
        int vcount = vowelCount - 1;
        StringBuffer stringBuffer = new StringBuffer();

        for (int j = 0; j < word.length(); j++) {
            if (wordArr[j] == 'a' || wordArr[j] == 'e' || wordArr[j] == 'i'
                    || wordArr[j] == 'o' || wordArr[j] == 'u') {
                if (lookupArray[i][vcount] == 1) {
                    stringBuffer.append(wordArr[j]);
                }
                vcount--;
            } else {
                stringBuffer.append(wordArr[j]);
            }
        }

Answer 1

Powers of two grows exponentially. If vowelCount is high, one array alone could easily cause OutOfMemoryError (2^32 = 4GB).

You can try to tweak your VM maximum memory requirement (e.g. -Xmx512m), but do realize that your algorithm is requiring A LOT OF MEMORY. You may want to find a better algorithm if at all possible.

---

See also

• Wikipedia: exponential growth
  • Wheat and chessboard problem -- famous anecdote to show just how surprisingly quick powers of two can grow
• java application launcher command line options
  • "-Xmxn : Specify the maximum size of the memory allocation pool."

---

After edit: just as I expected, you're generating a huge array filled with all binary possibilities. You rarely need to actually store this whole array in memory. You can just generate each possible combination "on-the-fly" and feed it to whoever needs the 0s and 1s "just-in-time".

Do keep in mind that this is still exponential growth, so even though you've taken care of your memory requirement from O(2^N) to just O(N), your time complexity is still O(2^N).

each time this method is called, that array is getting created. Is it possible that the array is not getting released .

Yes, that is very possible, if the reference to the array is ever leaked, and then something somewhere holds on to this reference. The garbage collector doesn't really care what you think is/isn't garbage; as long as an object is referred to by something (and it's not a weak reference etc), it's NOT garbage.

---

After figuring out what you're trying to do, here's my solution. Note that it doesn't generate an array of bits at all.

static void generate(String prefix, String suffix) {
    int i = suffix.replaceAll("[aeiou].*", "").length();
    if (i == suffix.length()) {
        System.out.println(prefix + suffix);
    } else {
        generate(prefix + suffix.substring(0, i), suffix.substring(i + 1));
        generate(prefix + suffix.substring(0, i+1), suffix.substring(i + 1));
    }
}

// generate("", "apple");

It uses regex to find where the next vowel is. You can use a regular for-loop instead and the general algorithm will still work. You can optimize it to use StringBuilder instead (I'm mostly going for conciseness and hopefully clarity in this snippet).

---

Here's an alternative solution that uses split to pre-chop the input string into pieces (O(N) space), then uses a StringBuilder to generate all the other strings (O(N) space).

static void generate(StringBuilder sb, String[] parts, int i) {
    if (i == parts.length) {
        System.out.println(sb.toString());
    } else {
        if ("aeiou".contains(parts[i])) {
            generate(sb, parts, i + 1);
        }
        sb.append(parts[i]);
        generate(sb, parts, i + 1);
        sb.setLength(sb.length() - parts[i].length());
    }
}
static void generate(String s) {
    generate(
        new StringBuilder(),
        s.split("(?<=[aeiou])|(?=(?!^)[aeiou])"),
        0
    );
}

// generate("apple");

The regex splits "apple" into [ "a", "ppl", "e" ]. It splits everywhere after a vowel, or (if it's not the beginning of the string) everywhere before a vowel.

It should be obvious now that the space requirement is O(N), so unless your string is ridiculously long, this should not cause OutOfMemoryError.

Of course, if you're storing the generated strings -- all O(2^N) of them -- in memory then of course you'll get OutOfMemoryError. I hope this fact is obvious.

The entire idea is to not store in memory anything that you don't need to generate this HUGE OUTPUT. If you then store all of this HUGE OUTPUT in memory (instead of, say, printing them to stdout or a file) then it defeats the whole purpose and you'll get an OutOfMemoryError as expected.

Answer 2

You might want to consider using a profiler that can give you a picture of what types of objects exists at any given time in your program. As one example, NetBeans has a built-in profiler.

With that being said, the likely culprit is--as has been pointed out by others--the extraordinarily high amount of memory that your two-dimensional array will require as the vowel count grows.

Answer 3

I assume you have something like the following code:

int totalCombination = 1 << vowelCount;
System.out.println("totalCombination = " + totalCombination);
System.out.println("totalCombination (in Millions) = " + totalCombination / 1000 / 1000);

int[] arr = new int[totalCombination];

In a 32 bit VM the array cannot ever grow further than 4 GB, that is 1024 million entries. Make sure you always get smaller numbers printed out in the above code.

And maybe you should take a completely different algorithm. But for that you would have to tell us what you want to achieve, not how you are trying it.