[m-dev.] New conservative GC

[Ralph Becket]

Michael Day, Thursday, 12 April 2007:
> Hi Ralph,
> 
> >I've just put the finishing touches to my garbage collector (you can
> >check it out of the Mercury repository as `hgc').  I've made no attempt
> >to optimise it, but early benchmark results are encouraging.
> 
> That looks interesting; any quick explanation of why it is so much 
> faster than the existing garbage collector for your benchmarks?

The collector is based on the paper "One pass real-time generational
mark-sweep garbage collection", by Joe Armstrong and Robert Virding
(1995).

In this style of collector, every cell has an extra "history" pointer
attached used to link cells together in order of creation (spare tag
bits in the history pointer are also used for marking during garbage
collection).  The head of the allocation chain is the most recently
created cell, while the last cell in the allocation chain is the oldest
live cell.

Because cells can only reference older cells (except for mutable cells,
which require special treatment), it follows that one can mark and sweep
the allocation chain in a single pass.  Moreover, one can collect
incrementally (i.e., only do a limited amount of work at a time) and
generationally (i.e., stop collecting at the point in the allocation
chain that marks the start of the survivors of the previous collection).
The cells that are collected are immediately available for reuse.  I
suspect that all of these things add up more cache-friendly behaviour -
which was what prompted me to try the experiment - than is possible with
Boehm GC, which has to assume that mutable cells are the norm.

In HGC, mutable cells are only collected during a major collection,
which uses a traditional two-pass mark-sweep algorithm.  However, major
collections are invoked relatively rarely (by default ten minor
collections occur before each major collection).  HGC would probably not
be a good choice for, say, Java or C programs, but should work nicely
for declarative languages.

Anyway, I need to investigate more, try using it with some real
programs, and write it up.  Still, I'm very encouraged: I expected I'd
have to do a lot of tweaking to be competitive with Boehm, but on these
toy benchmarks at least my unoptimised collector is winning by a huge
margin.

-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------