[gclist] Hughes' algorithm

[Marc Shapiro]

 || From: wilson@cs.utexas.edu (Paul R. Wilson)
 || Date: Fri, 15 Mar 1996 02:16:43 -0600
 || 
 || Does anybody out there really understand Hughes' algorithm?

I think I understand the idea, but I certainly don't understand all the
details of the paper...

 || My basic conception of Hughes' algorithm is that really it's a global
 || incremental tracing algorithm, where you can have multiple traces going on
 || at the same time.  If this is the right intuition, I don't see how it can
 || work correctly, due to termination detection problems.
 || 
 || Here's the minus-one'th order version, as I see it.  [...]  First
 || question: is this even roughly right?

Yes!

Conceptually there are many traces occuring in parallel, but at one process a
single trace thread runs periodically.  I.e. multiple traces do not overlap at
any single process.

 || Second question: is the trace a snapshot trace, or an incremental update
 || trace?

I don't think the paper says anything about this, and I don't see why the
question is relevant.

 ||   If we're propagating a mark (say, 4) and we come to an object that's
 ||   marked with a lower mark, we just clobber the lower mark with the
 ||   higher one and spread the higher one (only) from there.

Conversely, if you are propagating mark 3 and get to an object marked 4, you
can stop tracing 3.

 || I don't see how you can ever detect termination.  For example, there may
 || be no unpropagated 3 marks left in the system, but if there are 4 marks or
 || 5 marks, you can't tell whether GC 3 has actually terminated or
 || not---since 4 marks or 5 marks can clobber 3 marks, it may be that there
 || are things that were reachable for GC 3 _and_still_are_, but the 3 marks
 || have been hidden by clobbering them with 4's and 5's.

If a 3 mark has been clobbered by a 5, that means that the object was still
reachable at timestamp 5.  When the global minimum reaches 3, 4 or 5 the
object will not be collected, which is safe.  If you detect termination and
reach a global minimum for 5, you don't need to worry about 3 any more.

Also, a process traces its roots in decreasing timestamp order.  So, you first
trace from mark 5, then from mark 4, then 3, etc.  This ensures that each
object is marked with the maximum possible timestamp.

I think this answers your question.

                                                Marc