2
<html><head><title>A garbage collector for C and C++</title></head>
4
<table bgcolor="#f0f0ff" cellpadding="10%">
6
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html">Interface Overview</a></td>
7
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/04tutorial.pdf">Tutorial Slides</a></td>
8
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/faq.html">FAQ</a></td>
9
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/simple_example.html">Example</a></td>
10
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source">Download</a></td>
11
<td><a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/license.txt">License</a></td>
14
<h1>A garbage collector for C and C++</h1>
16
<li><a href="#platforms">Platforms</a>
17
</li><li><a href="#multiprocessors">Scalable multiprocessor versions</a>
18
</li><li><a href="#details">Some collector details</a>
19
</li><li><a href="#further">Further reading</a>
20
</li><li><a href="#users">Current users</a>
21
</li><li><a href="#collector">Local Links for this collector</a>
22
</li><li><a href="#background">Local Background Links</a>
23
</li><li><a href="#contacts">Contacts and Mailing List</a>
25
[ This is an updated version of the page formerly at
26
<tt>http://reality.sgi.com/boehm/gc.html</tt>
28
<a href="ftp://parcftp.xerox.com/pub/gc/gc.html">
29
<tt>ftp://parcftp.xerox.com/pub/gc/gc.html</tt></a>.]
31
The <a href="http://www.hpl.hp.com/personal/Hans_Boehm">Boehm</a>-<a href="http://www.cs.cornell.edu/annual_report/00-01/bios.htm#demers">Demers</a>-<a href="http://www-sul.stanford.edu/weiser/">Weiser</a>
32
conservative garbage collector can
33
be used as a garbage collecting
34
replacement for C <tt>malloc</tt> or C++ <tt>new</tt>.
35
It allows you to allocate memory basically as you normally would,
36
without explicitly deallocating memory that is no longer useful.
37
The collector automatically recycles memory when it determines
38
that it can no longer be otherwise accessed.
39
A simple example of such a use is given
40
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/simple_example.html">here</a>.
42
The collector is also used by a number of programming language
43
implementations that either use C as intermediate code, want
44
to facilitate easier interoperation with C libraries, or
45
just prefer the simple collector interface.
46
For a more detailed description of the interface, see
47
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html">here</a>.
49
Alternatively, the garbage collector may be used as
50
a <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/leak.html">leak detector</a>
51
for C or C++ programs, though that is not its primary goal.
53
Typically several versions will be available.
54
Usually you should first try to use
55
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/gc.tar.gz"><tt>gc_source/gc.tar.gz</tt></a>,
56
which is normally an older, more stable version.
58
If that fails, try the latest explicitly numbered version
59
in <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/">
60
<tt>gc_source/</tt></a>.
61
Later versions may contain additional features, platform support,
62
or bug fixes, but are likely to be less well tested.
63
Note that versions containing the letters <tt>alpha</tt> are even less
64
well tested than others, especially on non-HP platforms.
66
A slightly older version of the garbage collector is now also
67
included as part of the
68
<a href="http://gcc.gnu.org/">GNU compiler</a>
69
distribution. The source
70
code for that version is available for browsing
71
<a href="http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/boehm-gc/">here</a>.
73
The arguments for and against conservative garbage collection
74
in C and C++ are briefly
76
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html">issues.html</a>. The beginnings of
77
a frequently-asked-questions list are <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/faq.html">here</a>.
79
The garbage collector code is copyrighted by
80
<a href="http://www.hpl.hp.com/personal/Hans_Boehm">Hans-J. Boehm</a>,
82
<a href="http://www.xerox.com/">Xerox Corporation</a>,
83
<a href="http://www.sgi.com/">Silicon Graphics</a>,
85
<a href="http://www.hp.com/">Hewlett-Packard Company</a>.
86
It may be used and copied without payment of a fee under minimal restrictions.
87
See the README file in the distribution or the
88
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/license.txt">license</a> for more details.
89
<b>IT IS PROVIDED AS IS,
90
WITH ABSOLUTELY NO WARRANTY EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK</b>.
92
Empirically, this collector works with most unmodified C programs,
94
<tt>malloc</tt> with <tt>GC_malloc</tt> calls,
95
replacing <tt>realloc</tt> with <tt>GC_realloc</tt> calls, and removing
96
free calls. Exceptions are discussed
97
in <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html">issues.html</a>.
98
</p><h2><a name="platforms">Platforms</a></h2>
99
The collector is not completely portable, but the distribution
100
includes ports to most standard PC and UNIX/Linux platforms.
101
The collector should work on Linux, *BSD, recent Windows versions,
102
MacOS X, HP/UX, Solaris,
103
Tru64, Irix and a few other operating systems.
104
Some ports are more polished than others.
106
Irix pthreads, Linux threads, Win32 threads, Solaris threads
107
(old style and pthreads),
108
HP/UX 11 pthreads, Tru64 pthreads, and MacOS X threads are supported
110
</p><h3>Separately distributed ports</h3>
111
For MacOS 9/Classic use, Patrick Beard's latest port is available from
112
<a href="http://homepage.mac.com/pcbeard/gc/">
113
<tt>http://homepage.mac.com/pcbeard/gc/</tt></a>.
114
(Unfortunately, that's now quite dated.
115
I'm not in a position to test under MacOS. Although I try to
116
incorporate changes, it is impossible for
117
me to update the project file.)
119
Precompiled versions of the collector for NetBSD are available
120
<a href="ftp://ftp.netbsd.org/pub/NetBSD/packages/pkgsrc/devel/boehm-gc/README.html">here</a>
122
<a href="http://www.netbsd.org/packages/devel/boehm-gc/README.html">here</a>.
124
<a href="http://www.debian.org/">Debian Linux</a> includes prepackaged
125
versions of the collector.
126
</p><h2><a name="multiprocessors">Scalable multiprocessor versions</a></h2>
127
Kenjiro Taura, Toshio Endo, and Akinori Yonezawa have made available
128
a <a href="http://www.yl.is.s.u-tokyo.ac.jp/gc/">parallel collector</a>
129
based on this one. Their collector takes advantage of multiple processors
130
during a collection. Starting with collector version 6.0alpha1
131
we also do this, though with more modest processor scalability goals.
132
Our approach is discussed briefly in
133
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/scale.html"><tt>scale.html</tt></a>.
134
<h2><a name="details">Some Collector Details</a></h2>
135
The collector uses a <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html">mark-sweep</a> algorithm.
136
It provides incremental and generational
137
collection under operating systems which provide the right kind of
138
virtual memory support. (Currently this includes SunOS[45], IRIX,
139
OSF/1, Linux, and Windows, with varying restrictions.)
140
It allows <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/finalization.html"><i>finalization</i></a> code
141
to be invoked when an object is collected.
142
It can take advantage of type information to locate pointers if such
143
information is provided, but it is usually used without such information.
145
<tt>gc.h</tt> files in the distribution for more details.
147
For an overview of the implementation, see <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html">here</a>.
149
The garbage collector distribution includes a C string
150
(<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/cordh.txt"><i>cord</i></a>) package that provides
151
for fast concatenation and substring operations on long strings.
152
A simple curses- and win32-based editor that represents the entire file
153
as a cord is included as a
156
Performance of the nonincremental collector is typically competitive
157
with malloc/free implementations. Both space and time overhead are
158
likely to be only slightly higher
159
for programs written for malloc/free
160
(see Detlefs, Dosser and Zorn's
161
<a href="ftp://ftp.cs.colorado.edu/pub/techreports/zorn/CU-CS-665-93.ps.Z">Memory Allocation Costs in Large C and C++ Programs</a>.)
162
For programs allocating primarily very small objects, the collector
163
may be faster; for programs allocating primarily large objects it will
164
be slower. If the collector is used in a multithreaded environment
165
and configured for thread-local allocation, it may in some cases
166
significantly outperform malloc/free allocation in time.
168
We also expect that in many cases any additional overhead
169
will be more than compensated for by decreased copying etc.
170
if programs are written
171
and tuned for garbage collection.
172
</p><h1><a name="further">Further Reading:</a></h1>
173
<b>The beginnings of a frequently asked questions list for this
174
collector are <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/faq.html">here</a></b>.
176
<b>The following provide information on garbage collection in general</b>:
178
Paul Wilson's <a href="ftp://ftp.cs.utexas.edu/pub/garbage">garbage collection ftp archive</a> and <a href="ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps">GC survey</a>.
180
The Ravenbrook <a href="http://www.memorymanagement.org/">
181
Memory Management Reference</a>.
184
<a href="http://www.iecc.com/gclist/GC-faq.html">GC FAQ</a>.
187
<a href="http://www.ukc.ac.uk/computer_science/Html/Jones/gc.html">
189
<a href="http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html">
192
<b>The following papers describe the collector algorithms we use
193
and the underlying design decisions at
196
(Some of the lower level details can be found
197
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html">here</a>.)
199
The first one is not available
200
electronically due to copyright considerations. Most of the others are
201
subject to ACM copyright.
203
Boehm, H., "Dynamic Memory Allocation and Garbage Collection", <i>Computers in Physics
204
9</i>, 3, May/June 1995, pp. 297-303. This is directed at an otherwise sophisticated
205
audience unfamiliar with memory allocation issues. The algorithmic details differ
206
from those in the implementation. There is a related letter to the editor and a minor
207
correction in the next issue.
209
Boehm, H., and <a href="http://www.ubiq.com/hypertext/weiser/weiser.html">M. Weiser</a>,
210
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper">"Garbage Collection in an Uncooperative Environment"</a>,
211
<i>Software Practice & Experience</i>, September 1988, pp. 807-820.
213
Boehm, H., A. Demers, and S. Shenker, <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi91.ps.Z">"Mostly Parallel Garbage Collection"</a>, Proceedings
214
of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation,
215
<i>SIGPLAN Notices 26</i>, 6 (June 1991), pp. 157-164.
217
Boehm, H., <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi93.ps.Z">"Space Efficient Conservative Garbage Collection"</a>, Proceedings of the ACM
218
SIGPLAN '93 Conference on Programming Language Design and Implementation, <i>SIGPLAN
219
Notices 28</i>, 6 (June 1993), pp. 197-206.
221
Boehm, H., "Reducing Garbage Collector Cache Misses",
222
<i> Proceedings of the 2000 International Symposium on Memory Management </i>.
223
<a href="http://portal.acm.org/citation.cfm?doid=362422.362438">
224
Official version.</a>
225
<a href="http://www.hpl.hp.com/techreports/2000/HPL-2000-99.html">
226
Technical report version.</a> Describes the prefetch strategy
227
incorporated into the collector for some platforms. Explains why
228
the sweep phase of a "mark-sweep" collector should not really be
231
M. Serrano, H. Boehm,
232
"Understanding Memory Allocation of Scheme Programs",
233
<i>Proceedings of the Fifth ACM SIGPLAN International Conference on
234
Functional Programming</i>, 2000, Montreal, Canada, pp. 245-256.
235
<a href="http://www.acm.org/pubs/citations/proceedings/fp/351240/p245-serrano/">
236
Official version.</a>
237
<a href="http://www.hpl.hp.com/techreports/2000/HPL-2000-62.html">
238
Earlier Technical Report version.</a> Includes some discussion of the
239
collector debugging facilities for identifying causes of memory retention.
242
"Fast Multiprocessor Memory Allocation and Garbage Collection",
243
<a href="http://www.hpl.hp.com/techreports/2000/HPL-2000-165.html">
244
HP Labs Technical Report HPL 2000-165</a>. Discusses the parallel
245
collection algorithms, and presents some performance results.
247
Boehm, H., "Bounding Space Usage of Conservative Garbage Collectors",
248
<i>Proceeedings of the 2002 ACM SIGPLAN-SIGACT Symposium on Principles of
249
Programming Languages</i>, Jan. 2002, pp. 93-100.
250
<a href="http://portal.acm.org/citation.cfm?doid=503272.503282">
251
Official version.</a>
252
<a href="http://www.hpl.hp.com/techreports/2001/HPL-2001-251.html">
253
Technical report version.</a>
254
Includes a discussion of a collector facility to much more reliably test for
255
the potential of unbounded heap growth.
257
<b>The following papers discuss language and compiler restrictions necessary to guaranteed
258
safety of conservative garbage collection.</b>
260
We thank John Levine and JCLT for allowing
261
us to make the second paper available electronically, and providing PostScript for the final
264
Boehm, H., <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi96.ps.gz">``Simple
265
Garbage-Collector-Safety''</a>, Proceedings
266
of the ACM SIGPLAN '96 Conference on Programming Language Design
269
Boehm, H., and D. Chase, <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/boecha.ps.gz">
270
``A Proposal for Garbage-Collector-Safe C Compilation''</a>,
271
<i>Journal of C Language Translation 4</i>, 2 (Decemeber 1992), pp. 126-141.
273
<b>Other related information: </b>
275
The Detlefs, Dosser and Zorn's <a href="ftp://ftp.cs.colorado.edu/pub/techreports/zorn/CU-CS-665-93.ps.Z">Memory Allocation Costs in Large C and C++ Programs</a>.
276
This is a performance comparison of the Boehm-Demers-Weiser collector to malloc/free,
277
using programs written for malloc/free.
279
Joel Bartlett's <a href="ftp://ftp.digital.com/pub/DEC/CCgc">mostly copying conservative garbage collector for C++</a>.
281
John Ellis and David Detlef's <a href="ftp://parcftp.xerox.com/pub/ellis/gc/gc.ps">Safe Efficient Garbage Collection for C++</a> proposal.
283
Henry Baker's <a href="http://home.pipeline.com/%7Ehbaker1/">paper collection</a>.
285
Slides for Hans Boehm's <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/myths.ps">Allocation and GC Myths</a> talk.
286
</p><h1><a name="users">Current users:</a></h1>
287
Known current users of some variant of this collector include:
289
The runtime system for <a href="http://gcc.gnu.org/java">GCJ</a>,
290
the static GNU java compiler.
292
<a href="http://w3m.sourceforge.net/">W3m</a>, a text-based web browser.
294
Some versions of the Xerox DocuPrint printer software.
296
The <a href="http://www.mozilla.org/">Mozilla</a> project, as leak
299
The <a href="http://www.go-mono.com/">Mono</a> project,
300
an open source implementation of the .NET development framework.
302
The <a href="http://www.gnu.org/projects/dotgnu/">DotGNU Portable.NET
303
project</a>, another open source .NET implementation.
305
The <a href="http://irssi.org/">Irssi IRC client</a>.
307
<a href="http://titanium.cs.berkeley.edu/">The Berkeley Titanium project</a>.
309
<a href="http://www.nag.co.uk/nagware_fortran_compilers.asp">The NAGWare f90 Fortran 90 compiler</a>.
311
Elwood Corporation's <a href="http://www.elwood.com/eclipse-info/index.htm">
312
Eclipse</a> Common Lisp system, C library, and translator.
314
The <a href="http://www-sop.inria.fr/mimosa/fp/Bigloo/">Bigloo
316
and <a href="http://kaolin.unice.fr/%7Eserrano/camloo.html">Camloo ML
318
written by Manuel Serrano and others.
320
Brent Benson's <a href="http://ftp.cs.indiana.edu/pub/scheme-repository/imp/">libscheme</a>.
322
The <a href="http://www.cs.rice.edu/CS/PLT/packages/mzscheme/index.html">MzScheme</a> scheme implementation.
324
The <a href="http://www.cs.washington.edu/research/projects/cecil/www/cecil-home.html">University of Washington Cecil Implementation</a>.
326
<a href="http://www.icsi.berkeley.edu/Sather/">The Berkeley Sather implementation</a>.
328
<a href="http://www.cs.berkeley.edu/%7Eharmonia/">The Berkeley Harmonia Project</a>.
330
The <a href="http://www.cs.arizona.edu/sumatra/toba/">Toba</a> Java Virtual
331
Machine to C translator.
333
The <a href="http://www.gwydiondylan.org/">Gwydion Dylan compiler</a>.
335
The <a href="http://gcc.gnu.org/onlinedocs/gcc/Objective-C.html">
336
GNU Objective C runtime</a>.
338
<a href="http://www.math.uiuc.edu/Macaulay2">Macaulay 2</a>, a system to support
339
research in algebraic geometry and commutative algebra.
341
The <a href="http://www.vestasys.org/">Vesta</a> configuration management
344
<a href="http://www.visual-prolog.com/vip6">Visual Prolog 6</a>.
346
<a href="http://asymptote.sf.net/">Asymptote LaTeX-compatible
347
vector graphics language.</a>
349
</p><h1><a name="collector">More collector information at this site</a></h1>
350
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/simple_example.html">A simple illustration of how to build and
351
use the collector.</a>.
353
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html">Description of alternate interfaces to the
354
garbage collector.</a>
356
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/04tutorial.pdf">Slides from an ISMM 2004 tutorial about the GC.</a>
358
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/faq.html">A FAQ (frequently asked questions) list.</a>
360
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/leak.html">How to use the garbage collector as a leak detector.</a>
362
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/debugging.html">Some hints on debugging garbage collected
365
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html">An overview of the implementation of the
366
garbage collector.</a>
368
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/tree.html">The data structure used for fast pointer lookups.</a>
370
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/scale.html">Scalability of the collector to multiprocessors.</a>
372
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source">Directory containing garbage collector source.</a>
374
</p><h1><a name="background">More background information at this site</a></h1>
375
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/bounds.html">An attempt to establish a bound on space usage of
376
conservative garbage collectors.</a>
378
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html">Mark-sweep versus copying garbage collectors
379
and their complexity.</a>
381
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/conservative.html">Pros and cons of conservative garbage collectors,
382
in comparison to other collectors.
385
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html">Issues related to garbage collection vs.
386
manual memory management in C/C++.</a>
388
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/example.html">An example of a case in which garbage collection
389
results in a much faster implementation as a result of reduced
392
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/nonmoving">Slide set discussing performance of nonmoving
393
garbage collectors.</a>
395
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/popl03/web">
396
Slide set discussing <i>Destructors, Finalizers, and Synchronization</i>
399
<a href="http://portal.acm.org/citation.cfm?doid=604131.604153">
400
Paper corresponding to above slide set.</a>
401
(<a href="http://www.hpl.hp.com/techreports/2002/HPL-2002-335.html">
402
Technical Report version</a>.)
404
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_bench.html">A Java/Scheme/C/C++ garbage collection benchmark.</a>
406
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/myths.ps">Slides for talk on memory allocation myths.</a>
408
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/gctalk.ps">Slides for OOPSLA 98 garbage collection talk.</a>
410
<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers">Related papers.</a>
411
</p><h1><a name="contacts">Contacts and Mailing List</a><a></a></h1>
412
<a>We have recently set up two mailing list for collector announcements
415
<li><a href="mailto:gc-announce@linux.hpl.hp.com">gc-announce@linux.hpl.hp.com</a>
416
is used for announcements of new versions. Postings are restricted.
417
We expect this to always remain a very low volume list.
418
</li><li><a href="mailto:gc@linux.hpl.hp.com">gc@linux.hpl.hp.com</a> is used for
419
discussions, bug reports, and the like. Subscribers may post.
420
On-topic posts by nonsubscribers will usually also be accepted, but
421
it may take some time to review them.
423
To subscribe to these lists, send a mail message containing the
425
<a href="mailto:gc-announce-request@linux.hpl.hp.com?subject=subscribe">gc-announce-request@linux.hpl.hp.com</a>
427
<a href="mailto:gc-request@linux.hpl.hp.com?subject=subscribe">gc-request@linux.hpl.hp.com</a>.
428
(Please ignore the instructions about web-based subscription.
429
The listed web site is behind the HP firewall.)
431
The archives for these lists appear
432
<a href="http://www.hpl.hp.com/hosted/linux/mail-archives">here</a>.
433
The gc list archive may also be read at
434
<a href="http://dir.gmane.org/gmane.comp.programming.garbage-collection.boehmgc">gmane.org</a>.
436
Some prior discussion of the collector has taken place on the gcc
437
java mailing list, whose archives appear
438
<a href="http://gcc.gnu.org/ml/java/">here</a>, and also on
439
<a href="http://lists.tunes.org/mailman/listinfo/gclist">gclist@iecc.com</a>.
441
Comments and bug reports may also be sent to
442
(<a href="mailto:Hans_Boehm@hp.com">Hans.Boehm@hp.com</a>) or
443
(<a href="mailto:boehm@acm.org">boehm@acm.org</a>), but the gc
444
mailing list is usually preferred.
added
removed
doc/overview.html
