HnxGC - an accurate, pauseless & deterministic garbage collector

• Home
• Downloads
• Bookmark
• Contact

Introduction

On This Page

Garbage collection (also known as GC) is a form of automatic memory management. Contrary to manual memory management that requires programmers to specify which objects to be de-allocated and returned to the system by using a "free" or "delete" statement; automatic memory management frees programmers from this burden. An object is considered garbage (and subject to reclamation) if it is not reachable by the application program. Garbage collection system automatically reclaims managed objects when they are no longer being used.

However, garbage collections still have many technical obstacles that need to be solved.

ISSUES WE FACE

There is a lack of accurate garbage collection for universal C++ programming. In order to identify unreachable objects, garbage collector needs to know all effective references to objects, such as references in execution stacks and CPU registers. Not every C++ compiler provides reference layout information for garbage collector, therefore conservative garbage collectors 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 uncollected. Further, some optimization conducted by C++ compiler could make some pointers undetectable by conservative garbage collector, and might lead to crash at certain points.

RAII is conflicting with garbage collection. Resource Acquisition Is Initialization (RAII) design pattern is widely used in C++. It combines acquisition and release of resources with initialization and uninitialization of objects. But, RAII are not welcomed in most garbage collections (e.g. Java, .NET), either because of the high cost of running destructors of objects, or the inborn undeterministic characteristic that the programmers hardly know when, where and in which order destructors will be executed.

Memory or other associated resources are not released timely. When an object becomes orphan - the last reference to the object is dropped, the object is not reclaimed promptly in a non reference-counting based garbage collection. Incremental GC cannot guarantee the orphan object is promptly reclaimed; performing a thorough collection too frequently usually is not efficient both in time and space. The delay of reclaiming orphan objects often leads to waste of memory and system resources, such as leaving a large native data block of geographic picture uncollected, or holding unnecessary opened file handles or network connections. Alternative solutions, such as using specific function calls to explicitly destroy unused objects may help, but are awkward and still have many pitfalls.

Garbage collection interrupts the execution of application program to perform some tasks, such as taking a snapshot of application threads at initial-mark phase and to capture any changes at re-mark phase. It is hard to predict when garbage collector will kick in and interrupt application threads even all these threads are performing some works that is unrelated to managed objects.

Some garbage collections also bring in other issues, such as disallow multiple-inheritance, object composition, array union, bit-fields, etc., which is important and widely used for C++ programmers. Virtual machine even with Just-In-Time compiler is not as fast as native compiler, nor can it make deep-level optimization that takes too much time for a runtime environment.

HNXGC APPROACH

We develop HnxGC to address the above issues. It can perform accurate garbage collection without any special support from C++ compiler. Any C++ compiler that is compliance to standard C++ language can be used to build your application program with our HnxGC library. We have tested our HnxGC with many versions of C++ compilers, such as Visual C++ and GNU C++ for x86, x64, IA64, ARM, etc. In fact, our GC algorithm does not require any C++ features, but application source code just need C++ template to support several types of smart pointers to help application threads cooperate with garbage collector. If replaced these types of smart pointers by some other mechanisms, such as using a preprocessor tools to handle pointer operations, you can use HnxGC with other language that does not support smart pointers, like C or BASIC.

HnxGC can identify all effective references that keep object reachable and alive. There is no spurious pointer retaining garbage uncollected. All unreachable objects will be identified and collected by the system, no leak of garbage, and in turn all associated unmanaged resources will be freed at the execution of destructors of these objects. Also, there is no restriction on optimization level of C++ compiler, no risk of crashing application program caused by some effective reference misinterpreted as non-pointer data.

As a result of the deterministic feature of HnxGC, application program can embrace garbage collection now with RAII design pattern as well as it does in a traditional C++ language. HnxGC will promptly reclaim and execute the destructor of an object when the last reference to the object is dropped. Cyclic unreachable objects are reclaimed by tracing garbage collection. Application program can declare dependence rules for each object to control the destructing ordering of cyclic garbage objects. HnxGC will figure out an ordering that satisfies all user-declared rules. This behavior ensures the safety that garbage object will not be destroyed when some other executions of destructors of garbage objects are depended on them. Thus, we provide a safe environment that unmanaged resources can be freed in the destructor of managed objects.

We provide a multi-threading version of HnxGC that is lock-free (non-blocking) with no root-set scanning. Application thread will never be interrupted, suspended, blocked or forced to spin-waiting by our HnxGC collector, no matter in a multi-processors or an uni-processor environment. That means if you choose to run garbage collection at a lower priority than application thread, then your application will not be interrupted by the collector except allocating memory from managed memory pool or destructing objects in application threads, such as when an object becomes orphan or application mandatory destroys a live object. You don't worry about your critical execution being interrupted by garbage collector. You can control when and how garbage collection is performed, and at which priority level. Garbage collector priority level can be mixed with your application threads to meet your specific requirements.

Our garbage collector is just running as a normal application thread without any privileges. Pointer assignments that changes the graph of reference relationship are delicately designed to isolate it from the concurrent garbage collector. There is no traditional synchronization mechanism, such as exclusive-lock or spin-lock, used between the pointer assignment operations and garbage collector. We just use atomic primitives such as CMPXCHG of x86 processor architecture to cooperate with garbage collector. In multiple-processors architecture, we further apply our unique Global Memory Fence technique to eliminate the need of memory ordering requirement in some modern processors, such as IA64, to improve performance.

We use reference counting (RC) in application thread with a concurrent mark-and-sweep collector to achieve above goals. In our approach, reference counting not only counts the number of references to an object, but also counts the number of references to the object from the root-set area. We separate all memory of application program into two categories, the managed memory pool and the rest (root-set area). Managed objects are allocated from managed memory pool via our HnxGC API. All others memory blocks are considered as in the root-set area, which includes program's execution stack, initialized or uninitialized static memory sections, memory allocated from native memory pool via traditional ways, such as `new' operator in C++.

Reference coming from root-set area can `move' from one place to another within the root-set area without triggering any RC operations. This design significantly reduces the cost of RC operations. Some most-frequently-used reference operations, such as passing references as parameters or return values between function calls, are removed and will not cause any cost of RC operation.

HnxGC supports object composition, multiple-inheritance, and object arrays. This will reduce the number of use of indirect pointer access to managed object, as in Java and .NET platform. The access of object is faster and memory foot-print is reduced. HnxGC can trace union objects and bit-fields, which is normally being considered as hidden-pointers and forbidden in many garbage collectors. You can use almost all traditional C++ memory mechanisms in your application design, concentrate on your application logic, provide high performance and satisfaction to your end-customers.

LIST OF FEATURES

Click to view the "Hello world"

Want to know about the internal of HnxGC?