GC statistics (was Re: big project ported)

[Boehm, Hans]

Our collector does build free lists, but it does so incrementally at
allocation time.  A few more objects are put on the free list whenever it is
found to be empty in the allocator.  My guess is that this is slightly
faster than looking at bitmaps at each allocation, just because the
allocator needs to retrieve less global state.  It's cheaper to scan bitmaps
a page at a time.  But I have never actually done the experiment, and this
is probably very data-structure specific.  I expect that a purely
bit-map-based collector would also be very competitive. 

The arguments about copying collector complexity are mostly bogus.  The fact
that they are repeated so many times in the literature doesn't make them
true.  For more details see
http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html .

I don't believe that non-generational copying collectors make much sense
under most conditions.  The advantage of a copying collector is that it can
often make allocation of short-lived objects very cheap by more effectively
limiting the collection to recently allocated objects.  A copy-collected
area for young objects often does make sense for this reason.  (I don't know
if any of the high performance JVMs copy-collect old objects.  My impression
is "no".  They may use the "train" algorithm, but that has very different
performance characteristics from a traditional 2-space copying collector.
Also note that these collectors generally seem to be a bit slower than ours
for program phases that allocate mostly long-lived objects.)

I do have a very partial implementation of a copy-collected "nursery" for
our collector.  But my inclination at the moment is to put that off a while
longer.  Based on my measurements, I'm not completely convinced that its
potential benefit is worth the added complexity.

Our collector does currently clear objects before allocation if they are not
known to be completely pointer-free to the collector, and I believe they
never are for gcj.  My guess is that's a mistake for gcj, and the collector
should be fixed to accomodate gcj better.  (This is possible, though not
completely trivial.)  I'm not sure how big a performance cost it really is.
It does have the effect of making the GC look worse in profiles, since
initial cache misses for newly allocated objects (about to be allocated
objects, really) are all taken by the collector.

Hans  

-----Original Message-----
From: Jonathan P. Olson [ mailto:olson@mmsi.com ]
Sent: Wednesday, October 27, 1999 5:39 PM
To: Godmar Back; krab@daimi.au.dk
Cc: bryce@albatross.co.nz; jsturm@sigma6.com;
java-discuss@sourceware.cygnus.com
Subject: Re: GC statistics (was Re: big project ported)


On Wed, 27 Oct 1999, Godmar Back wrote:

>Other things that make Boehm's gc slower is the fact that it's
>noncopying; therefore, its sweep phase complexity is proportional
>to the amount of garbage found.  In other words, it has to spend
>time returned every garbaged object to the allocator one by one.
>
>	- Godmar
>-

In an embedded conservative collector, I do the sweep phase by merely
anding bits in allocation maps.  There's no work to do for each object
being freed, and each word written to the allocation maps can free
up to 32 objects.  In this collector, the mark phase dominates the
collection time, and the sweep phase is always constant.

--
Jon Olson, Modular Mining Systems
	   3289 E. Hemisphere Loop
	   Tucson, AZ 85706
olson@mmsi.com
Phone:	(520)746-9127
Fax:	(520)889-5790