Wed Aug 12 10:13:23 CEST 2009

Cheney GC

[ Minsky-Fenichel-Yochelson-Cheney-Arnborg (MFYCA) method ]

Like a recursive mark and copy collector, but using a breadth-first

  1 Copy all root objects: copy atoms, update moved vectors and copy
    vectors not yet moved.

  2 Copy all references in newly allocated objects.

  3 Repeat until heap stops growing (all reachable objects are moved).

OK: typed in, compiling, not working: it blows up.  Simplified, but I
can't see it.  Guess it's time for a proof.

An interesting challenge this is: I've always stayed away from
implementing graph algorithms in C.  It requires a lot of discipline
to get the invariants right.  The cause is usually due to embedding
and premature optimization, i.e. using the same field to represent two
distinct values in different modes when there are subtle cases where
this is not valid.  The Cheney algo is a simple one, but I couldn't
get it right ``just writing it down''.

Ha.. Indeed: caused by leaky abstractions: the problem was that vector
tags didn't get copied, which probably triggered an allocation loop in
the interpreter due to type errors.

Next: add assertions and error handling for the whole project.

[1] http://en.wikipedia.org/wiki/Cheney%27s_algorithm