Java uses more memory than anticipated

Question

Ok, so I try to do this little experiment in java. I want to fill up a queue with integers and see how long it takes. Here goes:

import java.io.*;
import java.util.*;

class javaQueueTest {
public static void main(String args[]){
    System.out.println("Hello World!");
    long startTime = System.currentTimeMillis();
    int i;
    int N = 50000000;

    ArrayDeque<Integer> Q = new ArrayDeque<Integer>(N);
    for (i = 0;i < N; i = i+1){
        Q.add(i);
    }
    long endTime   = System.currentTimeMillis();
    long totalTime = endTime - startTime;
    System.out.println(totalTime);
}
}

OK, so I run this and get a

Hello World!
12396

About 12 secs, not bad for 50 million integers. But if I try to run it for 70 million integers I get:

Hello World!
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.lang.Integer.valueOf(Integer.java:642)
    at javaQueueTest.main(javaQueueTest.java:14)

I also notice that it takes about 10 mins to come up with this message. Hmm so what if I give almost all my memory (8gigs) for the heap? So I run it for heap size of 7gigs but I still get the same error:

javac javaQueueTest.java
java -cp . javaQueueTest -Xmx7g
Hello World!
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.lang.Integer.valueOf(Integer.java:642)
    at javaQueueTest.main(javaQueueTest.java:14)

I want to ask two things. First, why does it take so long to come up with the error? Second, Why is all this memory not enough? If I run the same experiment for 300 million integers in C (with the glib g_queue) it will run (and in 10 secs no less! although it will slow down the computer alot) so the number of integers must not be at fault here. For the record, here is the C code:

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<glib.h>
#include<time.h>

int main(){
clock_t begin,end;
double time_spent;
GQueue *Q;

begin = clock();
Q = g_queue_new();
g_queue_init(Q);
int N = 300000000;
int i;
for (i = 0; i < N; i = i+1){
    g_queue_push_tail(Q,GINT_TO_POINTER(i));
}
end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("elapsed time: %f \n",time_spent);

}

I compile and get the result:

gcc cQueueTest.c `pkg-config --cflags --libs glib-2.0 gsl ` -o cQueueTest
~/Desktop/Software Development/Tests $ ./cQueueTest 
elapsed time: 13.340000

Answer 1

You can catch OutOfMemoryError with :

try{
    ArrayDeque<Integer> Q = new ArrayDeque<Integer>(N);
    for (i = 0;i < N; i = i+1){
        Q.add(i);
    }
}
catch(OutOfMemoryError e){
    Q=null;
    System.gc();
    System.err.println("OutOfMemoryError: "+i);
}

in order to show when the OutOfMemoryError is thrown.

And launch your code with :

java -Xmx4G javaQueueTest

in order to increase heap size for JVM

As mentionned earlier, Java is much slower with Objects than C with primitive types ...

Answer 2

In your case, the GC struggles as it assumes that at least some objects will be short lived. In your case all objects are long lived, this adds a significant overhead to managing this data.

If you use -Xmx7g -Xms7g -verbose:gc and N = 150000000 you get an output like

Hello World!
[GC (Allocation Failure)  1835008K->1615280K(7034368K), 3.8370127 secs]
5327

int is a primitive in Java (4 -bytes), while Integer is the wrapper. This wrapper need a reference to it and a header and padding and the result is that an Integer and its reference uses 20 bytes per value.

The solution is to not queue up some many values at once. You can use a Supplier to provide new values on demand, avoiding the need to create the queue in the first place.

Even so, with 7 GB heap you should be able to create a ArrayQueue of 200 M or more.

Answer 3

My rough thoughts about your questions:

First, why does it take so long to come up with the error?

As gimpycpu in his comment stated, java does not start with full memory acquisition of your RAM. If you want so (and you have a 64 bit VM for greater amount of RAM), you can add the options -Xmx8g and -Xms8g at VM startup time to ensure that the VM gots 8 gigabyte of RAM and the -Xms means that it will also prepare the RAM for usage instead of just saying that it can use it. This will reduce the runtime significantly. Also as already mentioned, Java integer boxing is quite overhead.

Why is all this memory not enough?

Java introduces for every object a little bit of memory overhead, because the JVM uses Integer references in the ArrayDeque datastructur in comparision to just 4 byte plain integers due to boxing. So you have to calulate about 20 byte for every integer.
You can try to use an int[] instead of the ArrayDeque:

import java.io.*;
import java.util.*;

class javaQueueTest {
    public static void main(args){
        System.out.println("Hello World!");
        long startTime = System.currentTimeMillis();
        int i;
        int N = 50000000;
        int[] a = new int[N];
        for (i = 0;i < N; i = i+1){
            a[i] = 0;
        }
        long endTime   = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println(totalTime);
    }
}

This will be ultra fast and due the usage of plain arrays. On my system I am under one second for every run!

Answer 4

First, why does it take so long to come up with the error?

This looks like a classic example of a GC "death spiral". Basically what happens is that the JVM does full GCs repeatedly, reclaiming less and less space each time. Towards the end, the JVM spends more time running the GC than doing "useful" work. Finally it gives up.

If you are experiencing this, the solution is to configure a GC Overhead Limit as described here:

• GC overhead limit exceeded

(Java 8 configures a GC overhead limit by default. But you are apparently using an older version of Java ... judging from the exception message.)

Second, Why is all this memory not enough?

See @Peter Lawrey's explanation.

The workaround is to find or implement a queue class that doesn't use generics. Unfortunately, that class will not be compatible with the standard Deque API.