[gclist] Tradeoffs in collectors

[Charles Fiterman]

> I've seen a lot of work done on making GCs fast or incremental.  What
> kinds of systems are recommended for saving space (both data and
> code)?  
> 
> In my case, I'm writing a small DOS application that needs to fit in
> 300k, so I want to make something really simple that doesn't have a
> lot of overhead per object.  I also don't have VM tricks to play with.
> A two-space copying collector is out due to space reasons.  :(
> 
> I would expect that GCs for small embedded systems would be what I
> need:
> 
> 	- small data overhead
> 	- small collector code size
> 	- small address space (no VM)

Let me suggest my infamous mark and don't sweep collector. Each object
starts with a pointer to a descriptor for that object. All methods on
the object are pointed to by the descriptor and accept a pointer to the
actual object as their first parm. All objects have a length() operator
in a consistant place. In OO terms everything is decended from a class
that can return its length.

All descriptors start at even addresses so the low order bit is always
available for other stuff. We use it for used free but the sense reverses.

The allocator scans forward looking for a large enough hole. Here is the
gimmic. If it passes a free object that is too small it marks it as used.
So when we reach the end of the heap everything is marked used.

Now flip the sense of used and free so everything is free. Start from
the root marking things used as they can be reached. Each object can
have a method for marking what it can reach in a consitant place on
the descriptor.

When the mark phase finishes repoint the scan pointer to the biginning
of the heap and restart.

I don't see how you can have less space per object and the allocator
collector seem close to minamal.

If you are looking for something less Spartan and would like to live
with C++ we, Geodesic Systems, have a treadmill wrapped pointer collector.