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

Henry G. Baker hbaker@netcom.com
Thu, 30 Jan 1997 07:31:51 -0800 (PST)

> At 8:44 PM -0800 1/29/97, Henry G. Baker wrote:
> >> At 3:24 PM -0800 1/29/97, Henry G. Baker wrote:
> >> >
> >> >Isn't this essentially the _original_ (1976-78) RTGC algorithm for
> >> >'displaced' (CL/Maclisp terminology) objects (i.e., objects with
> >> >headers) ??
> >>
> >> I don't know. What's the reference? If it is then why was the linked
> >> list introduced?
> >
> >Try ftp://ftp.netcom.com/pub/hb/hbaker/RealTimeGC.html (also .ps.Z).
> OK I just looked at that paper. That is a copying GC. The method I posted
> is a noncopying GC. No objects are moved. So it is not the same.

That's why I used the magic word 'headers'.  In many header/object systems,
the header doesn't move, and the object does, while in your system, the
header moves, but the object doesn't.

As the NoMotion paper points out, the key issues are the efficient
implementation of the colors and the sets.  The use of doubly linked
lists is merely illustrative of the basic idea.

Henry Baker
www/ftp directory: