Algorithm for finalizing cycles (Re: [Python-Dev] Garbage collecting closures)

Greg Ewing
Tue, 15 Apr 2003 13:41:15 +1200 (NZST)

> Why do I, as library developer, want the finalizer?  Because I don't
> want to rely on the application to keep track of when a file must be
> closed.
> But then why do I (still as library developer) recommend that the
> application closes files explicitly?  Because there's no guarantee
> *when* finalizers are run, and it's easy for the application to create
> a cycle unknowingly (as we've seen in Paul's case).

Okay, I think I see what you're saying. Finalizers are needed to make
sure that resources are *eventually* reclaimed, and if that's not good
enough for the application, it needs to make its own
arrangements. Fair enough.

What bothers me, though, is that even with finalizers, the library
writer *still* can't guarantee eventual reclamation.  The application
can unwittingly stuff it all up by creating cycles, and there's
nothing the library writer can do about it.

It seems to me that giving up on finalization altogether in the
presence of cycles is too harsh. In most cases, the cycle isn't
actually going to make any difference.  With a cycle of your
abovementioned file-descriptor-holding objects, for example, could be
finalized in an arbitrary order, because the *finalizers* don't depend
on any other objects in the cycle.

So maybe there should be some way of classifying the references held
by an object into those that are relied upon by its finalizer, and
those that aren't. The algorithm would then be to first go through and
clear all the references that *aren't* needed by finalizers, and

Actually, that's all you would need to do, I think.  If there is an
unambiguous order of finalization, that means there must be no cycles
amongst the references needed by finalizers. And if that's the case,
once you've cleared all the other references, normal ref counting will
take care of the rest and call their finalizers in the proper order.

If there's anything left after that, then you have a genuinely
difficult case and are entitled to give up!

Greg Ewing, Computer Science Dept, +--------------------------------------+
University of Canterbury,	   | A citizen of NewZealandCorp, a	  |
Christchurch, New Zealand	   | wholly-owned subsidiary of USA Inc.  |	   +--------------------------------------+