Re: Memory used during GC

> -----Original Message-----
> From: [email protected] [mailto:[email protected]]
> Sent: Tuesday, January 18, 2005 12:26 AM
> To: Boehm, Hans
> Cc: [email protected]
> Subject: RE: [gclist] Memory used during GC
> 
> 
> 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.
I agree.  In order to avoid pushing the spine of the list, you need
to arrange for the "next" field to get pushed first, so that it's
the last pointer to get followed.  If you are
implementing Scheme or Haskell, that's easy.  If there is
no built-in notion of list, that may not be practical.
> 
> 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 ?
That seems pretty standard.  We end up enqueuing
both r and its descriptor in visit(), since the
descriptor is much cheaper to get while you have access
to the mark bit.  And we try to do some prefetching.  (There's
an interesting paper about how to do that better at
ftp://ftp.cs.purdue.edu/pub/hosking/papers/asplos04.pdf .)
> > ...
> > 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. 
> 
I think we agree.  I was mostly concerned about embedded situations,
or in Knoppix-like environment, where the disk is likely to be
inaccessible.

Hans