Design Choices
A number of choices must be made when designing or selecting a garbage collection algorithm:
• Serial versus Parallel
With serial collection, only one thing happens at a time. For example, even when multiple CPUs are
available, only one is utilized to perform the collection. When
parallel collection is used, the task of
garbage collection is split into parts and those subparts are executed simultaneously, on different
CPUs. The simultaneous operation enables the collection to be done more quickly, at the expense of
some additional complexity and potential fragmentation.
• Concurrent versus Stop-the-world
When stop-the-world garbage collection is performed, execution of the application is completely
suspended during the collection. Alternatively, one or more garbage collection tasks can be executed
concurrently, that is, simultaneously, with the application. Typically, a concurrent garbage collector
does most of its work concurrently, but may also occasionally have to do a few short stop-the-world
pauses. Stop-the-world garbage collection is simpler than concurrent collection, since the heap is
frozen and objects are not changing during the collection. Its disadvantage is that it may be
undesirable for some applications to be paused. Correspondingly, the pause times are shorter when
garbage collection is done concurrently, but the collector must take extra care, as it is operating over
objects that might be updated at the same time by the application. This adds some overhead to
concurrent collectors that affects performance and requires a larger heap size.
• Compacting versus Non-compacting versus Copying
After a garbage collector has determined which objects in memory are live and which are garbage, it
can compact the memory, moving all the live objects together and completely reclaiming the
remaining memory. After compaction, it is easy and fast to allocate a new object at the first free
location. A simple pointer can be utilized to keep track of the next location available for object
allocation. In contrast with a compacting collector, a
non-compacting collector releases the space
utilized by garbage objects in-place, i.e., it does not move all live objects to create a large reclaimed
region in the same way a compacting collector does. The benefit is faster completion of garbage
collection, but the drawback is potential fragmentation. In general, it is more expensive to allocate
from a heap with in-place deallocation than from a compacted heap. It may be necessary to search the
heap for a contiguous area of memory sufficiently large to accommodate the new object. A third
alternative is a
copying collector, which copies (or evacuates) live objects to a different memory area.
The bene
fit is that the source area can then be considered empty and available for fast and easy
subsequent alloca
tions
, but the dr
awbac
k is the additional time r
equired for copying and the extra
space that may be required.
Performance Metrics
Several metrics are utilized to evaluate garbage collector performance, including:
• Throughput—the percentage of total time not spent in garbage collection, considered over long
periods of time.
• Garbage collection overhead—the inverse of throughput, that is, the percentage of total time spent in
garbage collection.
• Pause time—the length of time during which application execution is stopped while garbage
collection is occurring.
• Frequency of collection—how often collection occurs, relative to application execution.
• Footprint—a measure of size, such as heap size.
• Promptness—the time between when an object becomes garbage and when the memory becomes
available.
Sun Microsystems, Inc.
5
Garbage Collection