A garbage collector for C and C++

[ This is a November 1996 copy of http://reality.sgi.com/employees/boehm_mti/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. 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/employees/boehm_mti/gc_source/. 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, for the latest version, 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.

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. Solaris threads and PPCR threads are supported, though this version of the collector itself is only active in one thread at a time. For MacOS use, I recommend retrieving the latest available port from Patrick Beard's ftp directory. (I'm not in a position to test under MacOS, and it is impossible for me to update the project file.)

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.

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 nonicnremental 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 '91 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.

David Chase's GC FAQ.

Richard Jones' GC page.

Henry Baker's paper collection.

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.

The Bigloo and Camloo Scheme and 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.

Commercially supported garbage collectors for C and C++:

The following organizations sell commercially supported garbage collectors for C and C++:

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

- Kevin Warne ((800) 707-7171 or kevinw@direct.ca).

Both are unrelated to Xerox Corporation and Silicon Graphics.

Hans-J. Boehm
(boehm@mti.sgi.com)