GC statistics (was Re: big project ported)

[Godmar Back]

> 
> Bryce McKinlay <bryce@albatross.co.nz> writes:
> 
> > After a few very un-scientific tests I am inclined to agree with your conclusion
> > that gc is the major source of performance problems in libgcj. 
> 
> [Perhaps this is one for the FAQ]
> 
> This is part of the price paid for the convenience of CNI and the
> general gcc backend.  It's a tradeoff for cost-of-development versus
> speed. 
> 
> These performance issues to be expected from a conservative collector,
> such as the boehm system.  An exact collector, which knows exactly
> which registers and memory locations are pointers to objects, can do a
> much better job because it only needs to scan live objects.  A
> conservative collector on the other hand needs to visit all objects in
> every gc cycle -- both the ones that are live and the ones that are
> garbage.  Experiments show that most objects turn out to be garbage
> after a single gc-cycle, so the problem is inevitable.
> 

Kersten,

A conservative collector does not need to scan all objects during every
gc cycle.  It only scans those that it finds reachable from a set of
root addresses.

The difference between a conservative and a precise collector is how
this root set is determined: a precise collector determines it precisely,
a conservative collector may conservatively include addresses that refer
to objects that are essentially garbage.  However, this amount of so-called
floating garbage is usually small and it's probably not the primary cost
of conservative gc (or so the common wisdom goes.)

What does make a conservative collector slower is the fact that it has
to spend time determining whether a given address does or does not point
to an allocated object (see ptr_chck.c in Boehm's).  [Somebody mentioned 
that libgcj has boehm scan its data segment for pointers in addition 
to the thread stacks.]

Because Boehm was designed for languages such as C, where there is
almost no type information, he decided to make the process of determining
whether an address is a pointer or not fast.  He did so by allocating
objects in a matrix raster that allows him to perform address arithmetic
for this purpose.  On the flipside, this makes the allocator slower:
objects have to be kept in a freelist instead of being able to allocate
memory from a contiguous region.

Interestingly, other VMs (latte & SRCJava) has implemented a different
scheme of allocation: they implement fast allocation from small contiguous
region, yet still allow for conservative collection.

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
-