[gclist] Baker's treadmill improvments.

Charles Fiterman cef@geodesic.com
Fri, 31 Jan 1997 09:37:10 -0600

>No its not right. Programs which are never idle can use the treadmill
>just fine. Its great for programs like mine which do need extreme
>incremental behaviour. Audio processing does not tolerate a delay.
>If an incremental GC does its work correctly it should not need to
>use idle time to catch up. Idle time should be used to service other
>The array implementation of the treadmill which I presented does not
>have the finalization problem he mentions because all free objects
>have an index >= the allocate index. Even the original algorithm
>doesn't have the color problem with finalization that he mentions because
>at the flip time it is easy to check the colors of objects which need
>finalization. All newly freed objects are white. Only objects which have
>been on the free list from previous cycles are multicolored.

I had a typo. My form has the free list, having this in one color
allows a debug check against pointers to the free list. 

If a finalizer stores a pointer to its object you now have a pointer to
a post finalized object. If finalizers are general, that is not in
some subset of the language then you can have post finalized objects
with pointers to them.

Its important that post finalized objects with pointers to them not be freed. 
In Java for example if you can create a reference to space the system thinks 
if free you can write a virus. So freeing post finalized objects with pointers 
to them would be a monster bug in the collector rendering the whole system 

If the treadmill is the right algorithm for your application than you
are right, forcing frees and finalization into idle time is wrong for you.
But maybe there is a simple work around where atoms of collection are 
associated with various mutator actions like allocation. You reach a steady 
state by having say three atoms of collection for every allocation. Maybe 
the number can be tuned at run time by some heuristic.
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.