[gclist] Root identity algorithms

Jim Haungs Jim.Haungs@oracle.com
Mon, 16 Apr 2001 15:06:26 -0700

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



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)
         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.