[Python-Dev] Cyclic GC issues

[Tim Peters]

[Tim Peters]
>> I think you're in for a rude awakening if you expect any language's gc
>> support to help you manage arbitrary blobs of memory obtained from the
>> system malloc().
 
[Jason Evans]
> I don't expect that.  What I do expect is for there to be clean and
> efficient mechanisms for integrating custom Python object types into
> Python.  Python more or less meets this expectation.

OK ... but you must want more than just that, else this thread
wouldn't have started <wink>.

>> If all the nodes in your object graph derived from PyObject, Python's gc
>> would do it all for you.  If you want to plant pointers in and among
>> arbitrary C structs, then you'll have to implement your own gc, or hope
>> that you can bash a general gc thingie (like BDW -- and I'm not sure
>> there is anything else of that sort usefully available, so "like" is
>> probably optimistic) into guessing the layout of your structs.

> No, this is not necessary.  What is necessary is for my code to accurately
> maintain and report all references to Python objects during traversal.  The
> Crux code does so, and works as designed.

Isn't it also necessary for your code to clean up object graphs where
the nodes are *not* Python objects?  That's what I thought you were
saying to Martin,  If I misunderstood that, I apologize.  Almost
everything else I said was based on that belief.

>>> Crux was designed this way in order to be able to implement
various low level
>>> algorithms such that they never have to call interpreter-related code.

>> I don't know why that was thought to be desirable, or even exactly
>> what it means.  One plausible meaning is that you don't want to tie
>> the "various low level algorithms" to Python, because you hope to
>> reuse them in other, non-Python contexts.  And, in addition to that,
>> you don't want, or don't know how, to abstract the necessary
>> operations into macros or functions that are pluggable for the
> > different contexts you have in mind.
 
> First, "hoping" to be able use my code in other contexts is what allowed me
> to transition from using a different embeddable interpreter to using Python
> inside of two days.  Had I melded all of the scripting glue code with the
> low level tree code, it would not have been nearly as easy to transition to
> using Python.

So the "you don't want to tie ... to Python" guess was right (please
realize that you haven't *said* so before), and the "don't want to
abstract ... into macros or functions" part of the other guess was on
target (ditto).  I think you're reading judgments into my attempts to
extract answers.  It's fine by me if you don't want to make everything
a PyObject, but then I'm also trying to explain consequences of that
choice wrt what Python's gc will and won't do for you.

> Second, I have the scripting language glue and low level tree code
> separated for two reasons: 1) performance, and 2) modularization.  There's
> no question of whether I want to use cpp magic to be able to munge two
> large piles of code into one huge pile of code, nor whether I'm capable of
> doing so.  To do so would simply take the code in a bad direction.

Maybe.  I resist some here because adding just enough PyObject hair to
enable a C struct to work smoothly with Python's native gc doesn't
usually count as a "large pile" of code by any metric I use, and
really does make gc life easy.

[Martin]
>>>> 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?

[Jason]
>>> Yes, this is true.

>> It's false, but I covered that one yesterday.
 
> It is true, given my interpretation of the original context of the
> dialogue.  We were discussing whether it would work for a node object to
> hold a reference to a single ring object, and rely on the ring objects to
> report their neighbors.  Indeed this would work.

Regardless of context, in Python's gc there is no sense in which
calling a visit() callback "in turn" invokes visit() on anything.  If
there is a sense here in which that is true, the context must be
something other than Python's gc.  If the ring objects are not
PyObject themselves (I thought it was clear that they weren't, but
maybe that was wrong), then Python's gc gives them no way to "report
their neighbors".

>>> The problem I ran into had to do with the node logically holding
references to
>>> all the ring objects, but only reporting one of them.

>> If a ring object doesn't derive from PyObject, then visit() must not
>> be passed a pointer to a ring object.  Doing so would account for many
>> catastrophic meanings of "doesn't work" <wink>.

> If you want to see the Crux source code, I'll be happy to provide you with
> a source archive.

I'd like to say "yes", but I'll never make time to look at it.  I
would have been happier here if you had confirmed or denied that ring
objects don't derive from PyObject.  I pressed before on that "doesn't
work" isn't helpful, and that never got clarified.  Possible meanings
include segfaults, error messages, Python exceptions. and memory
leaks.

> In the meanwhile, please rest assured that the code doesn't suck nearly as
> badly as you are insinuating here.

I'm not insinuating anything about the code, I'm trying to guess what
you meant in your original post by "doesn't work" this-and-that. 
Passing a non-PyObject* to visit() remains a possible cause for
"doesn't work" in my head, because you haven't said anything to rule
it out.  If you in fact *had* been passing a non-PyObject* to visit(),
then the paragraph above could have been helpful ("ah, that's why it
didn't work!").

>> We can help you use Python's gc, but not if you're unwilling or unable
>> to change anything about what you do.

> Prior to switching to using Python, Crux integrated with a language that
> implemented atomic mark and sweep garbage collection.  I have had to change
> a tremendous amount about Crux in order to use a reference counted
> interpreter.  In fact, I made some changes to Crux this morning that were a
> direct result of your original response to my email (ring objects now
> report references to themselves, which makes reference counting of ring
> objects much simpler).

So Ring objects do derive from PyObject*.  Forget everything I said then <wink>.

> Many of the issues I ran into had to do with the impedence mismatch between
> my previous experience and the way Python works.

I sure believe that.  Python's cyclic gc is unusual in several respects.

> I appreciate you taking the time to respond to me, especially since you've
> helped me gain a deeper understanding of how Python's GC works.  However,
> please get it out of your mind that I am incompetent and/or set in my ways.

Those aren't in my head.  I do think you're so steeped in the details
of your code that you're not nearly as successful at communicating the
*salient* points as you think you are, though.  I'm so steeped in the
details of Python's gc that a similar claim could easily be made of
me.  I don't expect it to be clear the first time, though, so play
20-questions trying to tease out what you really need to know about
it.  If it's any consolation, this process has been painful on both
sides <wink>.

>>> I should have said tp_clear here.  In Modules/gcmodule.c:delete_garbage(),
>>> the clear() call does not pay attention to the return value.

>> Heh.  So true!  See
>>
>>     http://mail.python.org/pipermail/python-dev/2003-April/034435.html

>>> It would be possible to check the return value, and defer deallocatin if the
>>> return value were non-zero, and ob_refcnt were 1.  (However, it
would probably
>>> have to be a separate list of objects, contrary to what I claimed before.)

>> I'm not sure, but I think your desire for this was still based on
>> misunderstanding of what Python's gc does.
 
> Of the original issues I brought up, I think this one potentially still has
> merit, though I'm not sure that it's of sufficiently general utility.  The
> idea is to allow extension modules some control over the order in which
> objects are deallocated, so that it is possible to tear down
> interconnections in a particular order.

Well, think about it some more then.  "A separate list of objects" is
very easy to create efficiently in Python's gc internals -- each
gc'able object is in *some* doubly-linked list, so the cost of a new
list is just a new header node to identify it, and moving a gc'able
object from one list to another is 6 pointer stores.

> However, it occurs to me that since tp_clear can leave references in place,
> it might be possible to control the object destruction order by leaving a
> DAG of references in place, and letting Python deallocate objects in
> dependency order.  Does this work?

It could.  Here it should help to know that Python's cyclic gc never
calls an object's tp_dealloc directly.  The only way tp_dealloc ever
triggers in Python is as a side effect of a refcount falling to zero
-- no exceptions.  So, indeed, "all" cyclic gc does is break cycles,
and the only places garbage actually gets recycled in gcmodule.c are
as side effects of the

	Py_DECREF(op);

lines in delete_garbage() and release_weakrefs().  Weakrefs are
probably irrelevant to you at this point, so there's only one
Py_DECREF() in the codebase you care about.  So, e.g, if you have a
simple cycle like

     A -> B -> C -> ... -> Z -> A

and the tp_clear() calls break only the link from Z to A, that's all
they *need* to do, and then A's tp_dealloc() will be called first,
then B's tp_dealloc, ..., and finally Z's tp_dealloc.  You should be
aware that long chains of that sort can end up overflowing the C
stack, depeding on how tp_dealloc is coded.

That's in CPython, of course.  Jython uses Java's native gc, and I
suppose (but don't know that) IronPython uses .NET's.