| 1 |
[Interface Overview](gcinterface.md) | [Tutorial Slides](http://www.hboehm.info/gc/04tutorial.pdf) | [FAQ](http://www.hboehm.info/gc/faq.html) | [Example](simple_example.md) | [Download](https://github.com/ivmai/bdwgc/wiki/Download) | [License](http://www.hboehm.info/gc/license.txt) |
| 2 |
---|---|---|---|---|--- |
| 3 |
|
| 4 |
# A garbage collector for C and C++ |
| 5 |
|
| 6 |
* Platforms |
| 7 |
* Scalable multiprocessor versions |
| 8 |
* Some collector details |
| 9 |
* Further reading |
| 10 |
* Current users |
| 11 |
* Local Links for this collector |
| 12 |
* Local Background Links |
| 13 |
* Contacts and Mailing List |
| 14 |
|
| 15 |
[ This is an updated version of the page formerly at |
| 16 |
`www.hpl.hp.com/personal/Hans_Boehm/gc/`, before that at |
| 17 |
`http://reality.sgi.com/boehm/gc.html` and before that at |
| 18 |
`ftp://ftp.parc.xerox.com/pub/gc/gc.html`. ] |
| 19 |
|
| 20 |
The |
| 21 |
[Boehm](http://www.hboehm.info)-[Demers](http://www.cs.cornell.edu/annual_report/00-01/bios.htm#demers)-[Weiser](http://www.ubiq.com/hypertext/weiser/weiser.html) |
| 22 |
conservative Garbage Collector (**BDWGC**) can be used as a garbage collecting |
| 23 |
replacement for C `malloc` or C++ `new`. It allows you to allocate memory |
| 24 |
basically as you normally would, without explicitly deallocating memory that |
| 25 |
is no longer useful. The collector automatically recycles memory when |
| 26 |
it determines that it can no longer be otherwise accessed. A simple example |
| 27 |
of such a use is given [here](simple_example.md). |
| 28 |
|
| 29 |
The collector is also used by a number of programming language implementations |
| 30 |
that either use C as intermediate code, want to facilitate easier |
| 31 |
interoperation with C libraries, or just prefer the simple collector |
| 32 |
interface. For a more detailed description of the interface, see |
| 33 |
[here](gcinterface.md). |
| 34 |
|
| 35 |
Alternatively, the garbage collector may be used as a [leak detector](leak.md) |
| 36 |
for C or C++ programs, though that is not its primary goal. |
| 37 |
|
| 38 |
Typically several versions are offered for |
| 39 |
[downloading](https://github.com/ivmai/bdwgc/wiki/Download): preview, stable, |
| 40 |
legacy. Usually you should use the one marked as the _latest stable_ release. |
| 41 |
Preview versions may contain additional features, platform support, but are |
| 42 |
likely to be less well tested. The list of changes for each version |
| 43 |
is specified on the [releases](https://github.com/ivmai/bdwgc/releases) page. |
| 44 |
|
| 45 |
The arguments for and against conservative garbage collection in C and C++ are |
| 46 |
briefly discussed [here](http://www.hboehm.info/gc/issues.html). The |
| 47 |
beginnings of a frequently-asked-questions list are |
| 48 |
[here](http://www.hboehm.info/gc/faq.html). |
| 49 |
|
| 50 |
The garbage collector code is copyrighted by |
| 51 |
[Hans-J. Boehm](http://www.hboehm.info), Alan J. Demers, |
| 52 |
[Xerox Corporation](http://www.xerox.com/), |
| 53 |
[Silicon Graphics](http://www.sgi.com/), and |
| 54 |
[Hewlett-Packard Company](http://www.hp.com/). It may be used and copied |
| 55 |
without payment of a fee under minimal restrictions. See the README.md file |
| 56 |
in the distribution or the [license](http://www.hboehm.info/gc/license.txt) |
| 57 |
for more details. **IT IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY |
| 58 |
EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK**. |
| 59 |
|
| 60 |
Empirically, this collector works with most unmodified C programs, simply |
| 61 |
by replacing `malloc` with `GC_malloc` calls, replacing `realloc` with |
| 62 |
`GC_realloc` calls, and removing free calls. Exceptions are discussed |
| 63 |
[here](http://www.hboehm.info/gc/issues.html). |
| 64 |
|
| 65 |
## Platforms |
| 66 |
|
| 67 |
The collector is not completely portable, but the distribution includes ports |
| 68 |
to most standard PC and UNIX/Linux platforms. The collector should work |
| 69 |
on Linux, *BSD, recent Windows versions, MacOS X, HP/UX, Solaris, Tru64, Irix |
| 70 |
and a few other operating systems. Some ports are more polished than others. |
| 71 |
|
| 72 |
Irix pthreads, Linux threads, Win32 threads, Solaris threads (pthreads only), |
| 73 |
HP/UX 11 pthreads, Tru64 pthreads, and MacOS X threads are supported in recent |
| 74 |
versions. |
| 75 |
|
| 76 |
### Separately distributed ports |
| 77 |
|
| 78 |
For MacOS 9/Classic use, Patrick Beard's latest port is available from |
| 79 |
`http://homepage.mac.com/pcbeard/gc/`. (Unfortunately, that's now quite dated. |
| 80 |
I'm not in a position to test under MacOS. Although I try to incorporate |
| 81 |
changes, it is impossible for me to update the project file.) |
| 82 |
|
| 83 |
Precompiled versions of the collector for NetBSD are available |
| 84 |
[here](ftp://ftp.netbsd.org/pub/pkgsrc/current/pkgsrc/devel/boehm-gc/README.html). |
| 85 |
|
| 86 |
|
| 87 |
[Debian Linux](http://www.debian.org/) includes prepackaged versions of the |
| 88 |
collector. |
| 89 |
|
| 90 |
## Scalable multiprocessor versions |
| 91 |
|
| 92 |
Kenjiro Taura, Toshio Endo, and Akinori Yonezawa have made available |
| 93 |
a [parallel collector](http://ieeexplore.ieee.org/abstract/document/1592629/) |
| 94 |
based on this one. Their collector takes advantage of multiple processors |
| 95 |
during a collection. Starting with GC v6.0alpha1 we also do this, though with |
| 96 |
more modest processor scalability goals. Our approach is discussed briefly |
| 97 |
in [this document](scale.md). |
| 98 |
|
| 99 |
## Some Collector Details |
| 100 |
|
| 101 |
The collector uses a [mark-sweep](http://www.hboehm.info/gc/complexity.html) |
| 102 |
algorithm. It provides incremental and generational collection under operating |
| 103 |
systems which provide the right kind of virtual memory support. (Currently |
| 104 |
this includes SunOS[45], IRIX, OSF/1, Linux, and Windows, with varying |
| 105 |
restrictions.) It allows [_finalization_](finalization.md) code to be invoked |
| 106 |
when an object is collected. It can take advantage of type information |
| 107 |
to locate pointers if such information is provided, but it is usually used |
| 108 |
without such information. See the README and `gc.h` files in the distribution |
| 109 |
for more details. |
| 110 |
|
| 111 |
For an overview of the implementation, see [here](gcdescr.md). |
| 112 |
|
| 113 |
The garbage collector distribution includes a C string (`cord.h`) package that |
| 114 |
provides for fast concatenation and substring operations on long strings. |
| 115 |
A simple curses- and win32-based editor that represents the entire file as |
| 116 |
a cord is included as a sample application. |
| 117 |
|
| 118 |
Performance of the non-incremental collector is typically competitive with |
| 119 |
`malloc`/`free` implementations. Both space and time overhead are likely to be |
| 120 |
only slightly higher for programs written for `malloc`/`free` (see Detlefs, |
| 121 |
Dosser and Zorn's |
| 122 |
[Memory Allocation Costs in Large C and C++ Programs](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3073&rep=rep1&type=ps)). |
| 123 |
For programs allocating primarily very small objects, the collector may be |
| 124 |
faster; for programs allocating primarily large objects it will be slower. |
| 125 |
If the collector is used in a multi-threaded environment and configured for |
| 126 |
thread-local allocation, it may in some cases significantly outperform |
| 127 |
`malloc`/`free` allocation in time. |
| 128 |
|
| 129 |
We also expect that in many cases any additional overhead will be more than |
| 130 |
compensated for by decreased copying etc. if programs are written and tuned |
| 131 |
for garbage collection. |
| 132 |
|
| 133 |
# Further Reading: |
| 134 |
|
| 135 |
**The beginnings of a frequently asked questions list for this collector are |
| 136 |
[here](http://www.hboehm.info/gc/faq.html)**. |
| 137 |
|
| 138 |
**The following provide information on garbage collection in general**: Paul |
| 139 |
Wilson's [garbage collection ftp archive](ftp://ftp.cs.utexas.edu/pub/garbage) |
| 140 |
and [GC survey](ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps). |
| 141 |
|
| 142 |
The Ravenbrook |
| 143 |
[Memory Management Reference](http://www.memorymanagement.org/). |
| 144 |
|
| 145 |
David Chase's [GC FAQ](http://www.iecc.com/gclist/GC-faq.html). |
| 146 |
|
| 147 |
Richard Jones' |
| 148 |
[Garbage Collection Page](https://www.cs.kent.ac.uk/people/staff/rej/gc.html) |
| 149 |
and his [book](http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html). |
| 150 |
|
| 151 |
**The following papers describe the collector algorithms we use and the |
| 152 |
underlying design decisions at a higher level.** |
| 153 |
|
| 154 |
(Some of the lower level details can be found [here](gcdescr.md).) |
| 155 |
|
| 156 |
The first one is not available electronically due to copyright considerations. |
| 157 |
Most of the others are subject to ACM copyright. |
| 158 |
|
| 159 |
Boehm, H., Dynamic Memory Allocation and Garbage Collection, |
| 160 |
_Computers in Physics 9_, 3, May/June 1995, pp. 297-303. This is directed |
| 161 |
at an otherwise sophisticated audience unfamiliar with memory allocation |
| 162 |
issues. The algorithmic details differ from those in the implementation. There |
| 163 |
is a related letter to the editor and a minor correction in the next issue. |
| 164 |
|
| 165 |
Boehm, H., and [M. Weiser](http://www.ubiq.com/hypertext/weiser/weiser.html), |
| 166 |
[Garbage Collection in an Uncooperative Environment](http://www.hboehm.info/spe_gc_paper/), |
| 167 |
_Software Practice & Experience_, September 1988, pp. 807-820. |
| 168 |
|
| 169 |
Boehm, H., A. Demers, and S. Shenker, |
| 170 |
[Mostly Parallel Garbage Collection](http://www.hboehm.info/gc/papers/pldi91.ps.Z), |
| 171 |
Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design |
| 172 |
and Implementation, _SIGPLAN Notices 26_, 6 (June 1991), pp. 157-164. |
| 173 |
|
| 174 |
Boehm, H., |
| 175 |
[Space Efficient Conservative Garbage Collection](http://www.hboehm.info/gc/papers/pldi93.ps.Z), |
| 176 |
Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design |
| 177 |
and Implementation, _SIGPLAN Notices 28_, 6 (June 1993), pp. 197-206. |
| 178 |
|
| 179 |
Boehm, H., Reducing Garbage Collector Cache Misses, |
| 180 |
_Proceedings of the 2000 International Symposium on Memory Management_. |
| 181 |
[Official version](http://portal.acm.org/citation.cfm?doid=362422.362438). |
| 182 |
[Technical report](http://www.hpl.hp.com/techreports/2000/HPL-2000-99.html) |
| 183 |
version. Describes the prefetch strategy incorporated into the collector for |
| 184 |
some platforms. Explains why the sweep phase of a _mark-sweep_ collector |
| 185 |
should not really be a distinct phase. |
| 186 |
|
| 187 |
M. Serrano, H. Boehm, Understanding Memory Allocation of Scheme Programs, |
| 188 |
_Proceedings of the Fifth ACM SIGPLAN International Conference on Functional |
| 189 |
Programming_, 2000, Montreal, Canada, pp. 245-256. |
| 190 |
[Official version](http://dl.acm.org/citation.cfm?id=351264). Earlier |
| 191 |
[Technical Report](http://www.hpl.hp.com/techreports/2000/HPL-2000-62.html) |
| 192 |
version. Includes some discussion of the collector debugging facilities for |
| 193 |
identifying causes of memory retention. |
| 194 |
|
| 195 |
Boehm, H., Fast Multiprocessor Memory Allocation and Garbage Collection, |
| 196 |
[HP Labs Technical Report HPL 2000-165](http://www.hpl.hp.com/techreports/2000/HPL-2000-165.html). |
| 197 |
Discusses the parallel collection algorithms, and presents some performance |
| 198 |
results. |
| 199 |
|
| 200 |
Boehm, H., Bounding Space Usage of Conservative Garbage Collectors, |
| 201 |
_Proceedings of the 2002 ACM SIGPLAN-SIGACT Symposium on Principles |
| 202 |
of Programming Languages_, Jan. 2002, pp. 93-100. |
| 203 |
[Official version](http://portal.acm.org/citation.cfm?doid=503272.503282). |
| 204 |
[Technical report](http://www.hpl.hp.com/techreports/2001/HPL-2001-251.html) |
| 205 |
version. Includes a discussion of a collector facility to much more reliably |
| 206 |
test for the potential of unbounded heap growth. |
| 207 |
|
| 208 |
**The following papers discuss language and compiler restrictions necessary |
| 209 |
to guaranteed safety of conservative garbage collection.** |
| 210 |
|
| 211 |
We thank John Levine and JCLT for allowing us to make the second paper |
| 212 |
available electronically, and providing PostScript for the final version. |
| 213 |
|
| 214 |
Boehm, H., |
| 215 |
[Simple Garbage-Collector-Safety](http://www.hboehm.info/gc/papers/pldi96.ps.gz), |
| 216 |
Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design |
| 217 |
and Implementation. |
| 218 |
|
| 219 |
Boehm, H., and D. Chase, |
| 220 |
[A Proposal for Garbage-Collector-Safe C Compilation](http://www.hboehm.info/gc/papers/boecha.ps.gz), |
| 221 |
_Journal of C Language Translation 4_, 2 (December 1992), pp. 126-141. |
| 222 |
|
| 223 |
**Other related information:** |
| 224 |
|
| 225 |
The Detlefs, Dosser and Zorn's |
| 226 |
[Memory Allocation Costs in Large C and C++ Programs](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3073&rep=rep1&type=ps). |
| 227 |
This is a performance comparison of the Boehm-Demers-Weiser collector |
| 228 |
to `malloc`/`free`, using programs written for `malloc`/`free`. |
| 229 |
|
| 230 |
Joel Bartlett's |
| 231 |
[mostly copying conservative garbage collector for C++](ftp://gatekeeper.dec.com/pub/compaq/WRL/research-reports/WRL-TN-12.ps). |
| 232 |
|
| 233 |
John Ellis and David Detlef's |
| 234 |
[Safe Efficient Garbage Collection for C++](http://dl.acm.org/citation.cfm?id=1267983) |
| 235 |
proposal. |
| 236 |
|
| 237 |
Henry Baker's [paper collection](http://home.pipeline.com/%7Ehbaker1/). |
| 238 |
|
| 239 |
Slides for Hans Boehm's |
| 240 |
[Allocation and GC Myths](http://www.hboehm.info/gc/myths.ps) talk. |
| 241 |
|
| 242 |
# Current users: |
| 243 |
|
| 244 |
Known current users of some variant of this collector include: |
| 245 |
|
| 246 |
The runtime system for [GCJ](https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcj/), |
| 247 |
the static GNU java compiler. |
| 248 |
|
| 249 |
[W3m](http://w3m.sourceforge.net/), a text-based web browser. |
| 250 |
|
| 251 |
Some versions of the Xerox DocuPrint printer software. |
| 252 |
|
| 253 |
The [Mozilla](http://www.mozilla.org/) project, as leak detector. |
| 254 |
|
| 255 |
The [Mono](http://www.mono-project.com) project, an open source implementation |
| 256 |
of the .NET development framework. |
| 257 |
|
| 258 |
The [DotGNU Portable.NET project](http://www.gnu.org/projects/dotgnu/), |
| 259 |
another open source .NET implementation. |
| 260 |
|
| 261 |
The [Irssi IRC client](http://irssi.org/). |
| 262 |
|
| 263 |
[The Berkeley Titanium project](http://titanium.cs.berkeley.edu/). |
| 264 |
|
| 265 |
[The NAGWare f90 Fortran 90 compiler](http://www.nag.co.uk/nagware/NP/NP_desc.asp). |
| 266 |
|
| 267 |
Elwood Corporation's Eclipse Common Lisp system, C library, and translator. |
| 268 |
|
| 269 |
The [Bigloo Scheme](http://www-sop.inria.fr/mimosa/fp/Bigloo/) and |
| 270 |
[Camloo ML compilers](https://github.com/samoht/camloo) written by Manuel |
| 271 |
Serrano and others. |
| 272 |
|
| 273 |
Brent Benson's |
| 274 |
[libscheme](http://www.cs.indiana.edu/scheme-repository/libscheme-vhll/final.html). |
| 275 |
|
| 276 |
The MzScheme scheme implementation. |
| 277 |
|
| 278 |
The |
| 279 |
[University of Washington Cecil Implementation](http://www.cs.washington.edu/research/projects/cecil/www/cecil-home.html). |
| 280 |
|
| 281 |
[The Berkeley Sather implementation](http://www1.icsi.berkeley.edu/~sather/). |
| 282 |
|
| 283 |
[The Berkeley Harmonia Project](http://www.cs.berkeley.edu/~harmonia/harmonia/index.html). |
| 284 |
|
| 285 |
The |
| 286 |
[Toba](http://www.cs.arizona.edu/projects/sumatra/toba/) Java Virtual Machine |
| 287 |
to C translator. |
| 288 |
|
| 289 |
The [Gwydion Dylan compiler](http://www.gwydiondylan.org/). |
| 290 |
|
| 291 |
The |
| 292 |
[GNU Objective C runtime](http://gcc.gnu.org/onlinedocs/gcc/Objective-C.html). |
| 293 |
|
| 294 |
[Macaulay 2](http://www.math.uiuc.edu/Macaulay2), a system to support research |
| 295 |
in algebraic geometry and commutative algebra. |
| 296 |
|
| 297 |
The [Vesta](http://www.vestasys.org/) configuration management system. |
| 298 |
|
| 299 |
[Visual Prolog 6](http://www.visual-prolog.com/). |
| 300 |
|
| 301 |
[Asymptote LaTeX-compatible vector graphics language](http://asymptote.sf.net/). |
| 302 |
|
| 303 |
# More information on the BDWGC primary site |
| 304 |
|
| 305 |
[A simple illustration of how to build and use the collector](simple_example.md). |
| 306 |
|
| 307 |
[Description of alternate interfaces to the garbage collector](gcinterface.md). |
| 308 |
|
| 309 |
[Slides from an ISMM 2004 tutorial about the GC](http://www.hboehm.info/gc/04tutorial.pdf). |
| 310 |
|
| 311 |
[A FAQ (frequently asked questions) list](http://www.hboehm.info/gc/faq.html). |
| 312 |
|
| 313 |
[How to use the garbage collector as a leak detector](leak.md). |
| 314 |
|
| 315 |
[Some hints on debugging garbage collected applications](debugging.md). |
| 316 |
|
| 317 |
[An overview of the implementation of the garbage collector](gcdescr.md). |
| 318 |
|
| 319 |
[The data structure used for fast pointer lookups](tree.md). |
| 320 |
|
| 321 |
[Scalability of the collector to multiprocessors](scale.md). |
| 322 |
|
| 323 |
[Directory](http://www.hboehm.info/gc/gc_source/) containing the distribution |
| 324 |
files of all garbage collector releases. It duplicates |
| 325 |
[Download](https://github.com/ivmai/bdwgc/wiki/Download) page on GitHub. |
| 326 |
|
| 327 |
# More background information |
| 328 |
|
| 329 |
[An attempt to establish a bound on space usage of conservative garbage collectors](http://www.hboehm.info/gc/bounds.html). |
| 330 |
|
| 331 |
[Mark-sweep versus copying garbage collectors and their complexity](http://www.hboehm.info/gc/complexity.html). |
| 332 |
|
| 333 |
[Pros and cons of conservative garbage collectors, in comparison to other collectors](http://www.hboehm.info/gc/conservative.html). |
| 334 |
|
| 335 |
[Issues related to garbage collection vs. manual memory management in C/C++](http://www.hboehm.info/gc/issues.html). |
| 336 |
|
| 337 |
[An example of a case in which garbage collection results in a much faster implementation as a result of reduced synchronization](http://www.hboehm.info/gc/example.html). |
| 338 |
|
| 339 |
[Slide set discussing performance of nonmoving garbage collectors](http://www.hboehm.info/gc/nonmoving/). |
| 340 |
|
| 341 |
[Slide set discussing _Destructors, Finalizers, and Synchronization_, POPL 2003](http://www.hboehm.info/popl03/web/). |
| 342 |
|
| 343 |
[Paper corresponding to above slide set](http://portal.acm.org/citation.cfm?doid=604131.604153) |
| 344 |
([Technical Report](http://www.hpl.hp.com/techreports/2002/HPL-2002-335.html) |
| 345 |
version). |
| 346 |
|
| 347 |
[A Java/Scheme/C/C++ garbage collection benchmark](http://www.hboehm.info/gc/gc_bench/). |
| 348 |
|
| 349 |
[Slides for talk on memory allocation myths](http://www.hboehm.info/gc/myths.ps). |
| 350 |
|
| 351 |
[Slides for OOPSLA 98 garbage collection talk](http://www.hboehm.info/gc/gctalk.ps). |
| 352 |
|
| 353 |
[Related papers](http://www.hboehm.info/gc/papers/). |
| 354 |
|
| 355 |
# Contacts and new release announcements |
| 356 |
|
| 357 |
GitHub and Stack Overflow are the major two places for communication. |
| 358 |
|
| 359 |
Technical questions (how to, how does it work, etc.) should be posted |
| 360 |
to [Stack Overflow](https://stackoverflow.com/questions/tagged/boehm-gc) with |
| 361 |
_boehm-gc_ tag. |
| 362 |
|
| 363 |
To contribute, please rebase your code to the latest |
| 364 |
[master](https://github.com/ivmai/bdwgc/tree/master/) and submit |
| 365 |
a [pull request](https://github.com/ivmai/bdwgc/pulls) to GitHub. |
| 366 |
|
| 367 |
To report a bug, or propose (request) a new feature, create |
| 368 |
a [GitHub issue](https://github.com/ivmai/bdwgc/issues). Please make sure |
| 369 |
it has not been reported yet by someone else. |
| 370 |
|
| 371 |
To receive notifications on every release, please subscribe to |
| 372 |
[Releases RSS feed](https://github.com/ivmai/bdwgc/releases.atom). |
| 373 |
Notifications on all issues and pull requests are available |
| 374 |
by [watching](https://github.com/ivmai/bdwgc/watchers) the project. |
| 375 |
|
| 376 |
Mailing lists ([email protected], [email protected], |
| 377 |
and the former [email protected] and [email protected]) are not |
| 378 |
used at this moment. Their content is available |
| 379 |
in |
| 380 |
[bdwgc-announce](https://github.com/ivmai/bdwgc/files/1037650/bdwgc-announce-mailing-list-archive-2014_02.tar.gz) |
| 381 |
and |
| 382 |
[bdwgc](https://github.com/ivmai/bdwgc/files/1038163/bdwgc-mailing-list-archive-2017_04.tar.gz) |
| 383 |
archive files, respectively. The gc list archive may also be read |
| 384 |
at [Narkive](http://bdwgc.opendylan.narkive.com). |
| 385 |
|
| 386 |
Some prior discussion of the collector has taken place on the gcc java mailing |
| 387 |
list, whose archives appear [here](http://gcc.gnu.org/ml/java/), and also |
| 388 |
on [[email protected]](http://lists.tunes.org/mailman/listinfo/gclist). |