In response to my note about John McCarthy’s inventing automatic (non ref-counted) garbage collection, rosen4obg asked:
OK, GC was invented half a century ago. When it is going to land in the C++ world?
Here’s a short but detailed answer, which links to illuminating reading and videos.
The Three Kinds of GC
The three major families of garbage collection are:
- Reference counting.
- Mark-sweep (aka non-moving) collectors, where objects are collected but live objects don’t move. This is what McCarthy first invented.
- Mark-compact (aka moving) collectors, where live objects are moved together to make allocated memory more compact. Note that doing this involves updating pointers’ values on the fly. This category includes semispace collectors as well as the more efficient modern ones like the .NET CLR’s that don’t use up half your memory or address space.
When I say “automatic GC” I mean #2 or #3.
GC and C++
C++ has always supported #1 well via reference counted smart pointers. Those are now standard in C++11 in the form of unique_ptr, shared_ptr, weak_ptr. C++98 had auto_ptr, but it was never great and has been deprecated.
C++ has long supported #2, but less formally because the products were nonstandard, conservative, and not as portable. The major prior art is the Boehm (later Great Circle and Symantec) mark-sweep garbage collector. The new C++11 standard has just added a minimal GC ABI to more formally bless such non-moving collectors; see Stroustrup’s GC FAQ for more.
C++ cannot support #3 without at least a new pointer type, because C/C++ pointer values are required to be stable (not change their values), so that you can cast them to an int and back, or write them to a file and back; this is why we created the ^ pointer type for C++/CLI which can safely point into #3-style compacting GC heaps. See section 3.3 of my paper A Design Rationale for C++/CLI for more rationale about ^ and gcnew.
Other GC Resources
For a wonderful 57-minute conversation on garbage collection by one of the world’s top GC experts, run don’t walk to the C9 “Inside Garbage Collection” interview with Patrick Dussud. Patrick wrote the .NET CLR’s GC, and it was far from his first; before that he had deep experience implementing Lisp runtimes, and I’m sure has forgotten more about GC than I’ll ever know. He’s also a great guy to work with.
For a great book on GC, I love Garbage Collection by Jones and Lins.