Re: gc notes available

[Graham Hughes <ghughes@cs.ucsb.edu>]

>>>>> "Marius" == Marius Vollmer <mvo@zagadka.ping.de> writes:

    Marius> [ Graham, I'm CCing this to the Guile list because I think
    Marius> it is of general interest. ]

<nod>  I originally intended to CC the original message there and
screwed up the first time :)

<snip measurements>

    >>  Yes, but this overhead is two instructions compared to
    >> thousands.

    Marius> Yes, that makes the explicit `software' write barriers
    Marius> preferable, I think.  This is a good thing, because
    Marius> getting the needed support for `hardware' write barriers
    Marius> from the OS might be tricky (or not, I'm really not the
    Marius> right guy to discuss this topic).  When we can get by with
    Marius> software barriers, we should do so.

Definitely.

    Marius> Could you post more details how Urs has done the
    Marius> two-instruction trick?

Sure.  First, some background: when doing this sort of thing, shaving
one instruction off the write barrier, even if it means some extra
work on the GC side, saves you a lot of time.  So the two extra
instruction barrier isn't as precise as it could be, but that's OK
because it only needs to be really fast.

Urs uses a form of card marking, which basically means you take the
heap, divide it up into small chunks called cards and have a bit array
saying `this part of the heap has an intergenerational pointer
somewhere in it'.  Card size is quite variable; the _Opportunistic
Garbage Collector_ uses 32 32-bit words as its default card size.

At any rate, given this, and given that bit manipulation usually
requires several instructions on RISC processors, Urs uses a byte
array: you sacrifice a little space for some big performance benefits.

Let k be log_2 (card size).  If byte i in the byte table is marked,
then there exists a pointer somewhere in the cards i ... i+1; you need
to scan for this then.  Given all this, we can implement the write
barrier with this (SPARC):

	st [%obj + offset], %ptr
	sll %obj, k, %temp
	st %g0, [%byte_map + %temp]

There's a little fiddling that needs to be done, and it's detailed in
Jones & Lin (to a certain degree); the original paper is at

http://www.cs.ucsb.edu/oocsb/papers/write-barrier.html

Now, I don't know how much overhead is permissible in Guile: the above
paper is intended for advanced compilers where the savings of one
instruction is extremely important, so you may not have to go for
something this hairy.  It does provide a good baseline, though.
-- 
Graham Hughes <ghughes@cs.ucsb.edu>
PGP Fingerprint: 36 15 AD 83 6D 2F D8 DE  EC 87 86 8A A2 79 E7 E6