Debian Codegraph @

gc/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 * 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).