[gclist] Root identity algorithms

[Jim Haungs]

Bob asked me to forward his response to the GC list, as his email has
changed.

Jim

-----------------

Wouldn't it be O(n * m) in time (n=number of objects, m=number of roots) and
O(n + m^2) in space to do the following:

Make an array of hashtables t[m], and an array of integers s[m,m].
(Actually, s can be triangular).

For root i,
  For each object o reachable from i,
     for each root j < i,
       if o is in t[j]
         s[i, j] += sizeof(o)
       else
         s[i, i] += sizeof(o)
         enter o in t[i]

This then gives you not only the sizes per root, but also the pair-wise info
on which roots share ownership, so with O(m) arithmetic, you can reassign
ownership, or subtract out all shared objects, etc for any one root. O(m^2)
to do it for all roots.

If you make s uni-dimensional, you lose the ability to analyze what root is
truely responsible for what, and can get O(n + m) in space. You're left with
shared space being arbitrarily assigned to one of the roots.

This assumes that traversal itself is O(n), which it should be if accessing
the children is O(1) and you eliminate duplicates by checking t.

This should give you what you want, so long as m << n, but if m approaches
n, I think the problem inherently approaches O(n^2). But I have no proof.

-----Original Message-----
From: Jim Haungs [mailto:Jim.Haungs@oracle.com]
Sent: Saturday, April 14, 2001 11:36 PM
To: gclist@iecc.com
Subject: [gclist] Root identity algorithms


Can anyone point me to some papers describing algorithms that maintain root
identity for each reachable object?

I'm trying to determine if there's an O(N) algorithm for profiling the
cumulative size of objects reachable from other objects, but without
double-counting when they're reachable from multiple roots.

I searched the gclist archive but didn't come up with anything.