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

[James McCartney]

At 7:31 AM -0800 1/30/97, Henry G. Baker wrote:
>> 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.

OK, I am "moving" the index in the header of the object (actually just
setting it to the index of its new location). The pointers that are swapped
are not in the header of the object but in a separate table.
This is slightly cheaper than doing the linked list operation. With the
linked list you have to update 6 pointers*, in the array swap you have to
swap 2 array locations and 2 indices. In addition you can save some space
by having a small index field and eliminating the color bits.

*(2 for the surrounding objects you are leaving,
  2 for the surrounding objects you are joining and
  2 in the object itself)


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