A garbage collector for C and C++

These pages are archival copies from the reality.sgi.com server as of 2001-09-10

[ You may find updates of this page at http://www.hpl.hp.com/personal/Hans_Boehm/gc. This is a significantly revised version of the page at ftp://parcftp.xerox.com/pub/gc/gc.html.]

The Boehm-Demers-Weiser conservative garbage collector can be used as a garbage collecting replacement for C malloc or C++ new. It is also used by a number of programming language implementations that use C as intermediate code. For a more detailed description of the interface, see here.

Alternatively, it may be used as a leak detector for C or C++ programs, though that is not its primary goal.

Typically several versions will be available. Usually you should first try to use gc_source/gc.tar.gz, which is normally an older, more stable version.

If that fails, try the latest explicitly numbered version in http://reality.sgi.com/boehm/gc_source/ (2001-09-10 depreciated). Later versions may contain additional features, platform support, or bug fixes, but are likely to be less well tested. Note that versions containing the letters alpha are even less well tested than others, especially on non-SGI platforms.

The arguments for and against conservative garbage collection in C and C++ are briefly discussed in issues.html.

The garbage collector code is copyrighted by Hans-J. Boehm, Alan J. Demers, Xerox Corporation and Silicon Graphics. It may be used and copied without payment of a fee under minimal restrictions. See the README file in the distribution for more details. IT IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.

Empirically, this collector works with most unmodified C programs, simply by replacing malloc with GC_malloc calls, replacing realloc with GC_realloc calls, and removing free calls. Exceptions are discussed in issues.html.

Platforms

The collector is not completely portable, but the distribution includes ports to most standard PC and UNIX platforms. Win32, win32s, OS/2, and UNIX environments are supported on Intel-based PCs, as are all common UNIX workstations, MacOS, and AmigaDOS. Some ports are more polished than others.

Irix pthreads, Linux threads, Solaris threads (old style and pthreads) and PPCR threads are supported in the most recent versions, though this version of the collector itself is only active in one thread at a time. Win32 thread support appears to be getting more solid in the most recent versions.

Ian Piumarta made available a version that supports DEC and MIT pthreads.

Kenjiro Taura, Toshio Endo, and Akinori Yonezawa have made available a concurrent collector based on this one. Their collector takes advantage of multiple processors during a collection.

For MacOS use, Patrick Beard's latest port is available from http://www.vmeng.com/beard/gc/. (I'm not in a position to test under MacOS. Although I try to incorporate Patrick's changes, it is impossible for me to update the project file.)

Precompiled versions of the collector for NetBSD are available here.

Some Collector Details

The collector uses a mark-sweep algorithm. It provides incremental and generational collection under operating systems which provide the right kind of virtual memory support. (Currently this includes SunOS[45], IRIX, OSF/1, Linux, Windows NT, and Windows 95, with varying restrictions.) It allows finalization code to be invoked when an object is collected. It can take advantage of type information to locate pointers if such information is provided, but it is usually used without such information. See the README and gc.h files in the distribution for more details.

For an overview of the implementation, see here.

The garbage collector distribution includes a C string (cord) package that provides for fast concatenation and substring operations on long strings. A simple curses- and win32-based editor that represents the entire file as a cord is included as a sample application.

Performance of the nonincremental collector is typically competitive with malloc/free implementations. Both space and time overhead are likely to be only slightly higher for programs written for malloc/free (see Detlefs, Dosser and Zorn's Memory Allocation Costs in Large C and C++ Programs.) We expect that in many cases the additional overhead will be more than compensated for by decreased copying etc. if programs are written and tuned for garbage collection.

Further Reading:

The following papers describe the collector algorithms. The first two are not available electronically due to copyright considerations. The others are subject to ACM copyright.

Boehm, H., "Dynamic Memory Allocation and Garbage Collection", Computers in Physics 9, 3, May/June 1995, pp. 297-303. This is directed at an otherwise sophisticated audience unfamiliar with memory allocation issues. The algorithmic details differ from those in the implementation. There is a related letter to the editor and a minor correction in the next issue.

Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative Environment", Software Practice & Experience, September 1988, pp. 807-820.

Boehm, H., A. Demers, and S. Shenker, "Mostly Parallel Garbage Collection", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.

Boehm, H., "Space Efficient Conservative Garbage Collection", Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation, SIGPLAN Notices 28, 6 (June 1993), pp. 197-206.

The following papers discusses language and compiler restrictions necessary to guaranteed safety of conservative garbage collection. We thank John Levine and JCLT for allowing us to make the second paper available electronically, and providing PostScript for the final version.

Boehm, H., ``Simple Garbage-Collector-Safety'', Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation.

Boehm, H., and D. Chase, ``A Proposal for Garbage-Collector-Safe C Compilation'', Journal of C Language Translation 4, 2 (Decemeber 1992), pp. 126-141.

Related information:

The Detlefs, Dosser and Zorn's Memory Allocation Costs in Large C and C++ Programs. This is a performance comparison of the Boehm-Demers-Weiser collector to malloc/free, using programs written for malloc/free.

Joel Bartlett's mostly copying conservative garbage collector for C++.

John Ellis and David Detlef's Safe Efficient Garbage Collection for C++ proposal.

Paul Wilson's garbage collection ftp archive and GC survey.

Harlequin's Memory Management Reference.

David Chase's GC FAQ.

Richard Jones' GC page.

Henry Baker's paper collection.

Slides for Hans Boehm's Allocation and GC Myths talk.

Current users:

Known current users of some variant of this collector include:

Some versions of the Xerox DocuPrint printer software.

The Berkeley Sather implementation.

The NAGWare f90 Fortran 90 compiler.

Elwood Corporation's Eclipse Common Lisp system, C library, and translator.

The Bigloo Scheme and Camloo ML compilers written by Manuel Serrano and others.

Brent Benson's libscheme.

The University of Washington Cecil Implementation.

The Agora96 interpreter at the Free University Of Brussels.

The Toba Java Virtual Machine to C translator.

The Harissa Java Virtual Machine to C translator.

Nik Shaylor's JCC Java to C translator.

Yukio Andoh's j2c Java Virtual Machine to C translator.

Portable Object Compiler precompiler for Objective C.

The OOC Oberon compiler.

The Gwydion Dylan compiler.

Commercially supported garbage collectors for C and C++:

The following organization sells commercially supported garbage collectors for C and C++:

- Geodesic Systems ((800) 360-8388 or sales@geodesic.com).

Geodesic Systems is unrelated to Xerox Corporation and Silicon Graphics.
Hans-J. Boehm
(boehm@acm.org)