[gclist] Instanteneous GC

[David Chase]

At 11:49 PM 7/28/99 -0400, Tim Sweeney 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).  Enforce a rule that every object always has at least one incoming
>reference from a lowered number object.  Whenever a reference changes that
>breaks this rule, move the offending object to the end of the list (make it
>the highest numbered object), and readjust the other objects--which may
>cause them to recursively fall to the bottom of the list.  In this process,
>some objects that land at the bottom of the list will have no upward
>references, and those objects have immediately become garbage.  The overhead
>of this is (on a 32 bit machine) 8 bytes per object + 24 bytes per reference
>variable.  This has a lot of O(n^2) performance cases, for example many
>double-linked list implementations, but I think the algorithm can be
>restructured to never be worse than O(n).  Still this is impractically slow.

It's worth considering, if you are willing to scratch your head and
hack the analysis for the data structures that you actually deal with,
but ...

>So, my question is: is there any reasonably efficient way to do
>instantaneous garbage collection, using a write-barrier function that can
>immediately determine that objects have become garbage?

A little neuron jumping up and down at the back of my brain says
"no".  I think this is equivalent to some "on-line" graph connectivity
problems, and all the results that I remember from gradual school
say that edge addition is relatively easy, but edge deletion is
a good deal harder.  This general rule has held for most of the
graph-related problems I have had reason to play with (transitive
closure, dominator trees, e.g.).  HOWEVER, you might be able to
exploit some of the usual GC heuristics regarding frequency of
modification versus frequency of initialization and access.

This is the article that was bugging that neuron.  It's 18 years
old, perhaps someone has made progress since then, but since I'm
vaguely interested in this sort of problem, there's some chance
I would have noticed.

@article{ES:OLEDP,
TITLE = "An On-Line Edge-Deletion Problem",
AUTHOR = "Shimon Even and Yossi Shiloach",
JOURNAL = jacm,  VOLUME = 28, NUMBER = 1, MONTH = jan, YEAR = 1981,
PAGES = {1--4}
}

jacm = Journal of the ACM

David Chase
NaturalBridge