Re: OOC Garbage Collector Proposal

[Brian Hawley <brian.hawley@bigfoot.com>]

Mike> I would appreciate any algorithms you might be able to dig up--
Mike> especially if they are written in Oberon-2.  Selecting different

Mark> I posted a few URLs to pages containing extensive GC information in a
Mark> previous message. For convenience, I have repeated the URLs below. You
Mark> may especially want to read Paul Wilson's survey found at
Mark> ftp://ftp.cs.utexas.edu//pub/garbage/bigsurv.ps. It is about the best
Mark> introduction to uniprocessor garbage collection that I have found.
Mark>
Mark>   Boehm:         http://reality.sgi.com/employees/boehm_mti/gc.html
Mark>   Richard Jones:
http://stork.ukc.ac.uk/computer_science/Html/Jones/gc.html
Mark>   Harlequin:     http://www.harlequin.com/mm/reference/
Mark> 
Mark> In addition, there are ways of bounding the pauses due to garbage
Mark> collection so that the pauses can be tuned to an acceptable level.
Mark> Such are called incremental collectors and they are necessary for
Mark> real-time collection. Henry Baker presented an algorithm, which was
Mark> used in a system that I maintained. It works well. You can find it at:
Mark> 
Mark>   ftp://ftp.netcom.com/pub/hb/hbaker/NoMotionGC.html
Mark>   ftp://ftp.netcom.com/pub/hb/hbaker/NoMotionGC.ps.Z

You should also look at the paper by Paul Wilson on a better way to do real
time GC than Baker's at
  ftp://ftp.cs.utexas.edu/pub/garbage/GC93/wilson.ps
An implementation of Scheme (with source) that uses this technique is at
  http://www.rscheme.org/
I think that this technique would work well with Oberon.

Mike> garbage collection schemes may have to be specified during the
Mike> compiler build since it might be dangerous to mix and match different
Mike> techniques within one set of modules which are then linked with
Mike> another set of modules.  (I'm assuming here that these schemes
Mike> would require different compiler support which is embedded in
Mike> the generated code.)

Mark> I don't think different compiler support is required for multiple GC
Mark> algorithms since they all determine liveness by reachability from a
Mark> core set of anchor/root locations. The differences come from how they
Mark> trace reachability and how they separate live objects from garbage.
Mark> Since I haven't implemented any algorithms (only read and worked with
Mark> them), I can't say that with complete confidence however.

GC techniques usually need compiler support for one reason or another. The
Boehm collector doesn't need any because it is conservative and non-moving.
This is also why it is slow and memory inefficient, but it's the only type
that works well with type-poor languages like C. Precise GC needs type tags
either at the type or value level to distinguish which values are pointers.
Copying GC either needs a level of indirection in every pointer reference
or some way to rewrite pointers to point to the new location, although when
this happens varies depending on the method used. This affects all pointer
references and address arithmetic that the compiler generates. C programs
can't use copying collectors because address arithmetic is allowed in the
source language, unless special care is taken to implement manually the
hacks that a compiler has to generate to support it (although this does
make using C as a back end possible). Allowing a copying GC to scan the
stack either requires type tages for stack frames (and you can forget tail
recursion optimization and procedure inlining with that) or some form of
read or write barrier, any of which would have to be implemented by the
compiler (page fault barriers are too slow and non-portable). Seperate
compilation of modules when you can choose your GC is only practical for
systems with run-time code generation (like Juice).

Nonetheless, a portable Oberon-2 collector would be a great idea, if only
to reduce our dependency on someone else's C code for ports. You would have
to be extra careful when using external code when you have precise GC, but
the efficiency benefits would be worth it. I think a collector like the one
used by BlackBox that allocates multiple heaps as needed (or does it expand
and contract one heap?) would help.

I'm definitely for this one, if only because it sounds easier to port to
LCC-Win32 than the Boehm collector, and easier to use with native backends.

>Mark K. Gardner (mkgardne@cs.uiuc.edu)
>University of Illinois at Urbana-Champaign
>Real-Time Systems Laboratory

Brian Hawley
Multi-language hacker :)