[gclist] Re: gclist-digest V1 #68

[Matthew Fuchs]

Arturo:

> 
> >I should also point out that the algorithm I presented in my paper
> >went beyond just a depth-first search to mark each node touched as
> >either alive or garbage, unlike a pure DFS which only proves if the
> >initiating node is alive or dead.  That also cuts down the number of
> >times the algorithm is run, and provides lots of interesting
> >information that could be used for other heuristics.
> 
> Yes, but your algorithm was expensive in the number of messages sent and 
> it still had to go back to the initial node to determine when the 
> coloring was done, and then it has to propagate terminate messages, which 
> by all effects is not too different from an effective dfs, the biggest 
> advantage that your algorithm provides is the fact that it cleans up all 
> garbage, not just cycles which leaves plenty of room for optimisation 
> there.
> 

If you look carefully, you'll see that terminate messages are only
actually necessary when there cycles, and are at most one per node.
If we are only looking at garbage, it actually has less messages per
node, because the simple DFS algorithm can have redundant runs with no
upper limit on the number of times garbage is traced, whereas my
algorithm traces garbage only once and collects it with the same
number of messages (since the terminate message causes the node to be
collected).  There are more messages only if there are live nodes and
even then, only where there are live cycles - not all live nodes need
to receive terminate messages - so the number of extra messages per
operation is _at most_ one per edge, but on average will be much less,
and as I mentioned in my letter, that can be kept very low.  So I
would not agree that my algorithm is expensive in the number of
messages - in practice it would be less expensive.

Matthew
matt@wdi.disney.com
http://galt.cs.nyu.edu/students/fuchs