[Python-Dev] Cyclic GC issues (original) (raw)

"Martin v. Löwis" martin at v.loewis.de
Sun Oct 10 23:36:11 CEST 2004

1) I originally had lone rings refer to themselves (obrefcnt started out at 3; 2 self-references and one reference held by the associated edge).

I would have thought the refcount should have been 4: two self references, plus one from E, plus one from N (maybe I don't understand what make a ring "lone", though).

This didn't work. It appears that the cyclic GC does not actually calculate the number of live references to objects (references that are reachable by traversing all objects accessible from the root set);

That's correct. It doesn't need to.

instead it assumes that if tpclear() doesn't drop the reference count to a number that equals the number of references from live objects, there must still be references from live objects.

That's also correct. tp_clear is called for objects that are not reachable from the root set, anymore, so it should break all non-reachable cycles.

Unfortunately, visit()ing self does not work, so there is no way to convince Python that all references are from unreachable objects.

Wrong. If tp_clear is called, you already know for certain that "self" is garbage. So you need to clear all references - regardless of whether you think you should: trust us, we know what we do.

Working around this in Crux requires a lot of extra reference counting complexity, because there are three different cases for reference counts, depending on how many members there are in a ring (1, 2, or 3+ members).

Why is that? Just DECREF every PyObject* in "self", then set the PyObject* to NULL. No need for any additional reference counts.

2) This issue is really just a different manifestation of issue (1).

At the C (not Python object) level, each node only actually stores a pointer to a single member of the associated ring. Given a single ring member, it is possible to traverse the ring and reach all other ring members. As mentioned in issue (1), the cyclic GC expects tptraverse() to call visit() once for each reference held. It is not enough for a node to visit() one ring member; it must visit() all ring members, in order for the GC to count how many references are from unreachable objects, versus reachable from the root set.

Hmmm. Even if a ring member holds only a single reference to another ring member, would not calling visit() on this member in turn invoke visit() on the other one, which would, in turn, invoke visit() on the next one, and so on?

In summary, issues (1) and (2) are due to how the cyclic GC does the "marking" phase of mark/sweep GC. My expectation of mark/sweep GC is that it should be sufficient to assure that all objects reachable from the root set are visit()ed at least once; it should not be important how many times each unreachable object is visit()ed.

Correct. Indeed, cyclic GC makes sure visit is not called more often than needed.

I don't have a deep enough understanding of the Python interpreter to give a detailed suggestion for improvement. I suspect that determining the root set is not an easy operation; if this is the case, then I think we're stuck with the current design. If determining the root set is easy (or even possible), then I would suggest using a standard mark/sweep collector, where unreachable objects are scheduled for destruction.

That is already the case. tp_clear is the procedure that performs the destruction.

tptraverse(), tpclear(), and tpdealloc() would retain the same structure; the only difference would be the logic that determines which objects can be destroyed.

I don't see a need for change. The logic that determines the objects to be destroyed is already "precise", determining only unreachable objects.

3) A strange thing can happen when tpclear() is called. Suppose that an edge object is being cleared, and it drops its references to the associated rings. If obrefcnt of one of the rings drops to 0 as a result, Python will tpdealloc() the ring right now, without ever calling tpclear() on the ring. That means that I have to keep track of whether tpclear() has been called on objects, if it is at all important that tpclear() be called, so that I can manually do so in tpdealloc(), if necessary. It is in my opinion reasonable to have cleanup code in tpclear(), with the assumption that it will be called precisely once, but Python makes me do extra work to make sure that this happens.

Your expectation is wrong. tp_clear is not the place to perform cleanup. It is the place to break cycles. tp_dealloc is the place to perform cleanup.

4) There is no way to control the order in which objects are tpdealloc()ed.

Correct. Unfortunately, there is no way to change that. For cyclic structures, there is no natural "starting point". Python picks an arbitrary starting point, assuming that the order does not matter. If class objects have an del, it assumes that the order does matter, and gives up - putting the objects into gc.garbage.

This could be addressed in the Python interpreter by paying heed to the return value of tpdealloc(). If the return value is non-zero, move the object to the end of the list of objects to be destroyed, so that destruction is tried later. This allows the module to impose its own destruction ordering.

I don't understand. tp_dealloc does not have a return value, so what does "pay heed" mean?

Regards, Martin

More information about the Python-Dev mailing list