Episode 16

This article is the second part of my Java performance guide. After concentrating on how to make code fast, let’s turn to how to make code eat less memory. There are two important things to consider:

First, in modern computers, memory access time is more limiting than CPU frequency.

Second, when talking about algorithms from academic point of view, it is said, that there is a tradeoff between speed and memory. That’s of course true, however keep in mind, that memory allocation takes time, memory read/write takes time and finally garbage collection takes time. If you turn on heap status in Eclipse, you can sometimes literally see how the code is reaching 99% percent of the heap and then execution time hits the wall and things slows down a lot. GC is working hard to make things possible. If it is possible, otherwise you are getting OutOfMemoryError and you are done.

Java, wat r u doin! Java, staph…

Of course, you can increase heap space to make things happen. However you can’t do that indefinitely (unless you are Google). Although one of my PO’s said once that we shouldn’t worry because clients have unlimited memory, you should worry. Not always, and maybe not even half the time, but being reckless with memory might hit you hard in some particular cases.

Code that is memory efficient might be complicated, hard to maintain and error prone, but there are few thing you can keep in mind and use without introducing unnecessary complications. Sometimes, as I said in previous article, code that is faster or takes less memory may be even more elegant and readable.

So when to optimize size?

Again, get to know your code. Study, experiment, check out the production database (if you have access), do some statistics. If you have a collection containing all your users, check out how much user you have. If it’s a problem, look for high level solution. Perhaps you don’t need all users at one time? Maybe you can process them in batches? Maybe you can load lazily? Maybe you can construct some kind of cache?

If this approach fails, you can tweak stuff at lower level of abstraction, and that’s what we are going to discuss now.

Objects size

Object header in Java takes 12 bytes. However objects on heap are allocated in 8 bytes blocks, thus making smallest Objects take 16 bytes. Primitive sizes are:

• byte – well, 1 byte
• short, char – 2 bytes
• int, float – 4 bytes
• long, double – 8 bytes
• Reference – 4 bytes if heap is under 32 GB with default VM settings and 8 bytes otherwise.

So if you are thinking of reducing your object size from 32 to 28 or 26 bytes, I have bad news for you. It will still take 32 bytes no matter what.

byte and short pitfall

Primitives as objects fields always take a minimum of 4 bytes. So using bytes or shorts instead of ints as fields to save memory is useless. Arrays however are dense packed, so you may use byte and short array to get some savings.

Primitives vs wrappers

Wrappers carry the Object overhead. They take at least 16 bytes, and Long and Double takes 24. Plus 4 bytes for each reference to them. If you have a lot of data, and don’t need a null value, you can use primitives instead of wrappers to save memory. For example in a User object, if you only read data from database, you can probably use long instead of Long for primary key and save 16 bytes per object. On the other hand, if you use ORM framework, you may create objects by hand and then persist them, which means that primary key will be null at some point.

Arrays

• Primitive array of length n: 16 + (1 to 8) * n depending on primitive type.
• Objects arrays: 16 + (4 + object_size) * n on heap below 32 GB.

Strings

Each String contains a few ints, a reference to char array and the array itself. It all takes 40 + 2*n depending on number of characters. What does it mean? If you have a lot of very short Strings, you have a lot of overhead. If you have only one-letter strings, it’s probably better to use chars instead.

Lists

Now it’s getting interesting.

• ArrayList: 40 + (4 +object_size) *n + 4 * unused_capacity
• LinkedList: 48 + (24 + object_size)

Yes, LinkedList has 6 times more overhead per node. That’s another reason to use ArrayList instead most of the time. Array list resizes itself automatically, so it usually has some unused space. If you know that no more data will be added, you may use it’s trimToSize method to remove unnecessary overhead. Not very much, but with lots of small objects it might be visible.

Maps

• HashMap: 56 + (32 + object_size + key_size) * n + 4 * capacity
• LinkedHashMap: 56 + (40 + object_size + key_size) * n + 4 capacity
• TreeMap: 56 + (40 + object_size + key_size) * n + 4 * capacity

I had a situation where there was a graph node object, that contained several eagerly initialized collections, that were empty 95% of the time. It turns out that when number of nodes went in millions, it was a serious problem. Creating collections lazily might save you some space.

By the way, Sets in Java contains Maps, so they have same size per node, with additional overhead per Set Object.

Alternatives

There are libraries of specialized collections, like Trove. They are optimized for memory footprint. For example THashMap takes only 8 bytes per key / value pair instead of 40 as standard HashMap

EnumMap, EnumSet – specialized collection in standard Java. As, most of the time, Enums do not have more than 32 or 64 values, Set of enums may be represented as bit mask based on int or long. It reduces a lot of overhead for MapEntry objects.

BitSet. Dense packed bit vector, that only takes, well, only 1 bit per bit or boolean value. Normal boolean in Java occupies 4 bytes if it’s a variable or 1 byte if it’s in an array.

What’s next?

Perhaps I will come back to the topic of performance. I have a new book, Java Performance The Definitive Guide added to my long reading list. I hope it will be interesting and third episode about performance will be born on this blog afterwards.

Speaking of reading list, next episode is going to be a book review. Stay tuned ;)