"By the pricking of my thumbs, something wicked this way comes."
-- Macbeth, act iv
In almost all modern programming languages, you have this thing called Memory Management. Roughly speaking, it is the art of doing that which by any other engineering standard, would be considered procrastination. Your application allocates heap space and as desired and leaves the cleaning up for later.
And the clean up is done by a magic, little black box known as the Garbage Collector. Its workings are intricate and complex. There are sometimes good reasons for this complexity, and often not. If you are a Java programmer (or use JVM languages like Scala), you should know a few basic things about this mysterious beast. And these few things should put the fear of God into you.
Stop the world
The first, and sometimes most perplexing fact about Garbage collection in the JVM is that when it decides to reclaim memory all application threads are stopped. It doesn't wait for requests to complete, transactions to commit, nor for you to pass go and collect $200. When the GC decides to kick in, your program stops. The more objects you create, the longer this pause lasts, and the longer it lasts, the greater your risk of timing out connections, losing data and generally making things very bad for your users. This problem cannot be solved, it can only be mitigated. You must learn to live with it.
How the generational collector works
There are two generations (of interest), young and old. As their names imply, they are intended to house either flavor of object. This is often where you can get tripped. The Young Generation is a fast, short-lived space, operated by a copying collector. A copying collector works like this:
- You divide the memory into two equal spaces.
- Allocate objects in the first one until it fills up.
- Now, you stop the world, scanning for live objects and copy them to the second space.
- Then, start allocating from what's left of the second space.
- Lather, rinse, repeat
Now, copying collectors are very fast--especially if most of your data is garbage. This is because it copies just the surviving objects and discards a whole memory space at once. However, this comes at a rather large cost--one half of the memory is always useless.
Of course the JVM is a bit cleverer about it, and uses one very large allocation space (called Eden) and two smallish survivor partitions, swapping between them. So in practice this is not as great a problem. One of these cycles is called a minor collection, and they typically last in the milliseconds.
How the old generation works
Once objects have been copied a lot between the Eden and survivor spaces, the JVM decides that it is too expensive to keep copying them around since they don't seem to be dying at all. At this point it promotes the object by copying it to the old generation. This process is called tenuring and is intended to detect very long-lived objects such as singletons and data constants.
The old generation uses a much more memory efficient collector and is typically much larger in size than its young counterpart. It uses a compacting collector that works like this:
- Stop all application threads
- Perform a thorough analysis of live memory (including soft/weak refs)
- Copy all live objects to the beginning of the memory space ("defragment" it)
- Start allocation after the last live object, thus freeing up everything that was not copied
This process is known as
compaction and is comparatively very slow (runs in the seconds). It is very similar to
disk defragmentation, which you may be familiar with from MS DOS days. This is sometimes called a
full or
major collection. The slowness and impact of a full collection cannot be overstated. While it is running, your application is basically dead in the water.
Reducing the frequency and duration of the aforementioned cycles is a dark art, worthy of the most occult of bit-sorcerers.
The Four Banes of Murphy
The following are four nemeses to the unwitting Java programmer, who in her blissful exuberance and naivete, believes that automatic memory management somehow means not having to worry about managing memory.
The GC spiral of death
So, the generational collector at first glance seems like a wonderful compromise between optimizing for short and long-lived objects with a tradeoff for speed and memory respectively. At second glance however, this is one of the most notoriously difficult things to predict and control. Almost all poor GC performance comes from misunderstanding this in some way.
Take the following scenario: When the application is under light load, short-lived objects are allocated and destroyed in the young generation as quickly as needed. The JVM observes this memory usage pattern and decides to set the young generation at a smallish size. Now, you suddenly experience heavy load, and this means thousands if not tens of thousands of short-lived objects suddenly all start clamoring for memory. To keep things going, the GC overflows these short-lived objects to the old generation, where there is still plenty of space. So far, so good.
However, recall that the old generation only gets cleared in a full GC cycle--which means that you need to have much more frequent full cycles, causing more frequent and longer pauses (seconds' worth) under heavy load.
Now, if the load remains heavy, these objects are continually overflowing and the GC's adaptive sizer notices that the old generation is in much heavier use. It decides to increase the size of the old generation accordingly. By complement, this means decreasing the size of the young generation, causing further overflows, and still slower and more frequent full cycles where the application is completely paused. As a result, your users see slow or unresponsive GUI elements and they start repeating commands (have you ever stood at a DONT WALK sign and hammered the button?), or worse they reload the entire app, producing greater load and an even greater stress on the JVM. Eventually, your application is completely unresponsive and you start losing data, timing out connections, and are forced to kill the process.
Soft references are the Devil
The SoftReference class should really have been called the SuccubusReference, because that's what it is--a seductress of meretricious and superficial beauty, who will drag your soul to hell and leave your corporeal body a listless shell, exhausted and empty.
Soft references are often touted as a convenient way to write caches. They are similar to weak references in that the GC will clear them if they are no longer needed by any active parts of the program (in technical terms, if they are not reachable from heap roots). However, they differ from weak references in that the GC will not clear them until it determines that it is running out of memory. They are also cleared in order of staleness. If you have worked with caches before, you know that it is next to impossible to write an accurate LRU cache that is also highly concurrent. So if the JVM provides these for free, why not use them? Here's why not:
- SoftRefs use the timestamp of the last full GC cycle. Under memory pressure, this means you will have to wait for the next full GC cycle to get rid of them. Meaning that the JVM can run out of memory and die, even while there are soft references yet to be cleared.
- They are incredibly difficult to profile, since taking a heap dump will trigger a full GC cycle, and clear them.
- You cannot accurately predict when a SoftRef will be cleared, nor can you easily bound the size of a SoftRef cache.
- Using them in critical code is dangerous because you are giving up control of your program's behavior to the whims and quirks of the Garbage Collector.
For these reasons, I recommend against using them at all.
The Vacuous shall inherit the earth
What's wrong with this code sequence?
- Start with a HashMap using new HashMap<K, V>().
- Over time, put a largish number of values in it,
- Over still more time, remove a number of entries.
Two things are wrong:
- The HashMap starts with an initial capacity of 16. Each time you exceed its capacity it must resize the underlying array, which is wastes memory and is slow.
- At step #3 the map is largely empty and is wasting a huge amount of memory, eventually causing memory pressure.
What's wrong with this (almost opposite) code sequence?
- Start with a HashMap using new HashMap<K, V>(),
- Put a small number of entries in (but, don't remove any).
Now, if you use this pattern in your data model, you could end up with thousands or even millions of partly empty arrays. This all adds up to wasted space, and at crunch time, it will kill your application.
Fix this problem by estimating the size of maps and lists beforehand and by trimming down long-lived or cached data structures over their lifespan. Calling new HashMap<K, V>() is several times more efficient than calling map.clear() for even mid-sized maps. Don't fear that you are creating more work for the GC--remember that collecting dead memory is a constant time operation. Marking live memory on the other hand, is not. I simply cannot overstate the impact of this problem.
The JDK and collections libraries in the wild do not take this concern seriously enough, in my opinion.
JIT and the GC
So you wouldn't think it, but Sun's Hotspot just-in-time compiler actually has an effect on Garbage Collection efficiency. This is because of an interesting feature where marking paths are optimized in compiled methods. In the -server JVM, methods are not compiled until 10,000 invocations, which can take several hours or days depending on server load. During this time, profiling GC behavior can be misleading and potentially draw you to erroneous conclusions. So be wary of this.
There is also a strange flag: -XX:DontCompileHugeMethods, which is on by default (meaning it doesn't compile huge methods, unless you tell it to). For such large methods, if they are hot, you may incur a GC penalty.
Conclusion
If learning all this about Garbage Collection does not cause you the utmost of terrors, and the eternal loss of sleep (as it did for me), then go back to the top, and read this article again until it does. =)
"Glamis hath murder'd sleep, and therefore Cawdor shall sleep no more; Macbeth shall sleep no more."
-- Macbeth, act ii
Update: In all references to JVMs above, I am referring to Sun's Hotspot JVM as of version 6.0.
