[gclist] Page grouping trick

Pekka P. Pirinen pekka@harlequin.co.uk
Fri, 18 May 2001 19:48:55 +0100


> Francois-Rene Rideau <fare@tunes.org> wrote:
>> Just think about it: if an object might be moved without the address
>> change having been universally propagated, then you're forced to check
>> whether the object has moved or not. Hence, a read barrier, either
>> by conditional forward pointer checking or by inconditional indirection.
>
> Yes, exactly.

You can also use a write barrier, with a replicating collector, see
<http://www.xanalys.com/software_tools/mm/glossary/r.html#replicating
.garbage.collector>.

I think hybrid schemes are also possible, but I don't want to try to
wrap my head around that on a Friday evening.

>> Inconditional vs conditional indirection is a matter of tradeoff
>> between stressing the memory subsystem and loading the CPU;
>> at times when the CPU is much faster than RAM,
>> conditional indirection might be interesting again.
>
> Does anyone know of a useful paper discussing the trade-offs ?
> I've been working through the literature, but as I'm sure you all
> know, it's pretty extensive ;)

The best review is, as usual, in _Jones and Lins_ <http://www.cs.ukc.
ac.uk/people/staff/rej/gcbook/gcbook.html>.

The Appel-Ellis-Li read barrier <http://www.xanalys.com/software_tool
s/mm/bib/f.html#ael88> is quite practical.  Using hardware page
protection means that the overhead on object addressing is only a few
page faults over the whole collection.  YMMV, but it has worked well
in real systems, including Functional Developer (ex Harlequin Dylan).
-- 
Pekka P. Pirinen, Harlequin Limited
Real programs don't eat cache.