[gclist] Length of dependency chains

Hans Boehm boehm@hoh.mti.sgi.com
Thu, 17 Apr 1997 10:26:40 -0700

On Apr 17,  9:29am, Jerry Leichter wrote:

> This brings up an interesting point:  Just how long *are* typical dependency
> chains?  That is:  What is the expected length of the shortest path from a
> to a live element?  I suspect that, for most programming styles, not only is
> expected value quite small, but that the distribution is heavily skewed
> small values, with outliers being quite rare.

This is a very different question than the one for finalizable objects.  I
conjectured earlier that the number of finalizable objects on finalization
chains is typically 1 or 2.  That's certainly true for all the examples posted

For the other question, I have some limited anecdotal evidence that for Cedar
it's typically in the 5-50 range, i.e. small number of tens.  This is based on
playing with a backtracing tool that tried to find the chain backward to a root
from a randomly chosen heap object.  (This is actually a rather useful tool.)
 This tool basically performed a depth-first backward (very slow) search.


Hans-Juergen Boehm