Subject: Re: gc choice / design patterns
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 12 Oct 2002 20:38:03 -0500
Newsgroups: comp.lang.scheme
Message-ID: <3PidnfrqJ-LmUzWgXTWc3g@News.GigaNews.Com>
Jeffrey Siegal  <jbs@quiotix.com> wrote:
+---------------
| Rob Warnock wrote:
| > 	<URL:http://www.cs.ucsb.edu/labs/oocsb/papers/write-barrier.pdf>
| 
| As an aside, I'm not sure I agree with their basic assumption that using 
| bytes as marks is necessarily cheaper than using bits... today.
+---------------

Yes, a lot of those articles were written when most machines had only
byte parity (rather than ECC across 64 bits or more), and a byte-write
*was* faster than a bit-write. Note that byte-write is *still* faster
on a machine with *no* parity or ECC [which is, unfortunately, the vast
majority of desktops in the world today!! -- *sigh*]

But there's another, very important reason to use bytes (or maybe at
least nybbles) instead of bits: Byte marks can store the generation
number of the youngest generation pointed to from the card, so that
when doing a partial collection in a generational collector, if a
card's mark is higher than the highest generation currently being
collected, the card doesn't have to be scanned for roots at all
(since it can't possibly contain any).

In that case, storing a zero when crossing a write-barrier is just a
(mandatory) hint to the GC that the card must be scanned, and doesn't
necessarily say that the card contains pointers to gen-0 objects (and
thus roots for the current collection). That is, whenever a card is
scanned by the GC (because the mark is <= the highest gen. being
collected), the GC stores back into the mark the lowest generation-
pointed-to that it *actually* found, and if none of the scanned
pointers point to a generation being collected, the next GC of that
level (or less) will skip over the scanning of that card (unless
another store to that card occurs in the meantime, of course).

So IMHO byte-wide marks are still "a good thing"...


-Rob

-----
Rob Warnock, PP-ASEL-IA		<rpw3@rpw3.org>
627 26th Avenue			<URL:http://www.rpw3.org/>
San Mateo, CA 94403		(650)572-2607