Now, garbage collection is available for C and C++ programmers. You don't need a new language or a special compiler; it works with plain old C and C++. It's the Boehm collector. The techniques I describe in this article should work with any compiler and operating system to which Boehm has been ported. The Boehm collector works on C++ compilers, ISO/ANSI C compilers, and even pre-Standard C compilers.
What Is the Boehm Collector?
The Boehm collector is an open-source library written in C by Hans-J. Boehm. It provides a replacement for malloc, but you don't need to free memory that you allocate with the Boehm collector. You can obtain the Boehm collector at <www.hpl.hp.com/ personal/Hans_Boehm/gc>. On Unix, you install it with ./configure; make. It also installs on Windows.The Boehm collector has two headers files and one linkable library. For C, the header file is <gc.h>; for C++, it's <gc_cpp.h>. On Unix, the linkable library is -lgc. To use the Boehm collector, your programs must #include <gc.h> or <gc_cpp.h>, and you must link the program with -lgc (or whatever your platform calls the library).
The main interface to the Boehm collector is the function GC_MALLOC. Just like the malloc you know and love, GC_MALLOC allocates a block of memory and returns a pointer to it. Unlike malloc, you don't need to free memory that was allocated by GC_MALLOC. The Boehm collector will free the memory when it is appropriate to do so. It also provides a GC_FREE function that you can use to free a block of memory explicitly. In theory, you can use GC_FREE as a performance improvement. However, in the three large applications and innumerable tiny programs I've written since I began using the Boehm collector, I've found exactly one case in which GC_FREE was necessary to improve performance.
Performance
If you're curious or skeptical about the Boehm collector, try an experiment like Listing 1. In a loop, Listing 1 creates a large linked list and destroys it. It runs the loop once using malloc and free and then again using GC_MALLOC. (To free the list in the presence of garbage collection, the program just forgets about the list; there's no need to free each node.) For each allocation method, the program prints the number of lists created and destroyed, the number of seconds it looped, the rate at which lists were created and destroyed, and that rate relative to malloc's rate. (malloc's relative rate will be 1.0.) When running Listing 1 and similar programs on GNU/Linux, I've seen the Boehm collector perform 1.69 times faster than malloc/free; on OpenBSD, more than twice as fast; and on Microsoft Windows NT 4, more than 13 times faster.
Plain C
The Boehm collector provides one main function, GC_MALLOC, which is conceptually equivalent to malloc, but you don't need to free the memory. So to use the Boehm collector when programming in plain C, use GC_MALLOC and never free anything.Older libraries will allocate memory with malloc. Standard C's strdup is one such offender. You must be careful to call free on memory that those functions malloc for you, and you must be careful not to allow them to call free on memory you've allocated with GC_MALLOC. Also, the Boehm collector might not take memory that was malloced into account when determining what memory it can recycle, so it's best to rely on GC_MALLOC whenever possible [1].
If you are able to convert those old libraries to use the Boehm collector instead of malloc, the danger of mixing GC_MALLOC with free will disappear. A nice side effect of the conversions is that many lines of source code disappear; a benefit of garbage collection is that you needn't write code to guard against leaking memory in the face of exceptions.
GC_MALLOC is a bit of a bother to type, and who knows, maybe I'll use a different garbage collection system in the future. So I wrap GC_MALLOC in a function called xmalloc. I similarly wrap GC_FREE and GC_REALLOC. Listing 2 shows example implementations of these functions.
That's all you need to know to use the Boehm collector in C.
C++'s Double-Edged Sword of Destruction
C++'s destructors create some problems for garbage collectors. The problems aren't insurmountable, but you need to understand them or it will always bother you that garbage collectors can't call all your destructors for you.Notice that languages with built-in garbage collection don't use destructors. Java has destructors (called finalizers), true, but they are discouraged, and it is explicit that the programmer cannot predict when or whether Java's garbage collector will call an object's destructor. C# offers destructors and Finalize methods, but, like Java, doesn't allow programmers to call destructors directly. Python has similar semantics. Ada, Lisp, and Smalltalk don't have destructors except as implementation-specific extensions. Why do those languages avoid destructors?
A garbage collector can't guarantee that all destructors are called in the same order you'd call them explicitly. If there are referential cycles in your data, such as from a circularly linked list, a bi-directionally linked list, or a more general network of data, the garbage collector can either (1) fail to collect the memory involved or (2) collect it in some arbitrary order. What's more, isolating those networks can be difficult, so even a garbage collector that promises to collect them all might wait until the end of the program. So in the general case of using a garbage collector, you can't predict when or whether a particular block of memory will be recycled. For these reasons, languages with built-in garbage collection choose to avoid destructors.
C++ has had destructors from its beginning, and they play important roles in some programming idioms that C++ programmers use. For example, the "object creation is resource acquisition" idiom depends on them. So C++ needs destructors. It's an apparent dilemma, reconciling C++'s use of destructors with garbage collection's inability to guarantee when or whether a given destructor is called, but in practice, it isn't a problem.
For example, mutual exclusion can be implemented conveniently with a lock object on the stack. It's important that the lock object's constructor and destructor are called at appropriate times. Likewise, you usually create fstream objects on the stack, and it's important that the fstream's destructor is called to close the file. When an object is on the stack, garbage collection isn't involved at all, so its destructor will be called correctly, when your program exits the lexical block containing the object. These important cases present no conflict between destructors and garbage collection.
Even if you must allocate a new object, if you know when to call a destructor at run time, you can determine the place in the code to explicitly delete it. So the destructor will execute at the correct time, and the garbage collection system will reclaim the memory in its own time. This suggests that garbage collection is a form of memory management, destructors are part of object management, and the two don't need to overlap.
In programs without garbage collection, a common activity in destructors is to free memory, but once a program uses the Boehm collector, the destructor doesn't have this responsibility, so all the memory-management code in destructors disappears. Many destructors disappear entirely.
Boehm's C++ Interface
The Boehm collector's C++ interface is declared in a header file called <gc_cpp.h>, which comes with the Boehm collector distribution.For POD (Plain Old Data) and for classes without destructors, you can use the Boehm collector's overloaded ::operator new (GCPlacement). To allocate POD or an object under the Boehm collector's control, specify UseGC for the GCPlacement argument. For example, you could allocate an int with int *i = new (UseGC) int;. Use the new POD or object normally, but never, ever delete it. If you delete it, the compiler will probably emit its usual code to free memory, which will conflict with the Boehm collector. The Boehm collector won't even try to call the destructors on data allocated this way.
For classes with destructors, the Boehm collector provides class gc. It overrides operator new and operator delete so that you may allocate and delete instances. The Boehm collector will recycle the memory automatically, but if you want the destructor to be called, you must delete the object yourself. You may create instances on the stack; their destructors will be called because the Boehm collector won't be involved at all.
If you need a new class with destructors that the Boehm collector calls automatically, you may subclass the Boehm collector's class gc_cleanup. It's like class gc except that it arranges for the Boehm collector to call the destructor immediately before recycling an instance's memory. Remember that you have no guarantee that all instances will be recycled.
Listing 3 demonstrates all three techniques. Notice that I don't delete the POD; that would be an error. I delete the ManualDelete objects explicitly, which I must do if I want their destructors called. I delete one of the AutoDelete instances explicitly to show that it can be done, but I rely on the Boehm collector to delete the rest. Also notice that I create ManualDeletes and AutoDeletes on the stack to show that it can be done. In the program's output (Listing 4), notice that the destructors for all the ManualDelete instances were called but that some AutoDelete destructors were not. That's an example of how you cannot predict when or whether a garbage collector will recycle any particular object.
There's one more type of class you might need to use with the Boehm collector: classes whose destructors must be called but which are not subclasses of gc or gc_cleanup. In other words, it's most classes you're likely to encounter. If you allocate, say, an std::list with new(UseGC), you'll need to delete that list to call its destructor, but if you delete it, the C++ compiler will emit non-Boehm deallocation code, which will cause an error.
So what to do? Simple: create a class template whose instance classes are subclasses of the old class and of Boehm's gc_cleanup. Listing 5 shows class template Boehmable, which makes a new, garbage-collected class from an old class and gc_cleanup. You can rely on the Boehm collector to call most of the destructors; I've included some counting code to demonstrate that. (The counting code isn't needed in production.) When you must ensure that a destructor is called, you can delete an object yourself, but be sure that in the lexical scope where you do so, the compiler knows that the object you are deleting inherits from gc_cleanup. If not, the compiler will emit an ordinary delete instead of gc_cleanup's overridden operator delete.
STL Collections
Collections from the STL work fine with the Boehm collector because they manage their memory internally. (That's encapsulation in action.) In addition, you can create an allocator that uses Boehm's GC_MALLOC, and you can give that allocator to your STL collections so that all the memory they allocate will be subject to garbage collection. This isn't necessary, though, because the semantics of STL collections allow them to determine precisely when to delete their privately allocated memory, and they are already implemented with that in mind. In other words, where STL collections meet the Boehm collector, just use the STL collections normally.If you write your own classes that are similarly able to determine when their memory isn't needed, it's best if you allocate that memory through the Boehm collector because the Boehm collector works best when it controls most (or all) dynamically allocated memory. The documentation warns that the Boehm collector might not scan malloced memory, so it could recycle a memory region if the only reference to it were in a malloced block of memory, but I haven't seen this situation arise. So in those cases where you can easily and definitely determine when a chunk of memory is no longer needed, free it explicitly by calling GC_FREE (or the xfree I suggested for plain C).
C++ Heuristics
I've described a lot of details about using the Boehm collector with C++. To summarize them as rules of thumb, they are:1. Adopt the mental habit of keeping work out of destructors. C++ programmers must make this change for maximum benefit from garbage collection, whether it's the Boehm collector or some future version of C++ that compiles to a virtual machine with built-in garbage collection.
2. Use new (UseGC) ... to allocate POD. Never delete it!
3. Make gc or gc_cleanup a virtual base class of your new classes.
4. Use class template Boehmable with old classes.
5. If the timing of an object's destructor is critical, it means the object must be on the stack. (fstreams and lock objects are examples.)
Extra Boehm Collector Details
The basic interface I've described is all you need to use the Boehm collector most of the time, but the Boehm collector provides other options, which are documented in <gc.h>. The most useful of these is probably finalizer functions. There are also functions to allocate uncollectable memory and atomic memory, but these are optimizations and I haven't needed any of them in practice. I suspect they should be invoked if and only if your profiler tells you they are needed.
Conclusion
Programmers from languages that have had garbage collection for a long time can attest that garbage collection improves programmer productivity. Now, thanks to the Boehm collector, it's easy for C and C++ programmers to use these benefits, too.
Note
[1] C library implementers could treat malloc and free as a standard interface to memory management. Their default behaviors could be the traditional malloc and free, but you could specify alternative functions at run time, such as GC_MALLOC and GC_FREE. That would allow you to choose your own memory-management system, possibly for debugging or because you have one that's specially optimized for your application domain. Old code would still work fine.
About the Author
Gene Michael Stover ([email protected]) is an independent consultant. His current primary interests include online publishing and source-code portability.
