GC -- Looking ahead

[Eric W. Biederman]

There are quite a number of different ways to do garbage collection.
In the long run we need to implement an incremental garbage collector
with a bounded run-time it executes and collects some garbage.  These
collectors get rid of those annoying pauses.

Further for gabage collection in a distributed setting there is a nice
algorithm that relies upon object migration.  Basically all
collections are local, with objects migrating to other sites when they
have no more local references.  The objects either migrate to a node
that remotely references them, or when that's not possible they
migrate to a dedicated collection node, whose sole responsibility is
to collect circular distributed structers.  This acheives performance
as if it was local.

The major optimization that we need to be concerned with when we do an
implementation is locality of reference in the collection scheme, so
we probably will need to have a stack that does not embed it's
stack into pointers of the objects it is collecting.  Or at most a
mixed approach.  This will allow us to sort the order in which objects
are moved allowing better locality of reference for the collector.

With reference to the lambda functions capturing their runtime state,
in general we don't need to save the frames of the functions invoked.
This is only necessary when exceptions and other such functions begin
to be implemented.  When we get to implementing this there is a very
nice algorithm for implementing a special garbage collector for just
the procedure frames, independently of the rest of the garbage.  It is
optimized for coroutines (a cross between threads, and functions,
basically synchronous threads that you call as functions) so is a
little more restrictive then schemes call-with-current-continuation
(call/cc), but call/cc can be implemented with it. It is incremental
(I think), generational, and can use a normal stack, that grows
dynamically, and in the normal case requires only one extra comparison
before freeing it's stack frame.  For the time being allocate function
frames upon the stack.  We will have to be carefull about how pointers
are found inside of a stack frame though as these are roots.  If we
for the moment restrict ourselves to the case of synchronous GC, we
need not worry about which machine registers hold pointers.

Initially, for our first implementation of the LLL, we should
implement a crude copying collector, and then reimplement it with a
nicer a nicer set of garbage collectors, in the LLL itself.  I suspect
a really nice way to implement a concurrent garbage collector would be
with coroutines, from inside the memory allocation function.  That way
there would be no need to sychronize.  Possibly even allowing the
garabe collector to garbage collect it's useless garbage collecting
information. 

Anyway there are my long-range plans, for GC.  For the short range
let's just KISS.

Now all we have to do is figure out is what kinds of data types and
which opeations on them, our lll will support.

Eric