Put your fat Collections on a diet!

Background

Every Java program uses some sort of data structures, be it a trivial array or a Fibonacci Heap or even something more exotic that only Google search knows about. In most cases developers do not write their own implementations of these structures but use either the one provided by Java core APIs or some third-party library, such as Apache Collections or Google Guava. In my 10+ years of Java development not a day passed by without me using some data structure from Java Collection API. These Lists, Sets and Maps are so natural to me that I don't hesitate a second before writing 

Map<Integer, String> = new HashMap<Integer, String>(); 

And everything was fine until recently…

One of the classes inside our Plumbr java agent needs to store a bunch of integers as one of its fields. The semi-formal requirements are as follows:

• We need a data structure for storing integers.
• No duplicates
• Order is unimportant
• We need to add to this structure new elements
• We need to look up if some element exists in this structure
• Number of different elements is limited to a couple of hundreds at most
• Memory consumption is more important than speed
• Nevertheless the performance  must be decent, so MemoryMapped files, database etc are out of question.
  

The natural choice for this requirement is, at least considering my experience so far, java.util.HashSet<Integer>. So, without thinking twice I gave it a try. That was a disaster!

Experiment

Well, in order to illustrate my point, we need some way to measure memory usage of different data structures. For this blog post I used the following procedure:

1. Write a java class with main method, which holds needed data structure as a local variable
2. Add infinite cycle to the end of this main method in order for this thread not to die too quickly.
3. Using Eclipse Memory Analyzer take a memory dump and find out the size of retained heap for the local variable of interest.
   

As a baseline I used the fact that in Java integer takes 4 bytes. So, for a COUNT number of integers we need 4*COUNT bytes. Then we can calculate the overhead of the given data structure as follows:

Overhead = Structure's retained heap/(4*COUNT)

Please note, that Java distinguishes between primitives and objects and Collection API operates only on objects. It means that total overhead consists of the overhead of given collection data structure and overhead of using Integer objects, not primitives.

Results

Set<Integer> set = new HashSet<Integer>();
int COUNT = 10;
for (int i = 0; i < COUNT; i++) {
  set.add(i);
}

int COUNT = 10;
Integer[] array = new Integer[COUNT];
for (int i = 0; i < COUNT; i++) {
    array[i] = i;
} 

int COUNT = 10; 
int[] array = new int[COUNT];
for (int i = 0; i < COUNT; i++) {
    array[i] = i;
}

Conclusion