[virtmach] garbage collection

David Rush kumo@bellsouth.net
18 May 2000 17:28:52 +0100

thaddaeus.frogley@creaturelabs.com writes:
> Anyone got any links and / or advice on garbage collection ? :)

There are boatloads of GC info on the web. Henry Baker's website[1] is
a good place to start if you're just generally interested in the topic
(The downside is that Baker's into a *lot* of cool stuff - you have to
wade through a bit to find the GC). I also picked up a great survey
book called (pedantically enough) _Garbage_Collection_ by Richard
Jones and Rafael Lins. It's a fairly thorough survey of the field as
of 1996.

> I'm thinking, VM (obviously), single threaded environment, indexes into a
> repository containing polymorphic objects act as handles and are stored on
> an untyped stack.  

You're looking at a model that is very similiar to the original
Smalltalk-80 VM's GC scheme. _Smalltalk-80:The_Language_and_Its_Implementation_
is the canonical reference for it. I don't know if it can still be
bought. The central idea is the use of a master 'object table' so each
object reference is doubly-indirect. This makes object relocation very
easy, albeit at a somewhat higher constant overhead for every object

Does anyone know what effect the ST80 GC organization has on cache
locality? I've been diddling some ideas about OS support for GC
lately, and I'm curious...

> The way I see it, if 'n' isn't on the untyped stack then no references to
> object 'n' exist, then it can be removed from the polymorphic repository.

You can use the VM stack as your initial root set (assuming that you
have a compatible treatment for the global environment), but the stack
won't contain all object references (unless your VM can't have nested

> (I don't actually think I'm going to need this, I interested in ways it
> could be done if I did...)

Unless you've got explicit allocation/deallocation operators (or a
very clever compiler that does region/lifetime analysis), you need GC
of some form. The question is at what level of complexity.

david rush
[1] ftp://ftp.netcom.com/pub/hb/hbaker/home.html