| 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 |
* Some collector details |
| 8 |
* Further reading |
| 9 |
* Information provided on the BDWGC site |
| 10 |
* More background information |
| 11 |
* Contacts and new release announcements |
| 12 |
|
| 13 |
[ This is an updated version of the page formerly at |
| 14 |
`www.hpl.hp.com/personal/Hans_Boehm/gc/`, before that at |
| 15 |
`http://reality.sgi.com/boehm/gc.html` and before that at |
| 16 |
`ftp://ftp.parc.xerox.com/pub/gc/gc.html`. ] |
| 17 |
|
| 18 |
The |
| 19 |
[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) |
| 20 |
conservative Garbage Collector (**BDWGC**) can be used as a garbage collecting |
| 21 |
replacement for C `malloc` or C++ `new`. It allows you to allocate memory |
| 22 |
basically as you normally would, without explicitly deallocating memory that |
| 23 |
is no longer useful. The collector automatically recycles memory when |
| 24 |
it determines that it can no longer be otherwise accessed. A simple example |
| 25 |
of such a use is given [here](simple_example.md). |
| 26 |
|
| 27 |
The collector is also used by a number of programming language implementations |
| 28 |
that either use C as intermediate code, want to facilitate easier |
| 29 |
interoperation with C libraries, or just prefer the simple collector |
| 30 |
interface. For a more detailed description of the interface, see |
| 31 |
[here](gcinterface.md). |
| 32 |
|
| 33 |
Alternatively, the garbage collector may be used as a [leak detector](leak.md) |
| 34 |
for C or C++ programs, though that is not its primary goal. |
| 35 |
|
| 36 |
Typically several versions are offered for |
| 37 |
[downloading](https://github.com/ivmai/bdwgc/wiki/Download): preview, stable, |
| 38 |
legacy. Usually you should use the one marked as the _latest stable_ release. |
| 39 |
Preview versions may contain additional features, platform support, but are |
| 40 |
likely to be less well tested. The list of changes for each version |
| 41 |
is specified on the [releases](https://github.com/ivmai/bdwgc/releases) page. |
| 42 |
The development version (snapshot) is available in the master branch of |
| 43 |
[bdwgc git](https://github.com/ivmai/bdwgc) repository on GitHub. |
| 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/), |
| 54 |
[Hewlett-Packard Company](http://www.hp.com/), |
| 55 |
[Ivan Maidanski](https://github.com/ivmai), and partially by some others. |
| 56 |
It may be used and copied without payment of a fee under minimal restrictions. |
| 57 |
See the README.md file in the distribution or the |
| 58 |
[license](http://www.hboehm.info/gc/license.txt) for more details. |
| 59 |
**IT IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED OR IMPLIED. |
| 60 |
ANY USE IS AT YOUR OWN RISK.** |
| 61 |
|
| 62 |
Empirically, this collector works with most unmodified C programs, simply |
| 63 |
by replacing `malloc` and `calloc` with `GC_malloc` calls, replacing `realloc` |
| 64 |
with `GC_realloc` calls, and removing `free` calls. Exceptions are discussed |
| 65 |
[here](http://www.hboehm.info/gc/issues.html). |
| 66 |
|
| 67 |
## Platforms |
| 68 |
|
| 69 |
The collector is not completely portable, but the distribution includes ports |
| 70 |
to most standard PC and UNIX/Linux platforms. The collector should work |
| 71 |
on Linux, Android, BSD variants, OS/2, Windows (Win32 and Win64), MacOS X, |
| 72 |
iOS, HP/UX, Solaris, Tru64, Irix, Symbian and other operating systems. Some |
| 73 |
platforms are more polished (better supported) than others. |
| 74 |
|
| 75 |
Irix pthreads, Linux threads, Windows threads, Solaris threads (pthreads |
| 76 |
only), HP/UX 11 pthreads, Tru64 pthreads, and MacOS X threads are supported. |
| 77 |
|
| 78 |
## Some Collector Details |
| 79 |
|
| 80 |
The collector uses a [mark-sweep](http://www.hboehm.info/gc/complexity.html) |
| 81 |
algorithm. It provides incremental and generational collection under operating |
| 82 |
systems which provide the right kind of virtual memory support. (Currently |
| 83 |
this includes SunOS[45], IRIX, OSF/1, Linux, and Windows, with varying |
| 84 |
restrictions.) It allows [finalization](finalization.md) code to be invoked |
| 85 |
when an object is collected. It can take advantage of type information |
| 86 |
to locate pointers if such information is provided, but it is usually used |
| 87 |
without such information. See the README and `gc.h` files in the distribution |
| 88 |
for more details. |
| 89 |
|
| 90 |
For an overview of the implementation, see [here](gcdescr.md). |
| 91 |
|
| 92 |
The garbage collector distribution includes a C string (`cord.h`) package that |
| 93 |
provides for fast concatenation and substring operations on long strings. |
| 94 |
A simple curses- and Windows-based editor that represents the entire file as |
| 95 |
a cord is included as a sample application. |
| 96 |
|
| 97 |
Performance of the non-incremental collector is typically competitive with |
| 98 |
`malloc`/`free` implementations. Both space and time overhead are likely to be |
| 99 |
only slightly higher for programs written for `malloc`/`free` (see Detlefs, |
| 100 |
Dosser and Zorn's |
| 101 |
[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)). |
| 102 |
For programs allocating primarily very small objects, the collector may be |
| 103 |
faster; for programs allocating primarily large objects it will be slower. |
| 104 |
If the collector is used in a multi-threaded environment and configured for |
| 105 |
thread-local allocation, it may in some cases significantly outperform |
| 106 |
`malloc`/`free` allocation in time. |
| 107 |
|
| 108 |
We also expect that in many cases any additional overhead will be more than |
| 109 |
compensated for by e.g. decreased copying if programs are written and tuned |
| 110 |
for garbage collection. |
| 111 |
|
| 112 |
## Further reading |
| 113 |
|
| 114 |
**The beginnings of a frequently asked questions list for this collector are |
| 115 |
[here](http://www.hboehm.info/gc/faq.html).** |
| 116 |
|
| 117 |
**The following provide information on garbage collection in general:** |
| 118 |
|
| 119 |
Paul Wilson's |
| 120 |
[garbage collection ftp archive](ftp://ftp.cs.utexas.edu/pub/garbage) |
| 121 |
and [GC survey](ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps). |
| 122 |
|
| 123 |
The Ravenbrook |
| 124 |
[Memory Management Reference](http://www.memorymanagement.org/). |
| 125 |
|
| 126 |
David Chase's [GC FAQ](http://www.iecc.com/gclist/GC-faq.html). |
| 127 |
|
| 128 |
Richard Jones' |
| 129 |
[Garbage Collection Page](https://www.cs.kent.ac.uk/people/staff/rej/gc.html) |
| 130 |
and his [book](http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html). |
| 131 |
|
| 132 |
**The following papers describe the collector algorithms we use and the |
| 133 |
underlying design decisions at a higher level:** |
| 134 |
|
| 135 |
(Some of the lower level details can be found [here](gcdescr.md).) |
| 136 |
|
| 137 |
The first one is not available electronically due to copyright considerations. |
| 138 |
Most of the others are subject to ACM copyright. |
| 139 |
|
| 140 |
Boehm, H., Dynamic Memory Allocation and Garbage Collection, |
| 141 |
_Computers in Physics 9_, 3, May/June 1995, pp. 297-303. This is directed |
| 142 |
at an otherwise sophisticated audience unfamiliar with memory allocation |
| 143 |
issues. The algorithmic details differ from those in the implementation. There |
| 144 |
is a related letter to the editor and a minor correction in the next issue. |
| 145 |
|
| 146 |
Boehm, H., and [M. Weiser](http://www.ubiq.com/hypertext/weiser/weiser.html), |
| 147 |
[Garbage Collection in an Uncooperative Environment](http://www.hboehm.info/spe_gc_paper/), |
| 148 |
_Software Practice and Experience_, September 1988, pp. 807-820. |
| 149 |
|
| 150 |
Boehm, H., A. Demers, and S. Shenker, |
| 151 |
[Mostly Parallel Garbage Collection](http://www.hboehm.info/gc/papers/pldi91.ps.Z), |
| 152 |
Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design |
| 153 |
and Implementation, _SIGPLAN Notices 26_, 6 (June 1991), pp. 157-164. |
| 154 |
|
| 155 |
Boehm, H., |
| 156 |
[Space Efficient Conservative Garbage Collection](http://www.hboehm.info/gc/papers/pldi93.ps.Z), |
| 157 |
Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design |
| 158 |
and Implementation, _SIGPLAN Notices 28_, 6 (June 1993), pp. 197-206. |
| 159 |
|
| 160 |
Boehm, H., Reducing Garbage Collector Cache Misses, |
| 161 |
_Proceedings of the 2000 International Symposium on Memory Management_. |
| 162 |
[Official version](http://portal.acm.org/citation.cfm?doid=362422.362438). |
| 163 |
[Technical report](http://www.hpl.hp.com/techreports/2000/HPL-2000-99.html) |
| 164 |
version. Describes the prefetch strategy incorporated into the collector for |
| 165 |
some platforms. Explains why the sweep phase of a _mark-sweep_ collector |
| 166 |
should not really be a distinct phase. |
| 167 |
|
| 168 |
M. Serrano, H. Boehm, Understanding Memory Allocation of Scheme Programs, |
| 169 |
_Proceedings of the Fifth ACM SIGPLAN International Conference on Functional |
| 170 |
Programming_, 2000, Montreal, Canada, pp. 245-256. |
| 171 |
[Official version](http://dl.acm.org/citation.cfm?id=351264). Earlier |
| 172 |
[Technical Report](http://www.hpl.hp.com/techreports/2000/HPL-2000-62.html) |
| 173 |
version. Includes some discussion of the collector debugging facilities for |
| 174 |
identifying causes of memory retention. |
| 175 |
|
| 176 |
Boehm, H., Fast Multiprocessor Memory Allocation and Garbage Collection, |
| 177 |
[HP Labs Technical Report HPL 2000-165](http://www.hpl.hp.com/techreports/2000/HPL-2000-165.html). |
| 178 |
Discusses the parallel collection algorithms, and presents some performance |
| 179 |
results. |
| 180 |
|
| 181 |
Boehm, H., Bounding Space Usage of Conservative Garbage Collectors, |
| 182 |
_Proceedings of the 2002 ACM SIGPLAN-SIGACT Symposium on Principles |
| 183 |
of Programming Languages_, Jan. 2002, pp. 93-100. |
| 184 |
[Official version](http://portal.acm.org/citation.cfm?doid=503272.503282). |
| 185 |
[Technical report](http://www.hpl.hp.com/techreports/2001/HPL-2001-251.html) |
| 186 |
version. Includes a discussion of a collector facility to much more reliably |
| 187 |
test for the potential of unbounded heap growth. |
| 188 |
|
| 189 |
**The following papers discuss language and compiler restrictions necessary |
| 190 |
to guaranteed safety of conservative garbage collection:** |
| 191 |
|
| 192 |
We thank John Levine and JCLT for allowing us to make the second paper |
| 193 |
available electronically, and providing PostScript for the final version. |
| 194 |
|
| 195 |
Boehm, H., |
| 196 |
[Simple Garbage-Collector-Safety](http://www.hboehm.info/gc/papers/pldi96.ps.gz), |
| 197 |
Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design |
| 198 |
and Implementation. |
| 199 |
|
| 200 |
Boehm, H., and D. Chase, |
| 201 |
[A Proposal for Garbage-Collector-Safe C Compilation](http://www.hboehm.info/gc/papers/boecha.ps.gz), |
| 202 |
_Journal of C Language Translation 4_, 2 (December 1992), pp. 126-141. |
| 203 |
|
| 204 |
**Other related information:** |
| 205 |
|
| 206 |
The Detlefs, Dosser and Zorn's |
| 207 |
[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). |
| 208 |
This is a performance comparison of the Boehm-Demers-Weiser collector |
| 209 |
to `malloc`/`free`, using programs written for `malloc`/`free`. |
| 210 |
|
| 211 |
Joel Bartlett's |
| 212 |
[mostly copying conservative garbage collector for C++](ftp://gatekeeper.dec.com/pub/compaq/WRL/research-reports/WRL-TN-12.ps). |
| 213 |
|
| 214 |
John Ellis and David Detlef's |
| 215 |
[Safe Efficient Garbage Collection for C++](http://dl.acm.org/citation.cfm?id=1267983) |
| 216 |
proposal. |
| 217 |
|
| 218 |
Henry Baker's [paper collection](http://home.pipeline.com/%7Ehbaker1/). |
| 219 |
|
| 220 |
Slides for Hans Boehm's |
| 221 |
[Allocation and GC Myths](http://www.hboehm.info/gc/myths.ps) talk. |
| 222 |
|
| 223 |
## Information provided on the BDWGC site |
| 224 |
|
| 225 |
[Current users](https://github.com/ivmai/bdwgc/wiki/Known-clients) (the list |
| 226 |
may be rather outdated). |
| 227 |
|
| 228 |
[A simple illustration of how to build and use the collector](simple_example.md). |
| 229 |
|
| 230 |
[Description of alternate interfaces to the garbage collector](gcinterface.md). |
| 231 |
|
| 232 |
[Slides from an ISMM 2004 tutorial about the GC](http://www.hboehm.info/gc/04tutorial.pdf). |
| 233 |
|
| 234 |
[A FAQ (frequently asked questions) list](http://www.hboehm.info/gc/faq.html). |
| 235 |
|
| 236 |
[How to use the garbage collector as a leak detector](leak.md). |
| 237 |
|
| 238 |
[Some hints on debugging garbage collected applications](debugging.md). |
| 239 |
|
| 240 |
[An overview of the implementation of the garbage collector](gcdescr.md). |
| 241 |
|
| 242 |
[The data structure used for fast pointer lookups](tree.md). |
| 243 |
|
| 244 |
[Scalability of the collector to multiprocessors](scale.md). |
| 245 |
|
| 246 |
[Directory](http://www.hboehm.info/gc/gc_source/) containing the distribution |
| 247 |
files of all garbage collector releases. It duplicates |
| 248 |
[Download](https://github.com/ivmai/bdwgc/wiki/Download) page on GitHub. |
| 249 |
|
| 250 |
## More background information |
| 251 |
|
| 252 |
[An attempt to establish a bound on space usage of conservative garbage collectors](http://www.hboehm.info/gc/bounds.html). |
| 253 |
|
| 254 |
[Mark-sweep versus copying garbage collectors and their complexity](http://www.hboehm.info/gc/complexity.html). |
| 255 |
|
| 256 |
[Pros and cons of conservative garbage collectors, in comparison to other collectors](http://www.hboehm.info/gc/conservative.html). |
| 257 |
|
| 258 |
[Issues related to garbage collection vs. manual memory management in C/C++](http://www.hboehm.info/gc/issues.html). |
| 259 |
|
| 260 |
[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). |
| 261 |
|
| 262 |
[Slide set discussing performance of nonmoving garbage collectors](http://www.hboehm.info/gc/nonmoving/). |
| 263 |
|
| 264 |
[Slide set discussing _Destructors, Finalizers, and Synchronization_, POPL 2003](http://www.hboehm.info/popl03/web/). |
| 265 |
|
| 266 |
[Paper corresponding to above slide set](http://portal.acm.org/citation.cfm?doid=604131.604153) |
| 267 |
([Technical Report](http://www.hpl.hp.com/techreports/2002/HPL-2002-335.html) |
| 268 |
version). |
| 269 |
|
| 270 |
[A Java/Scheme/C/C++ garbage collection benchmark](http://www.hboehm.info/gc/gc_bench/). |
| 271 |
|
| 272 |
[Slides for talk on memory allocation myths](http://www.hboehm.info/gc/myths.ps). |
| 273 |
|
| 274 |
[Slides for OOPSLA 98 garbage collection talk](http://www.hboehm.info/gc/gctalk.ps). |
| 275 |
|
| 276 |
[Related papers](http://www.hboehm.info/gc/papers/). |
| 277 |
|
| 278 |
## Contacts and new release announcements |
| 279 |
|
| 280 |
GitHub and Stack Overflow are the major two places for communication. |
| 281 |
|
| 282 |
Technical questions (how to, how does it work, etc.) should be posted |
| 283 |
to [Stack Overflow](https://stackoverflow.com/questions/tagged/boehm-gc) with |
| 284 |
_boehm-gc_ tag. |
| 285 |
|
| 286 |
To contribute, please rebase your code to the latest |
| 287 |
[master](https://github.com/ivmai/bdwgc/tree/master/) and submit |
| 288 |
a [pull request](https://github.com/ivmai/bdwgc/pulls) to GitHub. |
| 289 |
|
| 290 |
To report a bug, or propose (request) a new feature, create |
| 291 |
a [GitHub issue](https://github.com/ivmai/bdwgc/issues). Please make sure |
| 292 |
it has not been reported yet by someone else. |
| 293 |
|
| 294 |
To receive notifications on every release, please subscribe to |
| 295 |
[Releases RSS feed](https://github.com/ivmai/bdwgc/releases.atom). |
| 296 |
Notifications on all issues and pull requests are available |
| 297 |
by [watching](https://github.com/ivmai/bdwgc/watchers) the project. |
| 298 |
|
| 299 |
Mailing lists ([email protected], [email protected], |
| 300 |
and the former [email protected] and [email protected]) are not |
| 301 |
used at this moment. Their content is available |
| 302 |
in |
| 303 |
[bdwgc-announce](https://github.com/ivmai/bdwgc/files/1037650/bdwgc-announce-mailing-list-archive-2014_02.tar.gz) |
| 304 |
and |
| 305 |
[bdwgc](https://github.com/ivmai/bdwgc/files/1038163/bdwgc-mailing-list-archive-2017_04.tar.gz) |
| 306 |
archive files, respectively. The gc list archive may also be read |
| 307 |
at [Narkive](http://bdwgc.opendylan.narkive.com). |
| 308 |
|
| 309 |
Some prior discussion of the collector has taken place on the gcc java mailing |
| 310 |
list, whose archives appear [here](http://gcc.gnu.org/ml/java/), and also |
| 311 |
on [[email protected]](http://lists.tunes.org/mailman/listinfo/gclist). |