[Python-Dev] finalization again

nascheme@enme.ucalgary.ca nascheme@enme.ucalgary.ca
Thu, 9 Mar 2000 12:37:31 -0700

[Tim, explaining something I was thinking about more clearly than
I ever could]

>It's not obvious, but the SCCs can be found in linear time (via Tarjan's
>algorithm, which is simple but subtle;

Wow, it seems like it should be more expensive than that.  What
are the space requirements?  Also, does the simple algorithm you
used in Cyclops have a name?

>If there are no safe nodes without predecessors, GC is stuck,
>and for good reason: every object in the whole pile is reachable
>from an object with a finalizer, which could change the topology
>in near-arbitrary ways. The unsafe nodes without predecessors
>(and again, by #4, there must be at least one) are the heart of
>the problem, and this scheme identifies them precisely.

Exactly.  What is our policy on these unsafe nodes?  Guido seems
to feel that it is okay for the programmer to create them and
Python should have a way of collecting them.  Tim seems to feel
that the programmer should not create them in the first place.  I
agree with Tim.

If topological finalization is used, it is possible for the
programmer to design their classes so that this problem does not
happen.  This is explained on Hans Boehm's finalization web page.

If the programmer can or does not redesign their classes I don't
think it is unreasonable to leak memory.  We can link these
cycles to a global list of garbage or print a debugging message.
This is a large improvement over the current situation (ie.
leaking memory with no debugging even for cycles without


"If you're a great programmer, you make all the routines depend on each
other, so little mistakes can really hurt you." -- Bill Gates, ca. 1985.