# [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
*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