Archive for October 25th, 2011

Insert your favorite "stop the world" joke here.

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:

  1. Reference counting.
  2. Mark-sweep (aka non-moving) collectors, where objects are collected but live objects don’t move. This is what McCarthy first invented.
  3. 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.

Read Full Post »


What a sad, horrible month. First Steve Jobs, then Dennis Ritchie, and now John McCarthy. We are losing many of the greats all at once.

If you haven’t heard of John McCarthy, you’re probably learning about his many important contributions now. Some examples:

  • He’s the inventor of Lisp, the second-oldest high-level programming language, younger than Fortran by just one year. Lisp is one of the most influential programming languages in history. Granted, however, most programmers don’t use directly Lisp-based languages, so its great influence has been mostly indirect.
  • He coined the term “artificial intelligence.” Granted, however, AI has got a bad rap from being oversold by enthusiasts like Minsky; for the past 20 years or so it’s been safer to talk in euphemisms like “expert systems.” So here too McCarthy’s great influence has been less direct.
  • He developed the idea of time-sharing, the first step toward multitasking. Okay, now we’re talking about a contribution that’s pretty directly influential to our modern systems and lives.

But perhaps McCarthy’s most important single contribution to modern computer science is still something else, yet another major technology you won’t hear nearly enough about as being his invention:

Automatic garbage collection. Which he invented circa 1959.

No, really, that’s not a typo: 1959. For context, that year’s first quarter alone saw the beginning of the space age as Sputnik 1 came down at the end of its three-month orbit; Fidel Castro take Cuba; Walt Disney release Sleeping Beauty; The Day the Music Died; the first Barbie doll; and President Eisenhower signing a bill to enable Hawaii to become a state.

GC is ancient. Electronic computers with core memory were still something of a novelty (RAM didn’t show up until a decade or so later), machine memory was measured in scant kilobytes, and McCarthy was already managing those tiny memories with automatic garbage collection.

I’ve encountered people who think GC was invented by Java in 1995. It was actually invented more than half a century ago, when our industry barely even existed.

Thanks, John.

And here’s hoping we can take a break for a while from writing these memorials to our giants.

Read Full Post »