Java Memory Puzzle

The Puzzle

The following code throws and OutOfMemoryError when you run it:

public class JavaMemoryPuzzle {
  private final int dataSize =
      (int) (Runtime.getRuntime().maxMemory() * 0.6);

  public void f() {
    {
      byte[] data = new byte[dataSize];
    }

    byte[] data2 = new byte[dataSize];
  }

  public static void main(String[] args) {
    JavaMemoryPuzzle jmp = new JavaMemoryPuzzle();
    jmp.f();
  }
}

This code does not throw an OutOfMemoryError:

public class JavaMemoryPuzzlePolite {
  private final int dataSize =
      (int) (Runtime.getRuntime().maxMemory() * 0.6);

  public void f() {
    {
      byte[] data = new byte[dataSize];
    }

    for(int i=0; i<10; i++) {
      System.out.println("Please be so kind and release memory");
    }
    byte[] data2 = new byte[dataSize];
  }

  public static void main(String[] args) {
    JavaMemoryPuzzlePolite jmp = new JavaMemoryPuzzlePolite();
    jmp.f();
    System.out.println("No OutOfMemoryError");
  }
}

The question is why?

Investigation (narrowing the problem)

So the only significant difference between the two classes is the use of a for loop in the code that doesn't OOM. The method f() is where I focused my attention. The method allocates two byte arrays each using 60% of the maximum amount of memory; if garbage collection doesn't kick in for data then an OOM error will happen. It looks like the narrowed puzzle is: why is the byte[] data not garbage collected after it falls out of scope?

My understanding of this (prior to this exercise) was that local variables were stored on the stack and popped off at the end of the method call, so nulling them inside a method was a waste of time. I hadn't considered the more fundamental scoping question though. When does the garbage collector remove references to local variables that are out of scope?

Ok now it was time to do some searching... the problem was that I didn't even know what to search for. After doing a bunch of searches about garbage collection I found this Appendix in a java garbage collection performance guide that seemed to answer the question.

Quote:

an efficient implementation of the JVM is unlikely to zero the reference when it goes out of scope... Because invisible objects can't be collected... you might have to explicitly null your references to enable garbage collection.

There were still some things bothering me though:

1. How does the for loop prevent the OOM? Is it enabling garbage collection?
2. The article is old: "Unless otherwise noted, all performance measurements described in this book were run on a pre-release build of the Java 2 Standard Edition (J2SE) v. 1.3 using the HotSpot Client VM on the Microsoft Windows operating system." IMHO, the VM has changed a lot since the pre-release 1.3 especially with regards to performance and garbage collection.

Investigation (Garbage Collection)

What I needed to know was what my more modern VM (1.5.0_16 on OSX) was really doing when both sets of code were executed. Here is the two executions with verbose GC enabled:

$ java -verbosegc JavaMemoryPuzzle
[GC 423K->156K(1984K), 0.0018041 secs]
[Full GC 156K->156K(1984K), 0.0136870 secs]
[GC 39219K->39209K(41040K), 0.0005973 secs]
[Full GC 39209K->39209K(41040K), 0.0085698 secs]
[Full GC 39209K->39201K(65088K), 0.0362276 secs]
Exception in thread "main" 
java.lang.OutOfMemoryError: Java heap space
 at JavaMemoryPuzzle.f(JavaMemoryPuzzle.java:12)
 at JavaMemoryPuzzle.main(JavaMemoryPuzzle.java:17)

$ java -verbosegc JavaMemoryPuzzlePolite
[GC 423K->156K(1984K), 0.0017339 secs]
[Full GC 156K->156K(1984K), 0.0107578 secs]
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
Please be so kind and release memory
[GC 39227K->39209K(41040K), 0.0006873 secs]
[Full GC 39209K->156K(41040K), 0.0082828 secs]

So this shows us the problem... the last Full GC is able to reclaim memory in the Polite class but is not able to in the non-Polite class. It still doesn't help us determine why.

Investigation (Bytecode)

The only thing I could think of was to somehow look at the bytecode that was being generated by the compiler. The tool to do this is javap. I opened a command prompt and ran it against the two classes. There is more stuff that comes out, but I trimmed the result to just the f() method as that is the important method:

$ javap -c JavaMemoryPuzzle
...
public void f();
  Code:
   0: aload_0
   1: getfield #6;
   4: newarray byte
   6: astore_1
   7: aload_0
   8: getfield #6;
   11: newarray byte
   13: astore_1
   14: return
...

It looks like the #6 and #13 the same index in the local variable array of the current frame to house the newarray created in #4 and #11. I'm not sure what this means but I think I was expecting two different indices.

Then I ran it again for the polite version:

$ javap -c JavaMemoryPuzzlePolite
...
public void f();
  Code:
   0: aload_0
   1: getfield #6;
   4: newarray byte
   6: astore_1
   7: iconst_0
   8: istore_1
   9: iload_1
   10: bipush 10
   12: if_icmpge 29
   15: getstatic #7;
   18: ldc #8;
   20: invokevirtual #9; 
   23: iinc 1, 1
   26: goto 9
   29: aload_0
   30: getfield #6;
   33: newarray byte
   35: astore_1
   36: return
...

Again it looks like the same thing (#6 and #35) but the difference is that there is storage instructionas a part of the initial creation of the for loop in line #8. Maybe it is this store instruction that is the key.

Note: I really had no idea what any of these commands meant but I consulted the VM Spec and looked at the instruction set.

Assignment or Looping?

I rewrote the Polite class's f() method as follows to remove the assignment but keep the loop by moving i to an instance variable:

int i = 0;
    public void f() {
        {
            byte[] data = new byte[dataSize];
        }
        for (; i < 3; i++) {
            System.out.println("whatever");

        }
        byte[] data = new byte[dataSize];
    }

When I run this I get an OOM. The bytecode looks like this:

public void f();
  Code:
   0: aload_0
   1: getfield #6;
   4: newarray byte
   6: astore_1
   7: aload_0
   8: getfield #7;
   11: iconst_3
   12: if_icmpge 36
   15: getstatic #8;
   18: ldc #9;
   20: invokevirtual #10;
   23: aload_0
   24: dup
   25: getfield #7;
   28: iconst_1
   29: iadd
   30: putfield #7;
   33: goto 7
   36: aload_0
   37: getfield #6;
   40: newarray byte
   42: astore_1
   43: return

Notice there is no store instruction between #6 and #42. Now I rewrite one more time just to have simple assignment (no loop) in the f() method:

public void f() {
        {
            byte[] data = new byte[dataSize];
        }
        int i = 1;
        byte[] data = new byte[dataSize];
    }

When I run this I get no OOM. The bytecode looks like this:

public void f();
  Code:
   0: aload_0
   1: getfield #6;
   4: newarray byte
   6: astore_1
   7: iconst_1
   8: istore_1
   9: aload_0
   10: getfield #6;
   13: newarray byte
   15: astore_2
   16: return

Notice the store instruction at #8 as well as #15 seems to use a different index.

Conclusion

I think the answer to the Java Memory Puzzle possibly depends upon the version of the JVM on which you are running. The OOM error occurs because the garbage collector has problems reclaiming memory allocated for invisible objects. It appears that the act of assignment from within the same method (and stack frame) but after an invisible object is out of scope, allows the garbage collector to reclaim the memory allocated for that invisible object. However, I don't understand why the garbage collector behaves this way.

Of course this code is a contrived example, I have found in practice that the two assignments in the example would probably happen in different methods and thus not run into this problem (each method gets its own stack frame). You certainly don't need to assign a variable to null if that is the last thing that happens before the method ends.

It is true that in very rare cases you may need to assign a local variable to null in order to let the garbage collector reclaim the memory assigned to that object. I can think of a couple of edge scenarioswhere this might be the case: A large data to small data scenario

public SmallData f() {
    BigData big = dataFetcher.getBigData();
    SmallData small = big.getSmallSubSet();
    big = null; //big can be collected
    small.doWork(); //creates a bunch of objects
    return small.readyForReturn();
}

or some kind of pool-like thing:

public void f() {
    {
      byte[] data = new byte[dataSize];
      data = null; //can be collected
    }
    while (true) {
      //do work forever
    }
  }