2. Algorithm Overview
There are basically two styles of garbage collection algorithm: reference counting and tracing collectors.
Reference counting (RC) maintains the count of all effective references to an object, and when the count falls to zero, the system reclaims the object. A non-deferred RC algorithm keeps the counter instantly reflecting the number of references, and can quickly release scarce resources such as operating system objects. Programmers can predict when and where an object is collected with the counter value dropped to zero. It is known as deterministic reclamation feature.
Incrementing and decrementing reference counts every time a reference is created or destroyed can significantly impede performance. To improve performance, deferred RC algorithms postpone performing reference counts increments and decrements, then merge or cancel some of these operations. But, they lose the merit of deterministic reclamation. It is neither able to release scarce resources quickly, nor maintain a predictable reclamation ordering of objects. To conserve deterministic reclamation, we choose non-deferred reference counting and use an alternative method to reduce the cost.
Without resorting to some type of tracing techniques, to our knowledge, any pure reference counting variations is not complete. Circular referenced garbage can not be collected by RC collector. David F. Bacon describes a novel cyclecollection algorithm by tracing suspect cycle objects. But, in order to provide an efficient way for programmers to determine that all stale garbage are collected, we choose to use a general tracing garbage collector in our approach to collect circular garbage.
Tracing garbage collector traces references from the rootset of application program, recursively traverses referents and their descendants to determine which objects are reachable, then reclaims all remaining objects. Traditionally, rootset is defined as a set of memory that are always accessible, typically the program's stack, processors' registers and static storage. In our approach, we broaden it as extended root-set to all areas outside the managed heap, which will be explained detailedly in Section 3.
One of our goals is to perform accurate garbage collection in almost, if not all, C++ language environments, including GNU g++, Microsoft VC++, IntelR C++, etc. We need a common way to determine references in the rootset of application program. Without the help of compilers, we cannot accurately determine which processors' register or which memory word in the program's stacks is a valid reference to a managed object at a particular point of execution. Therefore, we choose to discard determining references in the root-set, then steer to an alternative solution. During the execution of application program, managed objects that are referenced from the extended root-set are marked out; at the tracing garbage collection, the system distinguishes these marked-out objects, treats them as root objects, traverses them and their descendants to determine unreachable garbage. More specifically, we use reference counting technique to count the number of references from outside of the managed heap. When the count is not zero, it means that the object is marked-out and belongs to root objects of tracing collection. Therefore, by dynamically marking out root objects in application program execution, tracing collector can treat the managed heap boundary as the consideration boundary of tracing garbage collection, it need not to know about the outside of the managed heap and avoids analyzing complicated outside environments, such as program's stack and processors' registers.
Since the collector in our approach is only concerning the managed heap, thus we can further optimize and reduce the cost of reference counting in the extended root-set. If an reference operation does not changes the effective state of managed heap (collection of managed objects), we can optimize it freely without concerning any garbage collection issue. From the view of garbage collector, transferring a reference between two pointers within extended root-set does not change the state of referent, and the cost of RC can be removed. Multiple references in extended root-set to a managed object, especially from one thread, can be optimized by using one effective reference and multiple weak references. As a result, passing references between function calls as input, output parameters or return value can be optimized and does not incur any reference counting operations and costs. More optimizations can be applied manually or by a compiler with more intelligent capability of static analysis.
A non-deferred reference counting is an atomic operation, so the managed heap state is always consistent and all application codes are gc-safe. With a read/write barrier or synchronization mechanism, we build a full concurrent tracing collector by a variation of three-color forward incremental update algorithm. Details will be discussed in Section 5.
Some other issues and solutions, such as finalization ordering, managed object model, etc. are addressed in Section 6.