Re: Memory used during GC

Quoting "Boehm, Hans" <[email protected]>:

> Both of those decisions seem to be very dependent on the application.
> 
> If your data structure looks like a somewhat balanced tree, allocated
> in something like depth-first order (e.g. a parse tree), LIFO tracing
> seems much better.  The maximal FIFO gray set size is the maximum
> size of a tree level, which, if the tree is really balanced, is
> on the same order as the number of nodes in the tree.  LIFO won't
> need more than the tree height.  (And if you do things in the right
> order, "next" fields in singly-linked lists don't count for the
> height computation.) 

I'm not sure I understand what you mean by the "right" order (Which probably
implies we don't do it this right order), but part of the rationale for
using FIFO was a linked structure such as:

   a -> a -> a -> a -> a -> ...
   |    |    |    |    |
   v    v    v    v    v
   O    O    O    O    O

where O's are potentionally complex objects, which, in turn, require
marking, etc..

Depending on the order in which one visits the next pointer and the
pointer to an object, LIFO required space proportional to the list size.
Admittedly, by defining the pointers appropriately, one could avoid this
behaviour, but we did not want users to have to deal with such low-level
idiosyncrasies to get acceptable performance. And I don't see a way for
our compiler to detect the optimal order in which these pointers should
be followed.

The process goes more or less as follows:

gc:
 for r in roots do:
   visit(r);
   flush;
   end;

visit(r):
  if (r is marked)
    return;
  mark(r);
  enqueue(r);

flush:
  while (queue not empty)
    r = dequeue;
    for v accessible from r do
      visit(v);

Have we been missing something important ?


> And FIFO tracing is likely to exhibit
> worse locality, at least in this case.

Yes. I guess you are right. 


> 
> Copying the queue/stack to disk seems like a good idea, but only if
> you can guarantee that there is a disk with available space.
> 

The orders of magnitude are such that this should not be a problem to us.
If a system running a process of over a GB of RAM cannot create
a file of a few megabytes, we might as well stop with an out of memory
error message. However, I fully agree that this technique does not 
apply universally. 

Cheers,

Darius.

> We use basically the same algorithm that Dave described, also with positive
> results.  (Our mark stack holds both references and descriptors for gray
> objects.)
> 
> Hans
> 
> > -----Original Message-----
> > From: [email protected] 
> > [mailto:[email protected]]On
> > Behalf Of Darius Blasband
> > Sent: Friday, January 14, 2005 2:47 AM
> > Cc: [email protected]
> > Subject: Re: [gclist] Memory used during GC
> > 
> > 
> > We rather use a queue than a stack - various experiments lead us to 
> > conclude that fewer cells
> > were required if grey objects were processed FIFO . When the 
> > queue fills 
> > up, we swap half
> > of it on disk, read back when the queue gets empty.
> > 
> > It is a bit brutal, but then again, this queue is size in such a way 
> > that only
> > the biggest systems require this disk access, up to a point where the 
> > performance penalty is
> > essantially irrelevant.
> > 
> > D.
> > 
> > David Detlefs - Sun Microsystems Labs BOS wrote:
> > 
> > >Calum --
> > >
> > >Another approach that we use in a couple of places in Sun collectors
> > >is to allocate a fixed size stack to hold references to grey objects.
> > >If this stack overflows, record that fact, and at the end of marking
> > >restart the marking process, traversing the heap to find marked
> > >objects, treating them as roots.  This process will eventually
> > >terminate.  With even quite small stacks relative to total heap size,
> > >you can make this overflow quite unlikely (for "reasonable" programs
> > >that don't have very long pointer chains.)
> > >
> > >Hope this is useful...
> > >
> > >  
> > >
> > 
> > 
> > 
> 
> 
>