Editing Tracing garbage collection (section)

== Basic algorithm ==
Tracing collectors are so called because they trace through the working set of memory. These garbage collectors perform collection in cycles. It is common for cycles to be triggered when there is not enough free memory for the memory manager to satisfy an allocation request. But cycles can often be requested by the mutator directly or run on a time schedule. The original method involves a naïve ''mark-and-sweep'' in which the entire memory set is touched several times.

=== Naïve mark-and-sweep ===
[[File:Animation of the Naive Mark and Sweep Garbage Collector Algorithm.gif|thumb|upright=1.5|Naive mark-and-sweep in action on a [[Dynamic memory allocation#Manual memory management|heap]] containing eight [[Object (computer science)|objects]].  Arrows represent [[Reference (computer science)#References in object oriented languages|object references]]. Circles represent the objects themselves.  Objects #1, #2, #3, #4, and #6 are strongly referenced from the root set. On the other hand, objects #5, #7, and #8 are not strongly referenced either directly or indirectly from the root set; therefore, they are garbage. ]]

In the naive mark-and-sweep method, each object in memory has a flag (typically a single bit) reserved for garbage collection use only. This flag is always ''cleared'', except during the collection cycle. 

The first stage is the ''mark stage'' which does a tree traversal of the entire 'root set' and marks each object that is pointed to by a root as being 'in-use'. All objects that those objects point to, and so on, are marked as well, so that every object that is reachable via the root set is marked.

In the second stage, the ''sweep stage'', all memory is scanned from start to finish, examining all free or used blocks; those not marked as being 'in-use' are not reachable by any roots, and their memory is freed. For objects which were marked in-use, the in-use flag is cleared, preparing for the next cycle.

This method has several disadvantages, the most notable being that the entire system must be suspended during collection; no mutation of the working set can be allowed. This can cause programs to 'freeze' periodically (and generally unpredictably), making some real-time and time-critical applications impossible. In addition, the entire working memory must be examined, much of it twice, potentially causing problems in [[paged memory]] systems.

=== {{Anchor|TRI-COLOR}}Tri-color marking ===
[[File:Animation of tri-color garbage collection.gif|thumb|upright=1.5|
An example of tri-color marking on a heap with 8 objects. 
White, grey, and black objects are represented by light-grey, yellow, and blue, respectively.]]

Because of these performance problems, most modern tracing garbage collectors implement some variant of the ''tri-color marking'' [[abstraction (computer science)|abstraction]], but simple collectors (such as the ''mark-and-sweep'' collector) often do not make this abstraction explicit.  Tri-color marking works as described below.

Three sets are created{{snd}} ''white'', ''black'' and ''grey'':

* The white set, or ''condemned set'', is the set of objects that are candidates for having their memory recycled.
* The black set is the set of objects that can be shown to have no outgoing references to objects in the white set, and to be reachable from the roots. Objects in the black set are not candidates for collection.
* The grey set contains all objects reachable from the roots but yet to be scanned for references to "white" objects. Since they are known to be reachable from the roots, they cannot be garbage-collected and will end up in the black set after being scanned. 

In many algorithms, initially the black set starts as empty, the grey set is the set of objects which are directly referenced from roots and the white set includes all other objects. Every object in memory is at all times in exactly one of the three sets. The algorithm proceeds as following:

# Pick an object o from the grey set
# Move each white object that o references to the grey set. This ensures that neither this object nor any object it references can be garbage-collected.
# Move o to the black set
# Repeat the last three steps until the grey set is empty.

When the grey set is empty, the scan is complete; the black objects are reachable from the roots, while the white objects are not and can be garbage-collected.

Since all objects not immediately reachable from the roots are added to the white set, and objects can only move from white to grey and from grey to black, the algorithm preserves an important invariant{{snd}} no black objects reference white objects. This ensures that the white objects can be freed once the grey set is empty. This is called ''the tri-color invariant''. Some variations on the algorithm do not preserve this invariant but use a modified form for which all the important properties hold.

The tri-color method has an important advantage{{snd}} it can be performed "on-the-fly", without halting the system for significant periods of time. This is accomplished by marking objects as they are allocated and during mutation, maintaining the various sets. By monitoring the size of the sets, the system can perform garbage collection periodically, rather than as needed. Also, the need to touch the entire working set on each cycle is avoided.