1. Algorithm - Introduction
Garbage collection (GC) means automatic reclamation of unused heap storage, a form of automatic memory management. Contrary to manual memory management that requires programmers to specify which objects to be collected, by using a "free" or "delete" statement; garbage collections free programmers from this burden. An object is considered garbage (and subject to reclamation) if it is not reachable by the application program. Managed objects are referred to as objects whose lifetimes are managed by the garbage collection system, and were reclaimed when they are no longer being used.
1.1 Issues to Be Resolved
Notwithstanding that the first garbage collection was developed more than forty years ago, there are some issues with garbage collection.
Accurate Aspect - An accurate garbage collector need to identify all effective references to an object, such as pointers in thread stacks and references in CPU registers. Not every compiler provides this information for garbage collection, for example C++, thus some implementations (referred to as conservative garbage collector) merely treat anything that might be a pointer as a pointer. However, in such system a spurious pointer might result in unpredictable amount of garbage un-reclaimed. Further, an uncooperative compiler doing optimization could make some pointers undetectable by conservative garbage collector, and might lead to crash at certain points.
Deterministic Aspect - Resource Acquisition Is Initialization (RAII) is well advocated by Object-Oriented Programming (OOP). It combines acquisition and release of resources with initialization and uninitialization of objects. Unfortunately, in most garbage-collected languages (e.g. Java, C#), it is impossible to know when an object is reclaimed. Zero-referenced objects might be retained until a full collection is carried out. This non-deterministic character raises a conflict with RAII.
Pauses Aspect - During the normal execution of application program, garbage collection may kick in and cause unpredictable pause times. The average delay of a real-time garbage collection is at around millisecond level, and the worst-case delay is unpredictable. This hinders applying garbage collection to time critical scenarios or high quality commercial products.
Space and Time Efficiency Aspect - For years, people appreciate that an applications using garbage collection technique has need of more memory than a traditional native one. One of the reasons is that the tracing garbage collection conservatively allows garbage to go un-collected between collection cycles. Memory efficiency is depended on how frequently and how thoroughly garbage collection is carried out, so it is hard to guarantee memory efficiency even by a skilled programmer. On the other side, non-deferred reference counting though can reclaim zero-referenced garbage right away, but its cost is so high that prevents it from being widely applied.
There are some other issues relating to garbage collection. Sometimes, garbage collection causes too many changes in software development, such as single inheritance, union, bit-fields, hidden pointers, etc. Sometimes, the runtime system requirements, such as virtual machine environment, are too much for a particular platform.
Thus, better and faster techniques are needed for automatic memory management.
1.2 This Work
In view of the above limitations, we propose an algorithm to provide accurate, deterministic, pause-less and efficient garbage collection for nearly all platforms.
1. It completely avoids root-set scanning, such as scanning for pointer variables in program's stacks and CPU registers. In consequence, it eliminates the need to generate information about reference layout by a compiler, and can perform accurate collection in a language that does not have built-in support of GC.
2. It supports deterministic reclamation that all resources of an object can be released immediately when the last reference to the object is dropped.
3. All application codes become fully interruptible and GCsafe. Therefore, a tracing garbage collection can start at any point without the need of rendezvous. There is no suspension of any thread at any time, and a concurrent garbage collector can guarantee a predictable maximum latency in the worst case at microsecond level on stock hardware, a great improvement over millisecond-level real-time garbage collectors.
4. Reference counting maintenances that occur in thread stack, such as passing a reference to/from function call, can be significantly removed. This optimization does not affect consistency of reference relationships in our approach.
5. It is pure software based and requires little platform services, even virtual memory is not prerequisite. As being compatible with popular and widely-used C/C++ languages, it can be used in a wide array of platforms.
The main idea is to use reference counting to collect zeroreferenced object throughout the execution of application program, and use tracing collector to collect circular referenced garbage. We made some changes and improvements on ordinary reference counting, so it can assist tracing collector to avoid root-set scanning and to achieve other essential features. The tracing collector is a mark-&-sweep variation with coalescing write barrier into reference counting operations to achieve full concurrent garbage collection.
(Note - the latest implementation of HnxGC for multi-threading uniprocessor or multiprocessors provides lock-free full concurrent collection, which is not under the coverage of this article in some aspects.)