[gclist] Re: gclist-digest V1 #68

[Giuliano Carlini]

Marc,

Thank you for your response. I believe that most of your points indicate problems 
in my presentation rather than flaws in the algorithm.

>Sorry to disappoint you, but I've seen this before, lots of times.  Can't
>give you a reference though.

I just found out about Matt Fuchs work. Are there any others?

>You've added a number of nice features though.

Since I'm just caching up on what has already been done, could you tell me what 
features of what I propose are improvements over the prior works? Are they 
significant enough to publish? It would be a kick to get something published. 

>
> || 	- It should be relatively efficient. It should be O(n) where n is
> || 		the size of a cycle.
>
>If there are n zombies, and the average number of objects reachable from a zombie
>is m, the cost is O(n*m).

I wasn't very clear. I meant O(n) where n is the number of edges in the 
distributed object graph. But, what is important is that it has the same order of 
complexity as local collection. Whether it is O(n) edges or O(n*m) nodes. Of 
course, the difference in the constant of proportionality is rather large between 
the two.

>
> || When a stub is no longer reclaimed by the local collector, it sends a
> || delete message to its scion.
>
>This does not tolerate lost messages.  Instead, each space periodically sends
>the list of scions reachable from its own stubs, to every other space; any

I think this is handled under my scheme, and I assume Matt's inverse reference 
tracing, without requiring spaces to periodically anounce the stubs they still
hold. If a delete message is lost, the scion is retained. Eventually though,
the scion's space will notice that the scion has not been mentioned in an RPC,
and will consider the scion's target a zombie. In this case it will start a
back-search. The search will get back to the stub's space, where it is known
that the stub has been deleted. This will be sent back to the scion's space,
and the scion will be deleted.

If lost messages are rare, and I believe they are, this should be more efficient 
than repeatedly publicizing the stubs which are still live.

> || A zombie is: Locally unreachable.  The target of at least one scion.  Not
> || recently mentioned by an RPC.
>
>You only need to consider scions for zombies.  (A locally unreachable object is
>garbage anyway unless it is reachable from a scion.)

I was trying to optimize the case where several scion's exist for the same target.

>Why search *backwards*?  You get the same amount of information by going
>forwards:

I considered this. But, going backward's allows you to also collect acyclic 
garbage. There is therefore less wasted work.

>Following pointers backwards can be done, but it costs orders of magnitude
>more costly than forwards.

Why? It seems that the dominate cost is sending messages between spaces, and that 
is the same forward or backwards. Even if this were not true, the work still seems 
roughly the same. If we go backwards, we must compute for each stub, the scion's 
which can reach it. If we go forwards, we must compute for each scion, the stub's 
it can reach.

>
> || Only two requirements are imposed on [the local collector] by the
> || distributed collector. First, it must clear the remotely visible mark bit
> || of the objects it retains.
>
>More precisely: the local collector first marks or copies from local roots,
>setting the RV bit OFF; then from the scions, setting the RV bit ON.  Since
>it never marks the same object twice, the RV bits are correct.

I must be dense. I don't see the distinction between what we said.

>
> || If a back search cycles back to a zombie, then the zombie is not live
> || along that path.
>
>Careful here!  If the mutator is running concurrently, then this sentence is
>incorrect!

Once again, my presentation needs improvement. I wanted to explain the essence of 
the algorithm before handling the complexity introduced by race conditions.

> || Whenever a stub has been scanned, the space is notified that new scions
> || should be marked dirty. If the dirty scion is the first for the target,
>
>This bit is confusing. "Whenever a stub has been scanned" is the same as "all
>the time" since stubs are being scanned continuously.

Once again my presentation is lacking. Whenever a stub has been scanned by a 
back-search. Not by the local GC or the RV scanner.

>"If the dirty scion is
>the first for the target...": how can it not be, if there is a 1-to-1
>correspondence between stubs and scions?

While stubs and scion's are 1-1, scions and targets are 1 to many.

           Space A              Space B
        ------------          -----------
            ObjA1                ObjB1
              |                    |
              V                    V
            StubC1a-c          StubC1b-c
              |                    |
              |                    |
              |                    |
              |      Space C       |
              V    -----------     V
           ScionC1a-c          ScionC1b-c
              \_________  _________/
                        | |
                        V V
                       ObjC1

>
>How about trying a figure?  It's very hard to read through all the details of
>your text.  I know figures are difficult to draw with ASCII but it can be
>done...

Good idea. I'll try to add some. If ascii fails, perhaps I can add some uuencoded 
postscript.

Thanks,

g