[gclist] Length of dependency chains

[Hans Boehm]

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
root
> to a live element?  I suspect that, for most programming styles, not only is
the
> expected value quite small, but that the distribution is heavily skewed
toward
> 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
here.

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

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com