[gclist] Instanteneous GC

[Joshua W. Burton]

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 <jwb@geodesic.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)