[gclist] Compiler specialized GC's

[boehm.PARC@xerox.com]

"My impression is that no one GC scheme is optimal for all heap objects,
perhaps a smart compiler could derive and generate the right kind of hybrid
GC system that optimizes GC performance for a particular program."

There has been a reasonable amount of work on prediciting object lifetimes,
either using static compiler-based techniques, or profiling, or using the
execution history of the program itself.  The work by Tofte and Birkedal is one
example.  Much of the recent work on pointer aliasing (cf. POPL96 Proceedings)
can be used to obtain vaguely similar kinds of information.  I would argue that
static analysis tends to be better at predicting the kind of information that
allows you to explicitly discard objects at a certain point in the program;
profile-based information might be a better way to choose between gc or
allocation disciplines (cf. Barrett and Zorn, PLDI 93).

I don't know of any work that really chooses between GC algorithms based on
static analysis.  There are collectors that bypass the youngest generation for
certain objects, but I don't know if that counts.

"BTW Someone pointed me to a PLDI'92 paper by Diwan and Moss, that gives a
rough estimate for the cost of tracing roots in a precise copying GC system,
it's on the order of 1% of total GC time. Is this about the same order of
magnitued for conservative schemes?"

I don't have solid numbers.  I would guess that for stack tracing it's on the
same order, certainly for a single threaded environment.  If there are
statically allocated objects, then those clearly affect the number in both
cases.  Large statically allocated pointerfree regions tend to be a performance
problem for fully conservative collectors that scan those.  In the case of our
collector, it can be much cheaper to allocate those dynamically as pointerfree
objects  (or exclude them explicitly from the static root set, which happens to
be harder at the moment).

In general, it helps to inform a conservative collector of large pointerfree
regions of memory.  But in most systems that's easily done.  Conservative vs.
precise collection is not a binary choice; it's a nearly continuous engineering
tradeoff.

Hans

Standard disclaimer ...