Debian Codegraph @

external/bdwgc/doc/overview.md

raw
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).