[Gc] gc with trie

Boehm, Hans hans.boehm at hp.com
Tue Nov 21 11:06:20 PST 2006

You seem to be asking several disjoint questions here? 

> -----Original Message-----
> From: gc-bounces at napali.hpl.hp.com 
> [mailto:gc-bounces at napali.hpl.hp.com] On Behalf Of skaller
> Sent: Monday, November 13, 2006 7:26 PM
> To: gc at napali.hpl.hp.com
> Subject: [Gc] gc with trie
> FYI I have some concern using gc since it seems to exclude 
> use of a digital trie.
You're talking about a trie that's indexed by addresses rather than
character strings.  That does cause issues if objects can move, as they
can with some other collectors.  The standard solution is to assign each
object a unique identifier as it's allocated, which is then used instead
of its address.  Or you use something like Java hashcodes, and deal with
the fact that multiple objects may have the same hashcode.
> One use is a system with an exact partial collector with 
> conservative gc running in background to reclaim unmanaged 
> store. (The application is a programming language with exact 
> collector which supports interfacing to C/C++ applications 
> which might themselves be collected with BRD-gc).
> I guess there is a way to organise this so it causes no 
> problems, for example the exact collector can allocate from 
> store provided by the BRD-conservative gc, which is told not 
> to scan but not collect that region?
> Any hints on how to organise this?
This is likely to be somewhat painful unless you have a priori
constraints on pointers between the two heaps.  The usual problem is
that cycles spanning the two heaps tend to leak, since the pieces in
each heap appear to be rooted in the other heap.  IIRC, Attardi et al's
CMM work addresses this, but I don't think it does good things to the
worst case running time of a GC cycle.

Allocating one heap as a block in the other heap is generally not
sufficient to deal correctly with cross-heap pointers.  Either
references from that block are not scanned, or all of them, including
those in free objects, are scanned.  If you really have to deal
correctly with cross-heap pointers, I expect that you need some
modification to the collectors.  If you're willing to let cycles leak,
it may be OK to treat this in the same way as most distributed
collectors, and use finalization facilities in each collector to notify
the other collector when a cross-heap reference disappears. 

If the whole system were under your control, I suspect it would be a lot
easier to use a single collector that can be type accurate but can deal
with ambiguities when necessary. 


More information about the Gc mailing list