[gclist] Length of dependency chains
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.