Kick Butt, Eat Lunch, and Take out the Garbage

That was the motto of the Sun Labs GC Research group which I joined back in 1998.  After spending 5 years working on Fortress, the best programming language no one has ever worked with, I’m back to doing GC work again.  I’d love to tell you about Shenandoah, the new GC we’re working on at Red Hat, but before I do I’m going to give you a GC history lesson.

Back in 1998 when I joined Sun the only JVM that I knew of was the reference VM.  This VM had what was called a conservative garbage collector.  You had to guess whether objects on the stack were pointers or not, if they looked like a correctly aligned address in allocated memory then they were considered a pointer.  This GC has the benefit that it is easy to implement, but it has a couple of deficits.  The first downside is that you can’t move any object that is referenced from the stack.   This means that you can’t compact the live objects, and that you can’t do fast “pointer bump” allocation.  This is huge.  The cost of having to maintain free lists, and more importantly find a free block at allocation time was too high.  The other downside was that integers that looked like pointers could keep dead objects alive. 

My group, I had little to do with this, ripped the guts out of the reference VM and added safepoints and stackmaps.  Stackmaps are a contract between the compiler and the garbage collector.  The compiler already has this information so it only makes sense for it to share with the GC.  Stackmaps tell you the type of every location on the stack.  Maintaining them all the time is expensive and inhibits many compiler optimizations, so therefore we need safepoints.  For example the compiler is allowed to keep pointers into the middle of objects between safepoints, but at safepoints the stack must be consistent.  Safepoints are frequent enough (allocations, backward branches, etc) that waiting to get to a safepoint to GC is reasonable. 

Safepoints and Stackmaps enabled the first generational copying collector which I’ll talk about in my next post.