[gclist] Page grouping trick

Francois-Rene Rideau Francois-Rene Rideau <fare@tunes.org>
Thu, 17 May 2001 23:52:47 +0200

I remember proposing this "one object per virtual address page" trick
as a way to get a precise hardware write (or read) barriers.
However, problems of small TLB size limits the applicability of the system
as compared to software write (or read) barriers.
Maybe limit the trick to older generation writeable objects, in a system
where most objects are write-once? Even then, the payoff seems small.

> Maybe I should ask a more basic question: there is a fundamental clash
> between fast object addressing and a moving collector.
There is a clash if you add some constraint of incrementality.
A stop-the-world and move collector works great and has fast addressing.

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.

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.

To avoid the read barrier, you may (like OCAML, IIRC)
limit the use of stop&copy to the newest generation,
so that any address changes will have been propagated
(hopefully) without the pause being too long,
and use a non-moving collector for older generations.

Another completely different trick is to use some kind or another
of linear graph reduction (see Alan Bawden's thesis), so that
you always have back-pointers that you can update in real-time,
when you move things around.

Of course, optimizing a read or write barrier away from tight loops
is tricky enough in presence of timesharing,
and even more so in presence of parallel processing.

Someday I'll have to write that metaprogramming system to allow
for seamless test of various combinations of implementation techniques
without costly and error-prone human meddling,
and have it semi-automatically determine the best GC for an application.

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[  TUNES project for a Free Reflective Computing System  | http://tunes.org  ]
"I'm not a procrastinator, I'm temporally challenged"