[gclist] object identity & copying collection

[David Chase]

>David Chase writes:
> > Copying collectors
> > impede certain compiler optimizations, for instance.

At 10:37 AM 12/15/97 +0100, Thomas Johnsson wrote:
>Which ones?

Any optimizations that assume pointer values do not change.
For instance, if I write something like this:

 
   int [] x = new int[1000];
   for (i = 0; i < x.length; i++) x[i] = i;

in Java, then I could generate better code on some
machines if I did not have to worry about the array "x" being
moved in a GC started in some other thread.  (Assume that the
length has been constant-propagated in, and that the checks
are out; there is at least one Java compiler not yet on the
market that does these optimizations already.)  There's more
examples in my dissertation, and more examples in the GC-safety
papers that Hans Boehm and I have worked on over the years.
Part of the problem is that it is not as easy as you might think
to detail all the things that go wrong; it's pretty easy to
say "reduction in strength, common subexpression elimination",
but then someone might not build a compiler exactly like
that -- they might put all their money on partial redundancy
elimination, or else they might do it some other way.  That's
part of the impediment.

It's also possible to generate tables telling the GC all about
which offset pointers and other addressing-temporaries to repair
when it moves a pointer, but I regard generation of those tables
as an impediment as well; Eliot Moss and his minions have worked
on this problem, and I recall that it was a bit of a pain.

Another approach, and a very nice one, is to use a Bartlett-style
conservative-copying collector; if the compiler obeys a minimal
contract (leave obvious pointers to objects still in use) then
it can create all the weird offset expressions it wants, and
those objects won't be moved, and hence the expressions remain
valid.

David Chase