GC performance - was Re: [gclist] GC topics

[boehm.PARC@xerox.com]

Some comments on performance issues raised here.

1) Numbers like "5% GC overhead" are completely meaningless, given that you can
always trade off space for performance.  Our collector often runs faster if you
keep more live data around.  Why?  The heap expansion heuristic tries to keep
the GC overhead per byte allocated constant.  If there is more live data it
grows the heap.  Occasionally it overshoots a little.  Our collector tries to
keep the heap size at around 1.4 times the live data size.  I've heard of other
collectors that aimed for something like a factor of 7.

2) The cost of a garbage collecting allocation is roughly proportional to the
size of the allocation, since that's what determines GC frequency.  The cost of
malloc is typically constant.  Thus garbage coillectors probably lose for large
objects.  Some of the performance numbers here refer to Lisp-like programs with
an average allocation size of around 8 bytes.  One of the Detlefs-Dosser-Zorn
benchmarks has an average allocation size of 752 bytes.  The numbers are not
remotely comparable.

And on conservative collection specifically:

3) Manuel Serrano's Bigloo scheme implementation uses our conservative
collector.  Based on numbers I've seen from him, it performs as well as other
good Scheme implementations.  (This clearly has more to do with his compiler
than the collector.  But the collector doesn't seem to be a major obstacle.)
Based on a recent conversation with him, the collector does seem to hurt
significantly for a few ML benchmarks with very high allocation rates and no
updates.  This seems to be less of a problem for standard Scheme benchmarks.

4) Our conservative collector does support 2 generations.  But young objects
cannot be allocated completely contiguously.  This is the main reason it loses
in the presence of very high allocation rates and infrequent updates.

5) "Precise" garbage collectors clearly do have an advantage in predictability.
However it is rare for language implementations to document the performance
characteristics sufficiently that the programmer can take advantage of that.

6) It is often not appreciably more expensive to scan a region of memory
conservatively than it is to scan it precisely with exact type information.
It's probably cheaper than generating type specific traversal procedures
naively.  (It's easy to try some of this with our collector, since it actually
supports client provided type information.  But nobody bothers to supply it, as
far as I know.)  I claim it is typically cheaper to scan it conservatively than
to copy it precisely, possibly much cheaper.  There is a performance advantage
to the collector in knowing that all non-nil pointers point to the heap.  But
that often incurs other costs to the client code.

7) The performance of our collector can often be drastically improved with
minor tuning.  I've seen this for some other systems.  It's probably true for
the Detlefs-Dosser-Zorn benchmarks, though I don't think anyone has tried that.
For code written for malloc/free, it can be particularly important to remove
some allocation "optimizations", which can turn into gross pessimizations.

8) Based on my experience at doing both, it is much easier to use a
conservative collector in a language implementation, even when a precise
collector is possible.  And for a while at least, the result is likely to be
much more reliable.  There are two reasons for this.  The compiler/collector
interface is much simpler, hence you have a much better chance of using an
off-the-shelf collector.  Second, for a realistic implementation which allows
access to OS primitives, etc. it's often very hard to get the hand-written glue
code in the run-time system to preserve the GC invariants correctly.  A minor
mistake results in a subtle bug that may not be discovered for a long time.
The same comments apply to calls of user-written C code, at least if it's
allowed to munge garbage-collected data structures.

Hans

Standard disclaimer ...