This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
>>>>> "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