fork()

[Tim Peters]

[Andrew M. Kuchling]
> ...
> Perhaps lists and dictionaries could contain prev/next pointers that
> are used to maintain them in a doubly-linked list, and a linear-time
> traversal would be done to find unmarked objects, but there has to
> be a better way.

In this kind of approach, I doubt there's a substantially better way.  Guido
will also want a doubly-linked list (where the links don't count against the
refcount!) so that when a dict goes out of existence via the normal
refcount-hits-0 route, the dict can efficiently unlink itself from the list.

A worthwhile variation of the mark/sweep scheme you sketched is to move
objects into a new doubly-linked list *as* they're marked.  Then when the
mark phase ends, that new doubly-linked list is automatically the new list
of live dicts, and what remains in the old doubly-linked list is
automatically the list of cyclic dict trash.

At this point finalizers can still be run with everything intact, although
(as the Java folk keep saying) not particularly *usefully* in the absence of
a way for the user to force the order they're called in.

So, ignoring that, you make one pass over the trash list just to run
finalizers.

The next problem is resurrection:  running a finalizer can magically make
one or more trash items reachable again (e.g., "global somelist;
somelist.append(self)".  So at the end of the finalizer pass, you have no
idea what's still trash!

That's where variants of Graham's "two pass" come in.  If you're Java, you
mark each object whose finalizer has been run with a secret sticky "already
ran the finalizer" flag, and never run the finalizer on such an object again
even if it resurrects and becomes trash again a thousand times over.

Conceptually, you need to run the mark phase all over again to determine
what's still trash after finalization, and so on until you reach a steady
state.  In practice, you get clever instead.

The reward in the end is that you get something like the Java Spec's
(section 12.6.1) 8-state transition network for the possible paths of an
object thru the "is it trash yet?" space, and users figure the only way to
preserve their sanity in the face of this mess is to avoid finalizers
altogether <0.4 wink>.

resurrection-is-a-bitch-ly y'rs  - tim