[Gc] Custom marking infrastructure

Boehm, Hans hans.boehm at hp.com
Thu Jul 27 10:45:09 PDT 2006

Your talking about a collector GCC's internal data structures?  I
haven't actually looked at what's there in a while, and I expect it has
changed, but ...

In general, this collector doesn't get along particularly well with
direct recursive mark procedures.  There are several reasons for that,
some of which probably don't really apply here:

1) They generate more memory traffic than an explicit mark stack, since
stack frames re likely to be significantly bigger than the mark stack
entries.  Hence, there seems to be some reason to believe they're
slower.  (Interpreting a bit map in the mark loop is quite fast.)  I
think others arrived at the same conclusion, though actual measurements
are probably dated at this point.

2) It's really tough to deal with mark stack overflow with direct
recursion.  This is probably less important in this context, but
historically it mattered.  And I suspect it still matters on handhelds
and the like, where gcc is rarely run.

3) In the incremental GC case, it seems to be even harder to deal with
partially constructed objects and the like.

As I recall, the GCC data structures have an explicit small tag in each
object?  It might be easiest to build a slightly custom version of the
collector that knows how to map those to the existing gc descriptors,
presumably by looking them up in a table?  That would make it slightly
harder to use the standard library, but I don't know how much of an
issue that is.

(I think it's "slightly harder" and not impossible since think the
collector needs support for multiple alternative mark loops anyway, so
that it can take advantage of things like model dependent X86 prefetch
instructions.  With that support, I think it should be possible to make
this customization dynamic at small cost.)

How many different object layouts are there?  Another alternative is to
map them all to different "kinds".

I might be barking up the wrong tree, since I'm not sure I understand
the goals of this project ...


> -----Original Message-----
> From: gc-bounces at napali.hpl.hp.com 
> [mailto:gc-bounces at napali.hpl.hp.com] On Behalf Of Laurynas Biveinis
> Sent: Thursday, July 27, 2006 5:39 AM
> To: gc at napali.hpl.hp.com
> Cc: Daniel Berlin
> Subject: [Gc] Custom marking infrastructure
> Hi,
> I'm trying to make use of existing GCC type information 
> infrastructure to provide exact marking for the collector. 
> But I'm not sure what's the best way to handle the impendance 
> mismatch between what GCC provides and collector expects.
> If I understand gc_mark.h correctly, I have to register new 
> "kind" of objects (in this case, all GC-allocated objects 
> would be of this new kind), free list for it, redirect all 
> allocations to this "kind" and provide custom marking 
> procedure that works of a mark stack and marks only a little 
> bit of heap on every invocation.
> Now the old GCC mark-and-sweep collectors do not operate on 
> explicit mark stack - they use program execution stack and 
> use automatically generated recursive marking routines for 
> that. So the problem is, how can I make use of those 
> recursive routines for custom marking procedure that operates 
> on explicit stack? For me the easiest way would be have a 
> callback that replaces the whole marking phase routine with 
> my own one (this is experimental code and I don't have to 
> worry about incremental collection, multi-threaded 
> environment etc.) If that's impossible, are there any other options?
> Thanks in advance and please CC on replies,
> --
> Laurynas
> _______________________________________________
> Gc mailing list
> Gc at linux.hpl.hp.com
> https://www.hpl.hp.com/hosted/linux/mail-archives/gc/

More information about the Gc mailing list