conservative garbage collection?

[Geoffrey Irving]

When we start transitioning to low level data layout, I think we may want to use a conservative garbage collector.  Conservative collection would provide the following rather large advantages:

1. No worrying about listing register roots in generated code, so no shadow stack nastiness for C or LLVM (this is huge).
2. None of the complexity of type directed collection.  We can arrange data however we like, and it will just work.
3. No garbage collection complexity issues across language boundaries.
4. If we want them, finalizers and other fancy features for free.
5. The Boehm collector has support for marking objects pointer-free, so no wasted time scanning large data array (more a similarity than an advantage).

Disadvantages vs. accurate collection include

1. No copy collection, so potentially worse cache behavior for garbage intensive loop code.
2. Slightly unpleasant from a purity standpoint (this has near zero weight).

(2) doesn't really matter, and I'm not too concerned about (1).  I have a general feeling that if a performance critical algorithm is producing vast amounts of garbage, there is probably an even faster version of the algorithm that doesn't (perhaps one that uses arrays).  Maybe we won't beat Haskell on the "allocate a bunch of trees that then become garbage" benchmark, but no one cares.

Overall, the main advantage is freeing ourselves from the huge weight of complexity looming over us at the prospect of fitting an accurate garbage collector into unfriendly environments.

Options for conservative collectors include the Boehm collector and Apple's AutoZone collector:

1. http://www.opensource.apple.com/source/autozone/autozone-77.1/README.txt
2. http://www.hpl.hp.com/personal/Hans_Boehm/gc

Thoughts?

Geoffrey

[Dylan Alex Simon]

From Geoffrey Irving <irv...@naml.us>, Wed, Sep 02, 2009 at 09:45:43AM -0400:

I don't really know much about it, though boehm-gc is one of the few I've
used, and it's what gcc uses for objective-c. Also, that autozone page has
some unpleasant formatting.

How easily can we make LLVM work with these? How exactly do boxed arrays
look? Do we have to worry about internal pointers?

Are you on a 64-bit machine?

Unrelated: I've been making a mess of Pretty and precedence lately, and
noticed how we're parsing '::' and '->'. Are you sure you like their current
relative precedences?

1 :: 2 -> 3 :: 4

Seems like it should be:

(1 :: 2) -> (3 :: 4)

Not parse failure. I think.

:-Dylan

[Geoffrey Irving]

There should be nothing to do to make LLVM work with them beyond
calling their versions of malloc.

Boxed arrays would be a block not tagged as pointer-free with a size
followed by a bunch of pointers. I may not have understood the
question, though.

The Boehm gc detects internal pointers automatically (and conservatively).

> Are you on a 64-bit machine?

Yes, mostly (and more completely once I upgrade to Mac OS 10.6). Why?

Geoffrey