[gclist] Instanteneous GC
Joshua W. Burton
Thu, 29 Jul 1999 15:32:42 -0500
At 03:53 PM 7/29/99 -0400, you wrote:
> 2. Faster implementation: Assign each object a positive number,
> starting with 0 at the root. For each object, maintain for lists
> of references: (incoming, outgoing) x (to lower numbered objects,
> to higher numbered objects).
I assume others have noticed that this is strongly analogous to
tracking what various people (depending on their hobbies) refer to
as the Erd:os number, the Marilyn Monroe number, the Kasparov
number, or the Kevin Bacon number of everyone in a population.
So long as you know the Monroe numbers of all your old flames, and
keep your little black book organized (incoming references, in an
ordered list), you can always update your own Monroe number in
constant time. The problem, it seems to me, is that _everyone_
downstream from you (outgoing references, recursively) has to be
informed of the new topology, to keep their own lists ordered.
The Centers for Disease Control have devoted a lot of effort to
this problem, in various guises, and have concluded that it's hard,
at least for liveness graphs of high connectivity. In the worst
case, where most of the objects are in One Big Tangled Graph, you
have to phone _everybody_ thousands of times, and it would be
cheaper to just start over from Marilyn each time someone dies.
%% "What we have here is a failure to deallocate." - Cool Hand Leak %%
Joshua W. Burton <email@example.com> 414 N Orleans #410, Chi 60610
Geodesic Systems, Inc. +1 312 832 1221 x2033 (voice)
Software Engineer & Physicist at Large +1 312 832 1230 (fax/data)