
Introduction
Simple trace-based garbage collectors perform stop-the-world garbage collection, which can cause long pauses in user program execution. By collecting waste one portion at a time, we can shorten the length of the pauses.
We can divide work in two ways: time and space. The work is divided in time by interleaving garbage collection with mutation or space by collecting a portion of the garbage at a time. The first is referred to as incremental collection, whereas the second is referred to as a partial collection.
We will discuss the following Short-Pause Garbage Collection methods:
- Incremental Garbage Collection
- Partial-Collection Basics
- Generational Garbage Collection
- The Train Algorithm
Also see, Advanced Topics in Garbage Collection
Incremental Garbage Collection
An incremental garbage collector breaks up the reachability analysis into smaller units, which allows the mutator to run between them.
Incremental collectors are conservative. A trash collector must not collect non-junk objects, but it is not required to collect all garbage in each round. The garbage that remains after collection is called floating garbage. Of course, minimizing floating garbage is preferable.
An incremental collector, in particular, should not leave any garbage behind that was not available at the start of the collection cycle. Suppose we can be certain of such a collection guarantee. In that case, any garbage that isn't collected in one round will be collected in the next, and no memory will be released due to this garbage collection method.
In other words, incremental garbage collectors play it safe by overestimating the number of objects that can be reached. They process the program's root set atomically first, without the mutator interfering. After locating the initial set of unscanned objects, the mutator's operations are interleaved with the tracing step. During this time, any actions taken by the mutator that may affect reachability are stored in a side table as the collector can make the necessary adjustments when it resumes execution. If space runs out before tracing is finished, the collector ends the tracing process without allowing the mutator to run. In any case, after tracing is completed, space is atomically reclaimed.