[gclist] Re: gclist-digest V1 #74

[Matthew Fuchs]

Marc:

> 
> >From: giuliano@ix.netcom.com (Giuliano Carlini)
> >Date: Fri, 14 Jun 1996 08:29:57 -0700
> >Subject: Re: [gclist] Re: gclist-digest V1 #70
> 
> >Why is it cheaper to go forward? The local IRG is computed during the local GC
> >very cheaply.
> 
> I admit the local collector may compute the Inverse Reference Graph, which
> will bring the cost of a reverse search down.  However, remember that a
> standard tracing collector goes through any reachable object only once.
> Therefore it will not give you the complete IRG.  Ex:
> 
>         A ----> B --> C  ------> D
>                  \   /
>                   \ /
>                    X
>                   / \
>                  /   \
>         E ----> F --> G  ------> H
> 
> If the trace starts with A, it will tell you about  A->D and A->H, but not
> E->H and E->D.  Ladin and Liskov made a similar mistake in the first
> version of their protocol.
> 
> You might conceivably extend the trace to handle this case, but it will
> increase the cost (instead of being order of the number of reachable
> objects, it will be order of the number of reachable paths).
> 

Yes, and this may or may not be important, depending on how dense the
graph is.  I think you are generally overestimating the amount of
information actually required for the purposes of the algorithm.  I
can't speak to how anyone else does this, but scions A and E don't
need to actually know which stubs they point to, only which
distributed GC operations they may be involved in.  E doesn't need to
trace down to D and H if it can get this information from C and G.
Depending on your tradeoffs, this requires a minimum of a flag bit and
a maximum of a pointer.

> Also, as soon as the mutator changes something, your local IRG may become
> inconsistent with the reachability graph.  This may or may not be important
> depending on the details of the algorithm.
> 

We've already assumed that the stuff we're tracing is locally
unreachable, so the only changes to the graph must come from another
network node.

Matthew