The Garbage Collection Handbook

Richard Jones, Antony Hosking, Eliot Moss

Mentioned 9

Published in 1996, Richard Jones’s Garbage Collection was a milestone in the area of automatic memory management. The field has grown considerably since then, sparking a need for an updated look at the latest state-of-the-art developments. The Garbage Collection Handbook: The Art of Automatic Memory Management brings together a wealth of knowledge gathered by automatic memory management researchers and developers over the past fifty years. The authors compare the most important approaches and state-of-the-art techniques in a single, accessible framework. The book addresses new challenges to garbage collection made by recent advances in hardware and software. It explores the consequences of these changes for designers and implementers of high performance garbage collectors. Along with simple and traditional algorithms, the book covers parallel, incremental, concurrent, and real-time garbage collection. Algorithms and concepts are often described with pseudocode and illustrations. The nearly universal adoption of garbage collection by modern programming languages makes a thorough understanding of this topic essential for any programmer. This authoritative handbook gives expert insight on how different collectors work as well as the various issues currently facing garbage collectors. Armed with this knowledge, programmers can confidently select and configure the many choices of garbage collectors. Web Resource The book’s online bibliographic database at www.gchandbook.org includes over 2,500 garbage collection-related publications. Continually updated, it contains abstracts for some entries and URLs or DOIs for most of the electronically available ones. The database can be searched online or downloaded as BibTeX, PostScript, or PDF.

More on Amazon.com

Mentioned in questions and answers.

Almost everyone eventually runs into GC issues with Java.

Is there a cookbook guide or semi-automated tool to tune GC for Java?

My rationale is this:

  • Almost anyone eventually has these problems
  • There are many possible factors (say 20) out of which only a few affect your problem.
  • Most people don't know how to identify the key factors so GC tuning is more like a black art than a science.
  • Not everyone uses a HotSpot VM. Different Sun versions have different GC characteristics.
  • There is little incentive to experiment (like run the VM with slightly different settings every day to see how they play out).

So the question really is: Is there something that I can use in a check-list manner? Or maybe even a tool that analyzes GC logs or heap dumps and gives me specific hints where to look (instead of telling me "95% of the data is allocated in objects of the type byte[]" which is basically useless).

Related questions:

Out of various resources I have compiled a sanity checklist that I use to analyze GC behavior and performance of my applications. These guidelines are general and apply to any vendor-specific JVM but contain also HotspotVM-specific information for illustration.

  1. Disable Explicit GC. Explicit GC is a bad coding practice, it never helps. Use -XX:+DisableExplicitGC.

  2. Enable Full GC logging. Lightweight yet powerful.

    • Compute Live Data Set, Allocation Rate, and Promotion Rate. This will tell you if you need a bigger Heap or if your eg. Young Gen is too small, or if your Survivor spaces are overflowing, etc.
    • Compute total GC time, it should be <5% of total running time.
    • Use -XX:+PrintTenuringDistribution -XX:+UnlockDiagnosticVMOptions -XX:+LogVMOutput -XX:LogFile=jvm.log -XX:+HeapDumpOnOutOfMemoryError -Xloggc:gc.log -XX:+PrintGCTimeStamps -XX:+PrintGCDetails -showversion
  3. Consider additional means of collecting information about your GC. Logging is fine but there are sometimes available lightweight command-line tools that will give you even more insight. Eg. jstat for Hotspot which will show you occupation/capacity of Eden, Survivor and Old Gen.

  4. Collect Class Histograms These are lightweigh and will show you the content of the heap. You can take snapshots whenever you notice some strange GC activity, or you can take them before/after Full GC:

    • Content of the OldGen space: You can find out which objects reside in the OldGen. You need to print histograms before and after Full GC. And since a YoungGen collection is executed before the Full GC, these Histograms will show you the content of the Old generation. Use -XX:+PrintClassHistogramBeforeFullGC -XX:+PrintClassHistogramAfterFullGC.
    • Detecting prematurely promoted objects: To determine if any instances are promoted early, you need to study the Histograms to see which classes are expected to reside in the OldGen and which classes should be seen only in the YoungGen. This cannot be done automatically, you need to reason about the purpose of each class and its instance to determine if the object is temporary or not.
  5. Consider different GC Algorithm. The VMs usually come with several different GC implementations that are providing various tradeoffs : throughput, footprint, pause-less/short-pauses, real-time, etc. Consider the options you have and pick the one that suites your needs.

  6. Beware of finalize(). Check that GC keeps up with classes using finalize(). The execution of this method may be quite costly and this can impact GC and application throughput.

  7. Heap Dumps. This is the first step that is heavyweight and will impact the running application. Collect the Heap Dump to further study the heap content or to confirm a hypothesis observed in step 4.

Resources used:

Books:

Talks/Articles:

Mailing Lists:

AFAIK when a GC is doing its thing the VM blocks all running threads -- or at least when it is compacting the heap. Is this the case in modern implementions of the CLR and the JVM (Production versions as of January 2010) ? Please do not provide basic links on GC as I understand the rudimentary workings.

I assume global locking is the case as when compaction occurs references might be invalid during the move period, and it seems simplest just to lock the entire heap (i.e., indirectly by blocking all threads). I can imagine more robust mechanisms, but KISS often prevails.

If I am incorrect my question would be answered by a simple explanation of the strategy used to minimise blocking. If my assumption is correct please provide some insight on the following two questions:

  1. If this is indeed the behaviour, how do heavyweight enterprise engines like JBOSS and Glassfish maintain a consistantly high TPS rate ? I did some googling on JBOSS and I was expecting to find something on a APACHE like memory allocator suited for web processing.

  2. In the face of NUMA-esque architectures (potentially the near future) this sounds like a disaster unless the processes are CPU bound by thread and memory-allocation.

The answer is that this depends on the garbage collection algorithms used. In some cases, you are correct that all threads are stopped during GC. In other cases, you are incorrect in that garbage collection proceeds while normal threads are running. To understand how GC's achieve that, you need a detailed understanding of the theory and terminology of garbage collectors, combined with an understanding of the specific collector. It is simply not amenable to a simple explanation.

Oh yes, and it is worth pointing out that many modern collectors don't have a compaction phase per-se. Rather they work by copying live objects to a new "space" and zeroing the old "space" when they are done.

If I am incorrect my question would be answered by a simple explanation of the strategy used to minimise blocking.

If you really want to understand how garbage collectors work, I recommend:

... and beware that finding accurate, detailed, public descriptions of the internals of production garbage collectors is not easy. (Though in the case of the Hotspot GC's, you can look at the source code ...)

EDIT: in response to the OP's comment ...

"It seems it is as I thought -- there is no getting around the "stop the world" part."

It depends. In the case of the Java 6 Concurrent Collector, there are two pauses during the marking of the roots (including stacks), and then marking / copying of other objects proceeds in parallel. For other kinds of concurrent collector, read or write barriers are used while the collector is running to trap situations where the collector and application threads would otherwise interfere with each other. I don't have my copy of [Jones] here right now, but I also recall that it is possible to make the "stop the world" interval negligible ... at the cost of more expensive pointer operations and/or not collecting all garbage.

Does anyone know a proper resource to read on the available garbage collection mechanisms in java? So far I found a couple of websites but they did not contain a comprehensive description with respect to when to use which and what the implementation was. (I am referring to Oracle's jdk)

As of today, there are 4 GC algorithms available in the Java Hotspot VM:

  • The Serial GC - recommended for client-style applications that do not have low pause time requirements.
  • The Parallel GC - use when the throughput matters.
  • The Mostly-Concurrent GC (also known as Concurrent Mark-Sweep GC(CMS)) - use when the latency matters.
  • The Garbage First GC (G1) - new GC algorithm, for CMS replacement.

You can find more information about these GC algorithms in the references below.

Books:

  • Java Performance - practical guide, contains chapters on GC, explains comprehensively when and how to use various Hotspot GC algorithms,
  • The Garbage Collection Handbook - Garbage-Collection theory explained, mentions all available GC techniques.

Talks/Articles:

Mailing List:

Just a quick question on the memory usage of the play framework. I have a production instance, which appears to use 680768 kB of memory. Most of it is located in the swap.

The (virtual) server has about 750 MB, but also runs the MySQL server and 12 Apache virtual servers. Sometimes becomes temporary unrespondent (or very slow) for short periods. I guess it is because of the swapping (it is not the CPU).

Does the framework need that much memory? I could limit the memory usage with a JVM parameter -Xmx256m or so, but what value to put in, and what is the reason it uses so much memory?

This is the usage by Play! before and after start:

Java: ~~~~~ Version: 1.6.0_26 Home: /usr/lib/jvm/java-6-sun-1.6.0.26/jre Max memory: 194641920 Free memory: 11813896 Total memory: 30588928 Available processors: 2

After restart: Java: ~~~~~ Version: 1.6.0_26 Home: /usr/lib/jvm/java-6-sun-1.6.0.26/jre Max memory: 194641920 Free memory: 9893688 Total memory: 21946368 Available processors: 2

I am assuming that the 680768 kB of memory that you are reporting is from an OS tool like ps or task manager. The total amount of memory used by the JVM is not causing the temporary freezing of the app. The likely cause of the pause is that the JVM Garbage collector is running a full GC which will suspend all threads in the JVM which the full GC is running (unless you have a concurrent gc configured).

You should run the JVM running the playframework with -verbosegc -XX:+PrintGCDetails to see what the GC is doing.

Your question "Does the Play Framework need that much memory" can not be answered because the amount of memory used will depend on what your application is doing on a pre request basis. Also the JVM will let the heap run down and then do a GC cycle to clean up the Heap. A well behaved JVM app should show a saw tooth pattern on the GC graph.

I don't know which JVM you are using if you are using the hotspot VM read the JVM tunning guide. http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html You generally need to understand the following GC concepts before reading the JVM tuning guide for the guide to make sense.

  • Mark and Sweep Garbage Collection
  • Mark, Sweep and Compact Garbage Collection
  • Copy collector
  • Generational Garbage Collection
  • Parallel Garbage Collection
  • Concurrent Garbage Collection

http://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795/ is probably a good book on this subject

A couple of free tools that ship with the hotspot JVM that you can use include jconsole, and jvisualvm. jvisualvm has a nice plugin called VisualGC which is great at learning how the hotspot vm manages memory.

Could anyone advice a book (or any other source) that would thoroughly reveal internals of JVM memory management & garbage collection (optimization, work, circular references, pecularities, discussions for various JVM impls...)?

[What I've found so far are separate articles devoted to various aspects but no weighty tome :). Some good materials for Hotspot implementation are here. ]

Thanks a lot for any advice you give.

If you look for a vendor-independent resource revealing and thoroughly describing all the various GC algorithms ever researched/designed, I recommend:

  • The Garbage Collection Handbook - Explain theory and implementation of the main GC research that was there since the first GC algorithm ever designed. References also related research articles where you can find all the nasty details. I really like that book, I think that THIS IS A BIBLE of all the GC-related research.

I am studying GC implementations, and I'm currently looking for references and good open-source GC examples to base in.

Is there any good and simple generational GC implementation ? The second best thing would be good resources and guidelines!

Thank you!

I've wrote the Qish garbage collector (not really maintained any more, but feel free to ask). It is a free copying generational GC for C (with some coding styles restrictions).

The GCC MELT [meta-]plugin (free, GPLv3 licensed), providing a high level language, MELT, to extend the GCC compiler, also has a copying generational GC above the existing Ggc garbage collector of GCC. Look into gcc/melt-runtime.c

With generational copying GC, generating the application's code in C is quite useful. See my DSL2011 paper on MELT

Feel free to ask me more, I love talking about my GC-s.

Of course, reading the Garbage Collection Handbook: The Art of Automatic Memory Management (Jones, Hosking, Moss) [ISBN-13: 978-1420082791] is a must

PS. Debugging a generational copying GC is painful.

I have a Java app which shows different GC behaviour in different environments. In one environment, the heap usage graph is a slow sawtooth with major GCs every 10 hours or so, only when the heap is >90% full. In another environment, the JVM does major GCs every hour on the dot (the heap is normally between 10% and 30% at these times).

My question is, what are the factors which cause the JVM to decide to do a major GC?

Obviously it collects when the heap is nearly full, but there is some other cause at play which I am guessing is related to an hourly scheduled task within my app (although there is no spike in memory usage at this time).

I assume GC behaviour depends heavily on the JVM; I am using:

  • Java HotSpot(TM) 64-Bit Server VM 1.7.0_21 Oracle Corporation
  • No specific GC options, so using the default settings for 64-bit server (PS MarkSweep and PS Scavenge)

Other info:

  • This is a web app running in Tomcat 6.
  • Perm gen hovers around 10% in both environments.
  • The environment with the sawtooth behaviour has 7Gb max heap, the other has 14Gb.

Please, no guesswork. The JVM must have rules for deciding when to perform a major GC, and these rules must be encoded deep in the source somewhere. If anyone knows what they are, or where they are documented, please share!

Garbage collection is a pretty complicated topic, and while you could learn all the details about this, I think what’s happening in your case is pretty simple.

Sun’s Garbage Collection Tuning guide, under the “Explicit Garbage Collection” heading, warns:

applications can interact with garbage collection … by invoking full garbage collections explicitly … This can force a major collection to be done when it may not be necessary … One of the most commonly encountered uses of explicit garbage collection occurs with RMI … RMI forces full collections periodically

That guide says that the default time between garbage collections is one minute, but the sun.rmi Properties reference, under sun.rmi.dgc.server.gcInterval says:

The default value is 3600000 milliseconds (one hour).

If you’re seeing major collections every hour in one application but not another, it’s probably because the application is using RMI, possibly only internally, and you haven’t added -XX:+DisableExplicitGC to the startup flags.

Disable explicit GC, or test this hypothesis by setting -Dsun.rmi.dgc.server.gcInterval=7200000 and observing if GCs happen every two hours instead.

My application processes thousands of messages and uses dlopen / dlclose etc to call functions in shared libraries at runtime.

I have been analysing the memory at runtime and it seems (as I expected) that dlclose() does not free any malloc'ed memory after the close. So I have a rather bad memory leak....

The problem is these shared libs were written by someone else and I am not allowed to change the source. Is there any way around this? I suppose I could call a "subprocess" to process the message and then when it terminates the memory will dissappear for that subprocess....

Any other ideas?

Thanks for the help

Lynton

I believe it is the memory allocated by the shared library which you are dlclose-ing which is staying, and you have no simple way to remove it (because you don't know which other parts of your process -e.g. which others dlopen-ed libraries is using it). If you want to understand more, read a good book on Garbage Collection, or at least the wikipage. Being a memory useful to the process is a global property of the entire process, not of particular libraries.

However, some libraries have conventions regarding memory usage, and might offer you the facility of cleaning up memory and resources. Others libraries don't release resources. Some libraries give you the ability to give as parameters the allocation routines they are calling.

You might consider using the Boehm conservative garbage collector or chase your leaks with an utility like valgrind.

Good luck, since your problem has no general solution. Perhaps telling us more about the actual libraries you are dlopen-ing might help.

And of course, there is the work-around of restarting from time to time your process.

Probably this is a silly question.
When a object is marked for garbage collection, does java also marks the contained objects for garbage collection?

I mean,

class ContainerClass {
    ContainedClass obj1, obj2;  
    //Constructor
    ContainerClass() {
    obj1 = new ContainedClass ();
    obj2 = new ContainedClass ();
    }
  // main
    public static void main( String args[]) {
        ContainerClass  c = new ContainerClass();
        c = null ; // c is mared for GC. The question is c.obj1 and c.obj2 is also marked?
    }   
}

Does java perform GC recursively ?

No. A decent garbage collector does not use simple recursion for marking. If it did, then marking long linked lists would require the marking algorithm to use a very deep stack to mark it. That would be a significant problem.

There are a number of strategies that GC implementors can use to avoid excessive recursion:

  • You don't actually use recursion. You use a mark stack and an iterative algorithm ... which is more space efficient.
  • Tricks can be used to minimize stack depth when traversing deep lists ... if you know where the depth is; e.g. which is the next field.
  • The Knuth and Boehm-Demers-Weiser have ways of dealing with an overflowing mark stack that involve spilling the stack and then picking up the pieces.
  • The Deutsch-Schorr-Waite algorithm uses pointer reversal and hence no mark stack at all.
  • and so on.

If you want more details, refer to "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by Richard Jones and Rafael Lins, 1996. (There's a new GC book called "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, Antony Hosking and Eliot Moss due out later this year!!)

(Nit pick: the GC doesn't mark objects for garbage collection. It marks them for as non-garbage ... and throws away the objects that are NOT marked.)