A garbage collector for C++

[Mingnan G.]

Hello everyone.

I have written a garbage collector for standard C++ application. It has
following main features.

1) Deterministic Finalization
Providing deterministic finalization, the system can manage resources
as well as objects. The programming style is clear and easy, conforming
to RAII (Resource Acquisition Is Initialization) idiom of C++
programmers. The memory usage is very efficient, acyclic garbage is
reclaimed when the last reference to it is removed. A well-designed
application, which eliminates cyclic data structure, does not need
expensive garbage collection and is always running with minimum memory
usage.

2) Accurate GC for C++
It is a fully accurate tracing garbage collector. All garbage objects
are identified by the system, no conservative stack frame guessing.
Fully C++ optimization compiler support.

3) No Pause (less than 1us)
In this system, all application codes automatically become fully
interruptible and GC-Safe. Therefore, scavenge can start at any place
without rendezvous requirement. A special concurrent tracing garbage
collector successfully evades root-set scanning, and does not cause
suspension of any thread at all. In the worst racing case, the latency
is less than one microsecond (not millisecond). It is very satisfied
for real-time systems.

4) Small Overhead
The runtime cost of application threads is far less than a normal
reference counting. If there is no concurrently running scavenging
action, there is no write-barrier overhead, no strong memory ordering
requirement, no synchronization overhead. There is no extra code or
data structure injected for GC safe point. The whole system does not
require strong memory ordering, it is suitable for most modern
processor architecture. Multi-processor concurrency can be further
exploited by the multi-threading property of mutator and collector.

5) Compatible Object Model
As well as conventional C++, the system supports multiple-inheritance,
object as member variables, and object arrays. Support C++ raw pointer,
unions, bit-fields and hidden pointers. Support C++ templates. Support
native object and tracing.

6) Widely Portable
Even conducting an accurate tracing, the system does not require any
special information from compiler. Application can use any standard C++
compiler, such as Visual C++ 8 and GCC. There is no special platform
requirement, such as Win32 system call: SuspendThread, GetWriteWatch,
etc. Even virtual memory support is not necessary. Thus, it can be
ported to a wider area.

Does anyone have any interest in this system? Any comments are welcome!

Mingnan G.

[Chris Thomasson]

Mingnan G. wrote:

I am glad to see your kindly messages and suggestions, thanks very
much.

I am still carefully reading your posts and links. Followings are
questions I know to answer.

What sort of transactions occur between your collector and its mutators during a "scavenge" operation?

During a "scavenge" operation, the system uses multi-threading
synchronization mechanism between collector and mutators. There is some
overhead. However, since most objects are acyclic, scavenge operation
need not run as frequently as prior-art garbage collector. I recommend
tracing garbage collection runs with higher priority than normal
application threads, but lower than real-time threads. So that,
expensive tracing GC can finished sooner, and real-time threads are not
affected.

Do your mutators have any #StoreLoad dependencies during a scavenge operation? I take it that the collector can indeed interrupt mutators during scavenges, correct?

Mutators have #StoreLoad dependencies during a scavenge operation. The
collector can interrupt any application threads at any place, and start
a tracing collection without delay.

Humm... I am curious as to how you are implementing the interrupt logic???

[Mingnan G.]

Interrupt logic in this system is quite straight. All application code
is fully interruptible, so the mutator can be interrupted at any place.
If an application thread invoke the garbage collection, the thread
immediately enter the scavenge stage and starts traversals. Other
mutators keep running concurrently with the thread, which become the
collector. During the scavenge stage you can do anything, including
creating new threads, creating new GC objects, etc. Higher priority
threads might preempt the collector at any place, but this will cause
the collector running longer to finish a collection.

Mingnan G.

[Mingnan G.]

I do not quite understand your "per-epoch" smart pointers. In this
system, smart pointers physically is just a word of object address. It
traps assignment to pointers. Converting a strong smart pointer to a
raw pointer has no overhead through C++ compiler's optimization, just
like normal C/C++ pointer casting. On the contrary, converting a raw
pointer to strong smart pointer will indead cause a little overhead.
The overhead is very small and in most cases programmers should not
convert a raw pointer to a strong pointer. A strong pointer normally
should derived from another strong pointer. Convertion between strong
pointers is faster than converting from raw pointers.

Mingnan G.

[Rui Maciel]

Mingnan G. wrote:

... you could just post links to download and documentation.

Thanks for your kind advice. I am doing that currently. I need a place
to put my documentation and source code, and I need some time.

Why not release it as a sourceforge project? Sourceforge was created for
that exact purpose. It offers web hosting, CVS/subversion, project forums,
bug tracking and some other stuff I don't remember right now.

Here is the URL: http://sourceforge.net/
Hope this helps
Rui maciel
--
Running Kubuntu 5.10 with KDE 3.5.2 and proud of it.
jabber:ru****** **@jabber.org