[Python-Dev] finalization again

[Tim Peters]

[Guido, with some implementation details and nice examples]

Normally I'd eat this up -- today I'm gasping for air trying to stay afloat.
I'll have to settle for sketching the high-level approach I've had in the
back of my mind.  I start with the pile of incestuous stuff Toby/Neil
discovered have no external references.  It consists of dead cycles, and
perhaps also non-cycles reachable only from dead cycles.

1. The "points to" relation on this pile defines a graph G.

2. From any graph G, we can derive a related graph G' consisting of the
maximal strongly connected components (SCCs) of G.  Each (super)node of G'
is an SCC of G, where (super)node A' of G' points to (super)node B' of G'
iff there exists a node A in A' that points to (wrt G) some node B in B'.
It's not obvious, but the SCCs can be found in linear time (via Tarjan's
algorithm, which is simple but subtle; Cyclops.py uses a much dumber
brute-force approach, which is nevertheless perfectly adequate in the
absence of massively large cycles -- premature optimization is the root etc
<0.5 wink>).

3. G' is necessarily a DAG.  For if distinct A' and B' are both reachable
from each other in G', then every pair of A in A' and B in B' are reachable
from each other in G, contradicting that A' and B' are distinct maximal SCCs
(that is, the union of A' and B' is also an SCC).

4. The point to all this:  Every DAG can be topsorted.  Start with the nodes
of G' without predecessors.  There must be at least one, because G' is a
DAG.

5. For every node A' in G' without predecessors (wrt G'), it either does or
does not contain an object with a potentially dangerous finalizer.  If it
does not, let's call it a safe node.  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.

6. Else there is a safe node A'.  For each A in A', reclaim it, following
the normal refcount rules (or in an implementation w/o RC, by following a
topsort of "points to" in the original G).  This *may* cause reclamation of
an object X with a finalizer outside of A'.  But doing so cannot cause
resurrection of anything in A' (X is reachable from A' else cleaning up A'
couldn't have affected X, and if anything in A' were also reachable from X,
X would have been in A' to begin with (SCC!), contradicting that A' is
safe).  So the objects in A' can get reclaimed without difficulty.

7. The simplest thing to do now is just stop:  rebuild it from scratch the
next time the scheme is invoked.  If it was *possible* to make progress
without guessing, we did; and if it was impossible, we identified the
precise SCC(s) that stopped us.  Anything beyond that is optimization <0.6
wink>.

Seems the most valuable optimization would be to keep track of whether an
object with a finalizer gets reclaimed in step 6 (so long as that doesn't
happen, the mutations that can occur to the structure of G' seem nicely
behaved enough that it should be possible to loop back to step #5 without
crushing pain).


On to Guido's msg:

[Guido]
> When we have a pile of garbage, we don't know whether it's all
> connected or whether it's lots of little cycles.  So if we find
> [objects with -- I'm going to omit this] finalizers, we have to put
> those on a third list and put everything reachable from them on that
> list as well (the algorithm I described before).

SCC determination gives precise answers to all that.

> What's left on the first list then consists of finalizer-free garbage.
> We dispose of this garbage by clearing dicts and lists.  Hopefully
> this makes the refcount of some of the finalizers go to zero -- those
> are finalized in the normal way.

In Python it's even possible for a finalizer to *install* a __del__ method
that didn't previously exist, into the class of one of the objects on your
"first list".  The scheme above is meant to be bulletproof in the face of
abuses even I can't conceive of <wink>.

More mundanely, clearing an item on your first list can cause a chain of
events that runs a finalizer, which in turn can resurrect one of the objects
on your first list (and so it should *not* get reclaimed).  Without doing
the SCC bit, I don't think you can out-think that (the reasoning above
showed that the finalizer can't resurrect something in the *same* SCC as the
object that started it all, but that argument cannot be extended to objects
in other safe SCCs:  they're vulnerable).

> And now we have to deal with the inevitable: finalizers that are part
> of cycles.  It makes sense to reduce the graph of objects to a graph
> of finalizers only.  Example:
>
>   A <=> b -> C <=> d
>
> A and C have finalizers.  C is part of a cycle (C-d) that contains no
> other finalizers, but C is also reachable from A.  A is part of a
> cycle (A-b) that keeps it alive.  The interesting thing here is that
> if we only look at the finalizers, there are no cycles!

The scheme above derives G':

    A' -> C'

where A' consists of the A<=>b cycle and C' the C<=>d cycle.  That there are
no cycles in G' isn't surprising, it's just the natural consequence of doing
the natural analysis <wink>.  The scheme above refuses to do anything here,
because the only node in G' without a predecessor (namely A') isn't "safe".

> If we reduce the graph to only finalizers (setting aside for now the
> problem of how to do that -- we may need to allocate more memory to
> hold the reduced greaph), we get:
>
>   A -> C

You should really have self-loops on both A and C, right? (because A is
reachable from itself via chasing pointers; ditto for C)

> We can now finalize A (even though its refcount is nonzero!).  And
> that's really all we can do!  A could break its own cycle, thereby
> disposing of itself and b.  It could also break C's cycle, disposing
> of C and d.  It could do nothing.  Or it could resurrect A, thereby
> resurrecting all of A, b, C, and d.
>
> This leads to (there's that weird echo again :-) Boehm's solution:
> Call A's finalizer and leave the rest to the next time the garbage
> collection runs.

This time the echo came back distorted <wink>:

   [Boehm]
   Cycles involving one or more finalizable objects are never finalized.

A<=>b is "a cycle involving one or more finalizable objects", so he won't
touch it.  The scheme at the top doesn't either.  If you handed him your
*derived* graph (but also without the self-loops), he would; me too.  KISS!

> Note that we're now calling finalizers on objects with a non-zero
> refcount.

I don't know why you want to do this.  As the next several paragraphs
confirm, it creates real headaches for the implementation, and I'm unclear
on what it buys in return.  Is "we'll do something by magic for cycles with
no more than one finalizer" a major gain for the user over "we'll do
something by magic for cycles with no finalizer"?  0, 1 and infinity *are*
the only interesting numbers <wink>, but the difference between 0 and 1
*here* doesn't seem to me worth signing up for any pain at all.

> At some point (probably as a result of finalizing A) its
> refcount will go to zero.  We should not finalize it again -- this
> would serve no purpose.

I don't believe BDW (or the scheme at the top) has this problem (simply
because the only way to run finalizer in a cycle under them is for the user
to break the cycle explicitly -- so if an object's finalizer gets run, the
user caused it directly, and so can never claim surprise).

>  Possible solution:
>
>   INCREF(A);
>   A->__del__();
>   if (A->ob_refcnt == 1)
>       A->__class__ = NULL; /* Make a finalizer-less */
>   DECREF(A);
>
> This avoids finalizing twice if the first finalization broke all
> cycles in which A is involved.  But if it doesn't, A is still cyclical
> garbage with a finalizer!  Even if it didn't resurrect itself.
>
> Instead of the code fragment above, we could mark A as "just
> finalized" and when it shows up at the head of the tree (of finalizers
> in cyclical trash) again on the next garbage collection, to discard it
> without calling the finalizer again (because this clearly means that
> it didn't resurrect itself -- at least not for a very long time).

I don't think you need to do any of this -- unless you think you need to do
the thing that created the need for this, which I didn't think you needed to
do either <wink>.

> I would be happier if we could still have a rule that says that a
> finalizer is called only once by magic -- even if we have two forms of
> magic: refcount zero or root of the tree.  Tim: I don't know if you
> object against this rule as a matter of principle (for the sake of
> finalizers that resurrect the object) or if your objection is really
> against the unordered calling of finalizers legitimized by Java's
> rules.  I hope the latter, since I think it that this rule (__del__
> called only once by magic) by itself is easy to understand and easy to
> deal with, and I believe it may be necessary to guarantee progress for
> the garbage collector.

My objections to Java's rules have been repeated enough.

I would have no objection to "__del__ called only once" if it weren't for
that Python currently does something different.  I don't know whether people
rely on that now; if they do, it's a much more dangerous thing to change
than adding a new keyword (the compiler gives automatic 100% coverage of the
latter; but nothing mechanical can help people track down reliance-- whether
deliberate or accidental --on the former).

My best *guess* is that __del__ is used rarely; e.g., there are no more than
40 instances of it in the whole CVS tree, including demo directories; and
they all look benign (at least three have bodies consisting of "pass"!).
The most complicated one I found in my own code is:

    def __del__(self):
        self.break_cycles()

    def break_cycles(self):
        for rule in self.rules:
            if rule is not None:
                rule.cleanse()

But none of this self-sampling is going to comfort some guy in France who
has a megaline of code relying on it.  Good *bet*, though <wink>.

> [and another cogent explanation of why breaking the "leave cycles with
>  finalizers" alone injunction creates headaches]

> ...
> Even if someone once found a good use for resurrecting inside __del__,
> against all recommendations, I don't mind breaking their code, if it's
> for a good cause.  The Java rules aren't a good cause.  But top-sorted
> finalizer calls seem a worthy cause.

They do to me too, except that I say even a cycle involving but a single
object (w/ finalizer) looping on itself is the user's problem.

> So now we get to discuss what to do with multi-finalizer cycles, like:
>
>   A <=> b <=> C
>
> Here the reduced graph is:
>
>   A <=> C

The SCC reduction is simply to

    A

and, right, the scheme at the top punts.

> [more the on once-only rule chopped]
> ...
> Anyway, once-only rule aside, we still need a protocol to deal with
> cyclical dependencies between finalizers.  The __cleanup__ approach is
> one solution, but it also has a problem: we have a set of finalizers.
> Whose __cleanup__ do we call?  Any?  All?  Suggestions?

This is why a variant of guardians were more appealing to me at first:  I
could ask a guardian for the entire SCC, so I get the *context* of the
problem as well as the final microscopic symptom.

I see Marc-Andre already declined to get sucked into the magical part of
this <wink>.  Greg should speak for his scheme, and I haven't made time to
understand it fully; my best guess is to call x.__cleanup__ for every object
in the SCC (but there's no clear way to decide which order to call them in,
and unless they're more restricted than __del__ methods they can create all
the same problems __del__ methods can!).

> Note that I'd like some implementation freedom: I may not want to
> bother with the graph reduction algorithm at first (which seems very
> hairy) so I'd like to have the right to use the __cleanup__ API
> as soon as I see finalizers in cyclical trash.  I don't mind disposing
> of finalizer-free cycles first, but once I have more than one
> finalizer left in the remaining cycles, I'd like the right not to
> reduce the graph for topsort reasons -- that algorithm seems hard.

I hate to be realistic <wink>, but modern GC algorithms are among the
hardest you'll ever see in any field; even the outer limits of what we've
talked about here is baby stuff.  Sun's Java group (the one in Chelmsford,
MA, down the road from me) had a group of 4+ people (incl. the venerable Mr.
Steele) working full-time for over a year on the last iteration of Java's
GC.  The simpler BDW is a megabyte of code spread over 100+ files.  Etc --
state of the art GC can be crushingly hard.

So I've got nothing against taking shortcuts at first -- there's actually no
realistic alternative.  I think we're overlooking the obvious one, though:
if any finalizer appears in any trash cycle, tough luck.  Python 3000 --
which may be a spelling of 1.7 <wink>, but doesn't *need* to be a spelling
of 1.6.

> So we're back to the __cleanup__ design.  Strawman proposal: for all
> finalizers in a trash cycle, call their __cleanup__ method, in
> arbitrary order.  After all __cleanup__ calls are done, if the objects
> haven't all disposed of themselves, they are all garbage-collected
> without calling __del__.  (This seems to require another garbage
> colelction cycle -- so perhaps there should also be a once-only rule
> for __cleanup__?)
>
> Separate question: what if there is no __cleanup__?  This should
> probably be reported: "You have cycles with finalizers, buddy!  What
> do you want to do about them?"  This same warning could be given when
> there is a __cleanup__ but it doesn't break all cycles.

If I *ever* have a trash cycle with a finalizer in my code (> 0 -- "exactly
1" isn't special to me), I will consider it to be a bug.  So I want a way to
get it back from gc, so I can see what the heck it is, so I can fix my code
(or harass whoever did it to me).  __cleanup__ suffices for that, so the
very act of calling it is all I'm really after ("Python invoked __cleanup__
== Tim has a bug").

But after I outgrow that <wink>, I'll certainly want the option to get
another kind of complaint if __cleanup__ doesn't break the cycles, and after
*that* I couldn't care less.  I've given you many gracious invitations to
say that you don't mind leaking in the face of a buggy program <wink>, but
as you've declined so far, I take it that never hearing another gripe about
leaking is a Primary Life Goal.  So collection without calling __del__ is
fine -- but so is collection with calling it!  If we're going to (at least
implicitly) approve of this stuff, it's probably better *to* call __del__,
if for no other reason than to catch your case of some poor innocent object
caught in a cycle not of its making that expects its __del__ to abort
starting World War III if it becomes unreachable <wink>.

whatever-we-don't-call-a-mistake-is-a-feature-ly y'rs  - tim