[gclist] Baker's treadmill improvments.

[Charles Fiterman]

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

Agreed. In your paper on the four color algorithm I would have used the
word collection rather than doubly linked list and suggested that doubly
linked list was one appropriate implementation of collection.

Also the business of moving the white queue in mass to the free queue
looks really cool but is really a mistake. 

First applications that use the treadmill will be giving the collector 
atoms of time when they are idle. This more than fills the collectors 
needs for time and can be used to finalize and free objects instead of 
having that work done when a header is needed. Also having the white
queue contain objects with various color markings misses a good free
debug check.

The algorithm should say if there is nothing on the gray queue and 
something on the white queue, finalize the front object on the white queue 
and move it to the pink (finalized but not freed) queue if its still 
white. If the gray queue and the white queue are empty but the pink queue 
is not, free the front object of the pink queue. If gray, white and pink 
are empty move black to white and restart gray with the roots. The write 
barrier must be able to move objects from white or pink to gray. At end 
of job everything moves to gray and is then finalized one at a time.

Where releasing objects runs their finalizers there is a problem. A 
finalizer may store a pointer to its object. We can't prevent post 
finalized objects but we can prevent pointers to free objects. The
existence of post finalized objects and the fact that a finalizer
may require a pre finalized version of another object brings in
finalizer order. Finalizer order is purely in the semantics of the
mutator and cannot be deduced by the collector. Finalizer order is either
trivial or trivially impossible and in either case that's the mutator's
job. The mutator can provide an order number. Allowing this number to be 
set and read is sufficient, MAX_INT seems the correct default.
			-  
Charles Fiterman		Geodesic Systems
414 North Orleans Suite 410	Phone 312 832 1221 x223
Chicago IL 60610-4418		FAX   312 832 1230
				http://www.geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.