Re: Memory used during GC

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.) And FIFO tracing is likely to exhibit
worse locality, at least in this case.

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.

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...
> >
> >  
> >
> 
> 
>