[gclist] Prior work?

[Bryan O'Sullivan]

c> But this will change and change soon. Caches create heat and the
c> newest chips like the Itanium don't have caches they have smart
c> pipelines and multi processors. Since wires now dominate chip
c> surface and copper has replaced aluminum for wires, cache memory is
c> going to vanish in the near future. On a cacheless machine the
c> specialized scan function will obviously win.

Oh, my.  What you are saying here doesn't make the slightest bit of
sense, I'm afraid.  Cache memory is not going to vanish any time soon
(contrary to your assertion, Itanium has a three-level cache
hierarchy), and copper interconnects have nothing to do with the
problem.  "Smart pipelines" and "multiprocessors" have been around for
a long time, and they *increase* the need for effective caches.

Returning to our regular garbage collection diet: I worked for a short
while on the gc in the Glasgow Haskell Compiler (GHC).  Some of the
internals of GHC are loosely based on the idea of "taglessness".  For
example, instead of using a generic mark function to mark objects in
the heap based on its type tag, each object header instead used to
contain a pointer to its own custom marking and stack adjustment
thunk.

Take a function pointer for marking and add function pointers for
various other purposes (we're tagless, remember), and pretty soon all
of your objects start to look very large.  My memory is failing me,
but I think that we generated redundant mark functions for objects
that had "the same shape".  The result was large binaries, and an
impressive memory footprint.

I spent some time factoring out those chunks of object headers that
were needlessly replicated, and replaced each chunk with a pointer to
a single shared chunk.  This added a level of indirection to the
handling of some headers, but made a significant difference to memory
and binary footprints.  My recollection is that overall performance
was reduced by 1%, at a saving of about 30% in disk space and memory
usage at run time.

I wasn't at Glasgow for long enough to pay closer attention to the
performance of the gc, but I'd bet that if we had moved further away
from taglessness, we could have reduced our memory needs even further
and improved our performance by thrashing the cache less.  Using a
more modern processor implementation than our 1993-era Alphas might
have allowed us to use non-polluting loads for marking, which would
have been friendlier again to our caches.

	<b