A big step towards generational and compacting GC

People frequently ask me for status updates on generational GC, and I usually say I’ll tell them when something notable happens. Well, something notable just happened: exact rooting landed.

What is exact rooting? In order to support generational and/or compacting GC, you need to be able to move GC-allocated things such as objects around. This means you can’t have raw C++ pointers to any objects that might move; instead, you need some kind of indirect pointer that can be updated when necessary.

Unfortunately, both the JS engine and Gecko have a lot of pointers to GC-allocated things. The process of checking and converting them has been the main part of a task called “exact rooting”, and that’s what just finished. This has required an enormous amount of what is essentially very tedious work. Jim Blandy summarized it nicely, as follows.

I’ve never heard of a major project escaping from conservative GC once it had entered that state of sin; nor have I heard of anyone implementing a moving collector after starting with a non-moving collector. So, doing *both* is impressive. I hope it pays off big!

Major kudos to Terrence Cole, Steve Fink, Jon Coppeard, Brian Hackett, and the small army of other helpers who did this. Now that they’ve finished eating this gigantic serving of vegetables, they can move onto dessert, i.e. making the GC generational and compacting.

6 Responses to A big step towards generational and compacting GC

  1. Great job guys!
    You all deserve awards!

  2. That’s fantastic! Congratulations to everyone. Refactoring something that fundamental for something so massive is very impressive! What are the expected gains in efficiencies for compacting/generational GC?

  3. Rodrigo kumpera

    Mono started with boehm and have switched to a moving collector for a few years.

    The same process of cleaning up native references to managed pointer had happened there too.

  4. It all depends on what you mean by “major project”, but Racket (then called PLT Scheme) successfully escaped from imprecise GC, despite a runtime system that involved ~500,000 lines of C and C++ and had been developed for 10+ years. That runtime included everything from a forked copy of WxWindows to a networking system.

    You can read more about it here: http://www.cs.utah.edu/plt/publications/ismm09-rwrf.pdf — the basic trick is a tool that re-writes C (and some C++) to cooperate with the GC. Documentation for the tool is here: http://docs.racket-lang.org/inside/im_memoryalloc.html

  5. As someone that is at least as interested in vegetables as in desserts, I find your metaphor awkward, but otherwise, great work :-)