Sunday, January 13, 2013

Java garbage collection, generations and collectors

A "garbage collector" is the memory management system that gets rid of the objects that don't have any reference (dead object), make sure objects with reference (live object) are not removed and allocates memory space to new objects. this discussion focuses on the garbage collection in java. The discussion includes generation division of memory and different garbage collection strategies for them available in java.


Generation 
You either die young or you live long enough to see yourself become old generation!!

In generational collection the whole memory space is divided into divisions (generations) and different algorithm is used for garbage collection on each generation depending on the special characteristics of that generation.

For java the generations are divided according to the longevity of the survival of objects. it has two main generations. the young generation and the old generation. as the name suggests, newly created objects are stuffed into young generation. if the object survives long enough (enough number of garbage collection cycle) then its promoted to old generation.

Young generation is smaller and goes through frequent garbage collection. the hypothesis here is that most object die young. so whenever the tiny young generation is filled up a garbage collection runs on that part of memory (also referred to as a minor collection) and as a result dead objects are collected and removed, at the same time live objects which have survived enough number of garbage collection cycle are moved to the old generation.

Objects that are promoted to old generation are assumed to be living longer (as they have already faced enough garbage collector zombie waves and still survived the horror!!) and as a result garbage collection on old generation are a lot less frequent. When the old fills up a full collection (referred to as a major collection) is typically done on both young and old generations.

Just from a little common sense we can conclude that young generation garbage collection will need collection algorithm which are fast and with least pauses  (as it runs frequently) and old generation garbage collection needs to be space efficient (as old gen is a lot bigger than young gen). that being said lets go through some garbage collection algorithms available in java.


Serial Collection Strategy 

As the name suggests, garbage collection is done serially, one at a time. during this the whole application (for which garbage collection is done) is paused temporarily which is also referred as stop the world strategy.

For young gen it simply collects garbage serially and promotes objects if they are old enough. for old generation its a bit different. first an iteration is done over the whole old gen and dead objects are marked. the next iteration removes (sweeps) the dead ones. and in the end the live objects are moved closely next to each other (mostly to make them comfortable and warm and oddly but certainly) to keep the continuous free space in old gen as  big as possible. its called "mark-sweep-compact" -ing.  


Parallel Collection Strategy

Again the name suggests it all. Garbage collection is done with multiple CPUs simultaneously. Its also known as "throughput collector" (life is all about fancy names).

For young generation, it actually runs multiple serial collection using multiple CPUs  and thats it. For old gen, it does multiple serial "mark-sweep-compact"-ing thingy mentioned before using multiple CPUs simultaneously.

If you have enough money to afford multiple CPUs and a lot of memory then you are most probably gonna use it (but of course you might have the virtuous tendency to defy common practice). Also as both here are of the "stop the world" genre, you should think about time constraints as well.

Note:  the parallel collector can be set using the -XX:+UseParallelGC command line option.


Parallel Compacting Collection Strategy

This one is the improvement over "Parallel Collection Strategy". its mainly created to improve the parallel garbage collection in old generation part. the young generation part of it is same as "Parallel Collection Strategy".

Here the old gen is divided into same sized regions. each region gets its own garbage collection thread. (But that's just the tip of the iceberg but we will try to remain simple village folk here). in brief, before any collection, first a summary is generated for each region. from left to right, its looks for a region from where on all the regions are very lightly populated (so that the expense for compacting gets low). Left to that region nothing is done. And right to that region, collecting and compacting is done.

Nonetheless this strategy is of "stop-the-world" genre as well.

Note: the parallel compacting collector can be set using the -XX:+UseParallelOldGC command line option. 


Concurrent Mark-Sweep (CMS) Collection Strategy

For the young gen its the same as "Parallel Collection" (you can see how the young are neglected these days). But the magic starts with old gen collection. The following six phases of CMS are copied from oracle site, and i found them too fit for any alteration,

There are six phases involved in the collection:

Phase 1 (Initial Checkpoint) involves stopping all the Java threads, marking all the objects directly reachable from the roots, and restarting the Java threads.

Phase 2 (Concurrent Marking) starts scanning from marked objects and transitively marks all objects reachable from the roots. The mutators are executing during the concurrent phases 2, 3, and 5 below and any objects allocated in the CMS generation during these phases (including promoted objects) are immediately marked as live.

Phase 3: During the concurrent marking phase mutators may be modifying objects. Any object that has been modified since the start of the concurrent marking phase (and which was not subsequently scanned during that phase) must be rescanned. Phase 3 (Concurrent Precleaning) scans objects that have been modified concurrently. Due to continuing mutator activity the scanning for modified cards may be done multiple times.

Phase 4 (Final Checkpoint) is a stop-the-world phase. With mutators stopped the final marking is done by scanning objects reachable from the roots and by scanning any modified objects. Note that after this phase there may be objects that have been marked but are no longer live. Such objects will survive the current collection but will be collected on the next collection.

Phase 5 (Concurrent Sweep) collects dead objects. The collection of a dead object adds the space for the object to a free list for later allocation. Coalescing of dead objects may occur at this point. Note that live objects are not moved.

Phase 6 (Resetting) clears data structures in preparation for the next collection.

(I start again) Here the Stop the world pauses in phase 1 and 4 are very small. You might have noticed CMS  doesn't do any compacting. though its time saving, the free space isn't contiguous anymore. so next time the next object cant be just put beside last object and the expense for allocation gets increased. Also uneven fragments are created. to deal with fragmentation problems, popular object size is determined and for future demand. Moreover some dead object might miss the marking (if they die just after the marker passed over them) and cause "floating garbage" (as if we didn't have enough junk already).

Special Note: Unlike other collectors CMS starts old gen collection even before it gets full.  CMS
collector starts at a time based on statistics regarding previous collection times. It can also start based on what percentage of old gen is occupied, if you set –XX:CMSInitiatingOccupancyFraction = n (n is the value indicating percentage) , in command line options. The CMS collector can be set using the -XX:+UseConcMarkSweepGC command line option.  
In summary, compared to the parallel collector, the CMS collector decreases old generation pauses—sometimes dramatically—at the expense of slightly longer young generation pauses, some reduction in throughput, and extra heap size requirements.

I think thats big enough for one blog entry. other parts of GC such as selection criteria for collector, searching for memory leaks, heap profiling, throughput, tuning etc will be discussed later.

See command line options for tuning and performance analyzing of GC here.

References:



  









4 comments:

  1. Nice article What about G1GC? Do you plan on adding information on it?

    ReplyDelete
    Replies
    1. thanx.. i am planning on writing one on young gen GC.. didnt get the time though.. i will be on it soon

      Delete