[gclist] Baker's treadmill improvments.
Thu, 30 Jan 1997 10:56:27 -0600
>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
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
A computer language without garbage collection
is like a city without garbage collection.