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

Henry G. Baker hbaker@netcom.com
Wed, 29 Jan 1997 15:24:10 -0800 (PST)

> 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.

Isn't this essentially the _original_ (1976-78) RTGC algorithm for
'displaced' (CL/Maclisp terminology) objects (i.e., objects with
headers) ??

Henry Baker
www/ftp directory: