Removing "tails" from cyclic garbage found by GC

Core Development
1

I’m creating a new topic for this because I don’t want to hijack discussion related to “Improving the incremental GC”.

Summary

Before the GC finalizes and clears an unreachable set, run a strongly-connected-components (SCC) pass over the unreachable object graph and remove the “tails” - objects that cannot reach any cycle - from the set. The GC then finalizes and clears only the remaining “core” (in full, exactly as before this work). The removed tails are broken naturally by the ordinary refcount cascade once delete_garbage() clears the core cycles.

Motivation

finalize_garbage() calls tp_finalize on the unreachable objects in GC list order, which is essentially arbitrary. For a chain of finalizable objects hanging off a cycle - e.g. a TextIOWrapper -> BufferedWriter -> FileIO writer held only through a reference cycle - arbitrary order can finalize the inner FileIO (closing the fd) before the outer BufferedWriter flushes, losing buffered data. An example is gh-62052, which can result in data loss.

If those chain objects are instead removed from the unreachable set before finalization, they stay alive until the cycle they hang off is cleared by delete_garbage(). Clearing the cycle drops the reference into the chain, and the chain then dies through the refcount cascade: tp_dealloc -> PyObject_CallFinalizerFromDealloc (all _io deallocs route through _PyIOBase_finalize, Modules/_io/iobase.c). The cascade is referrer-first, so the chain is finalized outermost-first: the buffer flushes before the fd closes. PEP 442 ordering is preserved for these objects, and the data-loss bug is fixed.

Core / tail definitions

Build the unreachable-only directed graph: nodes are the unreachable objects, edges are tp_traverse references whose target is also in the unreachable set.

  • A cyclic SCC is one with size > 1, or size 1 with a self-edge (tp_traverse visits the object itself). Every directed cycle lives in one of these.
  • An object is core if its SCC can reach a cyclic SCC (including being one). This deliberately includes bridge objects between cycles: for cycle1 -> C -> cycle2, node C is a single-node SCC that reaches cycle2, so C is core. Its finalizer may observe cycle2, so it must be finalized while the graph is intact.
  • An object is a tail if it is not core (cannot reach any cycle).

Prototype

A prototype has been implemented, with the help of an AI agent. It is for the GIL-enabled GC only, implementing for the free-threaded GC should not be hard.

Pros and cons

Is this actually a good idea? The main downside is that it takes extra time and memory to find the SCCs and remove the tails. The upside is that if you have acyclic trees or chains of objects, those get “torn down” in the normal way, with decref cascades and finalizers run in a sensible order (rather than essentially random order, if they are part of the unreachable set).

Estimate on space and time, from Claude Opus:

  • N = number of objects in the unreachable set (gc_list_size(unreachable))
  • T = total number of references visited by calling tp_traverse on those N
    objects
  • E = number of retained edges whose target is also in the unreachable set
    • E <= T

Extra time (expected and worst case): O(N + T)

Extra space (temporary during tail finding, 64-bit platform): 152N .. <184N + 8E bytes

If we were to implement this, I suggest it should be off by default and enabled by a flag or by calling a gc module API. We might turn it on by default in a following release, if people generally prefer it turned on. Being off by default, the main downside to adding this would be the extra code it adds to the cyclic GC implementations.

My gut feeling is, while this is a neat idea, it’s not actually worth doing. Bugs like gh-62052 can mostly be avoided by using a context manager to cleanup resources. Relying on __del__ methods and weakref callbacks has always been dangerous and, while this would improve their reliability, perhaps the cost is not worth it. Well written code would not be helped by this and then would only be paying the extra cost.

4 Likes
2

“Use a context manager” is a very similar piece of advice to “break your reference cycles”. If it was so easy, then we wouldn’t have a cyclic GC in the first place.

That said, I agree that adding a SCC detector sounds a bit overkill.

3

Well, today I learned that this isn’t actually the current behaviour. I thought that only the order in the actual cycles was not defined and the rest of the references got cleared in the normal way.

Part of me wants to then just go all the way and also handle “bridges” correctly, but I understand that that would increase the complexity.

4

In thinking about if this is worth it, I imagine if I would opt to turn tail removal on, if it was off by default. My general philosophy is that it’s almost always better to pay a bit of cost if it results in more reliability. Software flakiness costs an enormous amount of person hours and the costs scale non-linearly. For gh-62052, I personally lost at least a few hours of debugging time tracking down why a file would sometimes be empty rather than containing expected data. That hasn’t happened recently though, probably because code I run now has nearly all open calls in a with.

Before I would turn it on, I’d want a better idea of how much it costs in practice, at least for my programs. That depends on how much cyclic trash is getting created and also the structure of that (how big is the core cyclic components). If the core is small, the GC becomes “surgical” in breaking cycles and that sounds nice. If the core is large, the SCC finding doesn’t give much value.