[gclist] Baker's treadmill without a doubly linked list.

[James McCartney]

I thought I would use this forum to make public knowledge a method I came
up with to implement Baker's treadmill GC in an array of pointers rather
than a linked list. My version of the algorithm allocates white and uses
a write barrier that changes a white object to grey if it is inserted into
a black object. This scheme does not use any less memory because there are
still two overhead words per object: the slot in the array and a field in
the object denoting its index in the array.

The array of object pointers contains pointers to all objects in the
treadmill. The array is arranged such that black objects are
at the lowest indices, followed by grey objects, white objects,
and free objects in that order.  There are several indices into the array.
The scan index points to the first grey object, the white index points to
the first white object and the allocate index points to the first free object.

In order to allocate an object the object at the allocate index is
returned and the allocate index is incremented.

In order to get an object to scan the object at the scan index is
returned and the scan index is incremented. When the scan index
equals the white index, the GC cycle is complete.

In order to turn a white object grey, the object pointer at the white index
is swapped with the pointer to the white object that is to turn grey. The
white index is then incremented and the index fields of the two objects are
swapped. Turning a white object grey requires the white object know its index
in the array so that you know what location to swap with.

It is easy at any time to determine the number of objects of any color by
comparing indices.


   --- james mccartney     james@clyde.as.utexas.edu   james@lcsaudio.com
If you have a PowerMac check out SuperCollider, a real time synth program:
ftp://mirror.apple.com//mirrors/Info-Mac.Archive/gst/snd/super-collider-demo.hqx