[gclist] Hardware assisted thread safe GC

Charles Fiterman cef@geodesic.com
Wed, 16 Apr 1997 09:00:29 -0500

Perkin Elmer used to make a multi processor which had
a special instruction for moving an object from one
doubly linked list to another. This operation was
guaranteed atomic. This instruction could also remove
an object from a queue and not put it on another.

If you had such an instruction or simulate one cheaply
the ideal collection algorithm for a system with lots
of processors and tasks becomes the Baker four color
algorithm. Any non busy processors can do garbage 
collection work in small increments. 

Blocking would be a problem in allocation but there
are ways to avoid most of that. For example the first
time a task asks for a 12 byte object get a page of
them, future requests by that task come from that page
without task blocking. Large allocations still create
task blocking.

If continuations are used for threads the hardware
assists for GC are hardware assists for generational
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.