Wednesday, December 1, 2010

Memory Usage in Java

In Java, memory is allocated in various places such as the stack, heap, etc. In this newsletter I'm only going to look at objects which are stored on the heap. Please don't take me to task for not mentioning the others, they might appear in a future newsletter.

Say I have a class Foo, how much memory will one instance of that class take? The amount of memory can be determined by looking at the data members of the class and all the superclasses' data members. The algorithm I use works as follows:
  1. The class takes up at least 8 bytes. So, if you say new Object(); you will allocate 8 bytes on the heap.
  2. Each data member takes up 4 bytes, except for long and double which take up 8 bytes. Even if the data member is a byte, it will still take up 4 bytes! In addition, the amount of memory used is increased in 8 byte blocks. So, if you have a class that contains one byte it will take up 8 bytes for the class and 8 bytes for the data, totalling 16 bytes (groan!).
  3. Arrays are a bit more clever, at least smaller primitives get packed. I'll deal with these later.
In order to be able to test many different types of objects, I have written a MemoryTestBench class that takes an ObjectFactory which is able to create the type of object that you want to test. The MemoryTestBench can either tell you how many bytes are used by that object or it can print out a nicely formatted result for you. You get the most accurate results if you make sure that supplementary memory is already allocated when you start counting. I therefore construct the object, call the methods for finding the memory, and then set the handle to null again. The garbage collector is then called many times, which should free up all unused memory. The memory is then counted, the object created, garbage collected, and the memory counted again. The difference is the amount of memory used by your object, voila!
public class MemoryTestBench {
  public long calculateMemoryUsage(ObjectFactory factory) {
    Object handle = factory.makeObject();
    long mem0 = Runtime.getRuntime().totalMemory() -
      Runtime.getRuntime().freeMemory();
    long mem1 = Runtime.getRuntime().totalMemory() -
      Runtime.getRuntime().freeMemory();
    handle = null;
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    mem0 = Runtime.getRuntime().totalMemory() -
      Runtime.getRuntime().freeMemory();
    handle = factory.makeObject();
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    System.gc(); System.gc(); System.gc(); System.gc();
    mem1 = Runtime.getRuntime().totalMemory() -
      Runtime.getRuntime().freeMemory();
    return mem1 - mem0;
  }
  public void showMemoryUsage(ObjectFactory factory) {
    long mem = calculateMemoryUsage(factory);
    System.out.println(
      factory.getClass().getName() + " produced " +
      factory.makeObject().getClass().getName() +
      " which took " + mem + " bytes");
  }
}
The ObjectFactory interface looks like this:
public interface ObjectFactory {
  public Object makeObject();
}

Basic Objects

Let's start with the easiest case, a BasicObjectFactory that simply returns a new instance of Object.
public class BasicObjectFactory implements ObjectFactory {
  public Object makeObject() {
    return new Object();
  }
}
When we run this, we get the following output:
BasicObjectFactory produced java.lang.Object which took 8 bytes

Bytes

I suggested earlier that bytes are not packed in Java and that memory usage is increased in 8 byte blocks. I have written the ByteFactory and the ThreeByteFactory to demonstrate this:
public class ByteFactory implements ObjectFactory {
  public Object makeObject() {
    return new Byte((byte)33);
  }
}

public class ThreeByteFactory implements ObjectFactory {
  private static class ThreeBytes {
    byte b0, b1, b2;
  }
  public Object makeObject() {
    return new ThreeBytes();
  }
}
When we run these, we get the following output:
ByteFactory produced java.lang.Byte which took 16 bytes
ThreeByteFactory produced ThreeByteFactory$ThreeBytes which took 24 bytes
This is great (not). When I first started using Java I used to spend hours deciding whether a variable should be an int or short or a byte in order to minimize the memory footprint. I was wasting my time.As I said earlier, I don't know if this is only a problem under NT or if it's the same on all platforms. Knowing Java's dream of being equally inefficient on all platforms, I suspect that it would be the same.

Booleans

Let's carry on and look at a smaller unit of information, the boolean. Now a boolean is simply a bit, true or false, yes or no, zero or one. If I have a class that contains 64 booleans, guess how much memory it will take? 8 for the class, and 4 for each of the boolean data members, i.e. 264 bytes!!! Since a boolean is essentially the same as a bit, we could have stored the same information in one long. If you don't believe me, have a look at the following class:
public class SixtyFourBooleanFactory implements ObjectFactory {
  private static class SixtyFourBooleans {
    boolean a0, a1, a2, a3, a4, a5, a6, a7;
    boolean b0, b1, b2, b3, b4, b5, b6, b7;
    boolean c0, c1, c2, c3, c4, c5, c6, c7;
    boolean d0, d1, d2, d3, d4, d5, d6, d7;
    boolean e0, e1, e2, e3, e4, e5, e6, e7;
    boolean f0, f1, f2, f3, f4, f5, f6, f7;
    boolean g0, g1, g2, g3, g4, g5, g6, g7;
    boolean h0, h1, h2, h3, h4, h5, h6, h7;
  }
  public Object makeObject() {
    return new SixtyFourBooleans();
  }
}
When we run this, we get the following output:
SixtyFourBooleanFactory produced SixtyFourBooleanFactory$SixtyFourBooleans
  which took 264 bytes
Admittedly, the example was a little bit contrived, as you would seldom have that many booleans in one class, but I hope you get the idea.
Sun must have realised this problem so they made constants in java.lang.Boolean for TRUE and FALSE that both contain instances of java.lang.Boolean. I think that the constructor for Boolean should have been private to stop people from creating 16 byte objects that are completely unnecessary.

Arrays of Boolean Objects

A Boolean Array takes up 16 bytes plus 4 bytes per position with a minimum of 8 bytes at a time. In addition to that, we obviously have to count the actualy space taken by Boolean objects.
public class BooleanArrayFactory implements ObjectFactory {
  public Object makeObject() {
    Boolean[] objs = new Boolean[1000];
    for (int i=0; i<objs.length; i++)
      objs[i] = new Boolean(true);
    return objs;
  }
}
Try guess how many bytes would be taken up by a Boolean array of size 1000 with Boolean objects stuck in there. Ok, I'll help you: 16 + 4*1000 (for the pointers) + 16*1000 (for the actual Boolean objects) = 20016. Run the code and see if I'm right ;-) If we, instead of making a new Boolean object each time, use the Flyweights provided in Boolean, we'll get to 16 + 4*1000 = 4016 bytes used.
Primitives get packed in arrays, so if you have an array of bytes they will each take up one byte (wow!). The memory usage of course still goes up in 8 byte blocks.
public class PrimitiveByteArrayFactory implements ObjectFactory {
  public Object makeObject() {
    return new byte[1000];
  }
}
When we run this, we get the following output:
PrimitiveByteArrayFactory produced [B which took 1016 bytes

java.lang.String

Strings actually fare quite well since they can be "internalised" meaning that only one instance of the same String is kept. If you, however, construct your String dynamically, it will not be interned and will take up a bit of memory. Inside String we find:
// ...
private char value[];
private int offset;
private int count;
private int hash = 0;
// ...
Say we want to find out how much "Hello World!" would take. We start adding up 8 (for the String class) + 16 (for the char[]) + 12 * 2 (for the characters) + 4 (value) + 4 (offset) + 4 (count) + 4 (hash) = 64 bytes. It's quite difficult to measure this, as we have to make sure the String is not internalized by the JVM. I used the StringBuffer to get this right:
public class StringFactory implements ObjectFactory {
  public Object makeObject() {
    StringBuffer buf = new StringBuffer(12);
    buf.append("Hello ");
    buf.append("World!");
    return buf.toString();
  }
}
When we run this, we get, as expected, the following output:
StringFactory produced java.lang.String which took 64 bytes

java.util.Vector

Now we get to the real challenge: How much does a java.util.Vector use in memory? It's easy to say, now that we have a MemoryTestBench, but it's not so easy to explain. We start by looking inside the java.util.Vector class. Inside we find the following:
// ...
protected Object elementData[];
protected int elementCount;
// ...
Using the knowledge we already have, we decide that the amount of memory used will be 8 (for the class) + 4 (for the pointer to elementData) + 4 (for elementCount). The elementData array will take 16 (for the elementData class and the length) plus 4 * elementData.length. We then follow the hierarchy up and discover the variable int modCount in the superclass java.util.AbstractList, which will take up the minimum 8 bytes. For a Vector of size 10, we will therefore take up: 8 + 4 + 4 + 16 + 4*10 + 8 = 80 bytes, or simply 40 + 4*10 = 80 bytes, which agrees with our experiment:
public class VectorFactory implements ObjectFactory {
  public Object makeObject() {
    return new java.util.Vector(10);
  }
}
When we run this, we get the following output:
VectorFactory produced java.util.Vector which took 80 bytes
So, what happens when we create a JTable with a DefaultTableModel with 100x100 cells? The DefaultTableModel keeps a Vector of Vectors so this will take 40 + 4*100 + (40 + 4*100) * 100 = 440 + 44000 = 44440 bytes just for the empty table. If we put an Integer in each cell, we will end up with another 100*100*16 = 160'000 bytes used up.

java.util.LinkedList

What's better, a java.util.LinkedList or a java.util.ArrayList? Experienced followers of these newsletters will of course say: "Neither, the CircularArrayList is better" ;-). Let's see what happens when we put 10000 objects into an ArrayList (which uses the same amount of memory as the Vector) vs. a LinkedList. Remember that each Object takes up 8 bytes, so we will subtract 80000 bytes from each answer to get comparable values:
import java.util.*;
public class FullArrayListFactory implements ObjectFactory {
  public Object makeObject() {
    ArrayList result = new ArrayList(10000);
    for (int i=0; i<10000; i++) {
      result.add(new Object());
    }
    return result;
  }
}

import java.util.*;
public class FullLinkedListFactory implements ObjectFactory {
  public Object makeObject() {
    LinkedList result = new LinkedList();
    for (int i=0; i<10000; i++) {
      result.add(new Object());
    }
    return result;
  }
}
When we run this, we get the following output:
FullArrayListFactory produced java.util.ArrayList which took 120040 bytes
FullLinkedListFactory produced java.util.LinkedList which took 320048 bytes
When we subtract 80000 bytes from each, we find that the ArrayList takes up 40040 bytes (as expected) and the LinkedList uses 240048 bytes. How many of us consider issues like this when we code?
We have come to the end of yet another newsletter. I am trying to put newsletters together that will be worthwhile to send out, so as a result they will not always appear every week, unless I feel particularly

No comments:

Post a Comment