[gclist] Thread safe GC

[Jim Larson]

In message <9704140924.ZM13104@hoh.mti.sgi.com> Hans Boehm writes:
>- for a massively parallel system, you want to allow more than one
>thread doin g useful GC work at the same time.  I don't know of too
>many implementations tha t support this.  (One of ours does, but only
>to a very small extent.)  I don't believe there are any fundamental
>problems here.  But I suspect it's hard to get the details right.

I wrote a mildly-parallel (up to 24-processor) parallel GC as part
of the runtime system for a committed-choice logic language (similar
to Mercury).  The details aren't too hard to get right - at least
no harder than any other part of a parallel runtime system - the
difficulty lies in getting good parallel speedups out of it.

We found that a huge problem was that many of the heaps we built
contained a lengthy 'spine' of live data which had to be scanned
sequentially.  Even though we had two dozen processors trying to
do GC work, all but one of them were idle after an initial flurry
of activity, and had to wait for a long, deep list to be traversed.

Any parallel code has to be tuned to eliminate bottlenecks or hot
spots, but parallel GC introduces a problem that's harder still.  The
programmer must find a way to let the parallel GC run, but cannot do so
by optimizing the GC code.  Instead, the programmer must create data
structures in such a way that the GC scanning can run in parallel.  So
the code to optimize in inaccessible and its data set is created
indirectly - and all the while the programmer has to make sure that
normal execution runs quickly too.

For this reason, most parallel GC'd systems tend to focus on having
good single-threaded concurrent collectors rather than
'stop-the-world' parallel collectors.

References to our research available upon request.

Jim Larson
James.S.Larson@jpl.nasa.gov