Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.object
Subject: Re: C++ and garbage collection
Message-ID: <966@exodus.Eng.Sun.COM>
Date: 26 Sep 90 21:45:14 GMT
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 88

One thing I haven't noticed yet is mention of transformations applied
to pointers by an optimizing compiler.  I've also got some experience
using the Boehm-Weiser collector, both in "conservative" mode
(ignoring interior pointers) and in "hyper-conservative" mode
(treating interior pointers as pointers).


INTERIOR POINTERS

Treating interior pointers as pointers is not a trivial matter.  In
one application (a Modula-3 compile server) the collector failed to
reclaim large amounts of storage.  This required changes to the
program to manually recycle certain pieces of storage.


OPTIMIZATION AND THE COLLECTOR

If your C++ "compiler" is just a translator to C (or a compiler
written in ignorance of the needs of a garbage collector) then there
is no guarantee at all that the compiler will maintain pointers in the
format required by the collector.  I'll provide some contrived
examples:
    
    char * x;

    for (i = A; i < B; i++)
       {
        ... x[i + C] ... /* C is constant in the loop */
       }
    /* No subsequent uses of x */

It is quite likely that the expression "&(x[C])" could be
recognized as loop invariant and hoisted out of the loop.
There is no guarantee that C is greater than zero, and none is
necessary since the language only requires that "i + C" be a valid
index for the array.


Edelson doesn't rely on conservative pointer location; instead, he
links pointer roots together in lists to aid in location.  This avoids
the problems with conservative collection, but may not work correctly
in (say) a multi-threaded system on a machine with instruction
scheduling in the compiler (e.g., MIPS, Sun, IBM RS/6000), and
preemptive scheduling in the OS (e.g., Mach).  The example goes
something like this:

   int f()
   {
      R_t x;      /* Really
                     x.ptr = NULL;
                     x.link = head.root_list;
                     head.root_list = & x;
                   */
      register int y;
      ...
      y = x -> m; /* Really overloads and inlines into "x.ptr -> m" */
      x = NULL;   /* Really "x.ptr = NULL */

     return  y;
     /* Implicitly, head.root_list = x.link at procedure exit. */
   }

It may not improve the speed of the program (but it might) to first
form the address of "x.ptr -> m" (in a temporary, "t"), then assign
NULL to x.ptr, and then dereference "t" to get the value for "y".  "X"
is local, and not declared volatile, and contains no integers, so a
compiler might reasonably assume that it is safe to reorder the
assignment to "x.ptr" and the load from the "t".  However, if this
thread is suspended after the assignment, but before the load, then
the garbage collector could erronously recycle the memory referenced
by "x".


Now, I haven't gone to the trouble of trying to provoke a compiler
into doing this, but most RISC optimizers fool around with their
instruction schedules, and super-scalar machines often benefit by
getting some separation between their memory operations; it seems to
me that there is some burden on the proponents of garbage collection
in C++ to demonstrate (dare I say, "prove"?) that their collector will
work with a gc-ignorant optimizing compiler, or else I must charge to
the collector the time wasted by running unoptimized code.  Of course,
this needs to be reproved with each new release of the compiler.

In the short term, many of these problems can be solved by the use of
"volatile", though that won't help my program's speed much either.

David Chase
Sun Microsystems