[m-dev.] Alternative garbage collector

[Ralph Becket]

I've just come across Fred Smith and Greg Morrisett's work on
mostly copying garbage collection (see
http://www.cs.cornell.edu/Info/People/fms/MCC/gc.html).

It's interesting stuff: generally competitive with the Boehm GC,
but some programs can reap a 40% performance improvement - and 
that's with an untuned collector.

There are a number of attractive points about MCC (their
implementation):
1. it's straightforward to extend to support concurrent GC and
2. it works with both conservative and non-conservative
allocations (for a non-conservative allocation you supply a
32-bit mask indicating which words in a new allocation
may contain pointers).

In their paper they report that on a SPARC their implementation
takes about 200 machine instructions to check a pointer during
collection vs. about 30 for the Boehm collector.  However, they
only have to check a fraction of the possible pointers that the
Boehm GC does.

The reason their pointer checking is costly is because their
allocation strategy is by simple heap-pointer increment, hence
differently sized allocations will not be separated into different
heap `pages', which means that the GC-engine has to search each
page for the start of an allocation when checking a pointer.  They
took this approach so they could keep the HP in a machine register.

On an x86 architecture this isn't really an option anyway, so
there's no real penalty in having multiple heap pointers for
different sized allocations (hence reducing the cost of checking
a possible pointer to that of the Boehm GC).  I suspect this would
make MCC a very attractive option on x86 architectures.

The downside is that, as it's a copying collector, it has a larger
memory footprint that the Boehm GC.

Any thoughts?

- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------