Is python maximum recurrence depth per object?

Question

I am refactoring a Python signal processing framework because of a maximum recurrence depth error we experienced.

The most likely explanation for the error is that sometimes a large number of instances of a single class are created recursively from the class' its init method. Indeed experiments simulating this situation lead to a Exception RuntimeError: 'maximum recursion depth exceeded'.

When I move creating the next element in the chain to the container managing these objects the problem seems to disappear, this despite building in my naive understanding a call stack of the same depth. I call create through all the previously created objects. (see example code).

I am inclined to conclude that the recursion depth limit is somehow set per object (be it a class or an instance). Which when creating recursively via init probably puts everything on the stack of the class, where as if we create them recursively through a line of instances of the same class all the objects will have very limited recursion depth.

I am seeking some confirmation for this hypothesis, but find it hard to get either confirmation or refutation.

import sys

class Chunk(object):
    pre=None
    post=None
    def __init__(self, container,pre):
        print 'Chunk Created'
        self.pre=pre
        self.container=container

    def create(self,x):
        if self.post == None:
            self.post=Chunk(self.container,self)
            newChunk =self.post
        else:
            newChunk =self.post.create(x+1)
        return newChunk

    def droprefs(self):
        print 'refcount droprefs start: ', sys.getrefcount(self)
        if not self.pre ==None:
            self.pre.droprefs()

        self.pre=None
        self.post=None
        self.container=None
        print 'refcount droprefs end: ', sys.getrefcount(self)

    def claimContainer(self):
        self.container.setmasterchunk(self)
        self.pre.droprefs()
        self.pre=None

class Container(object):
    masterchunk=None

    def __init__(self):
        self.masterchunk=Chunk(self, None)

    def setmasterchunk(self, chunk):
        print 'refcount 5: ', sys.getrefcount(self.masterchunk)
        self.masterchunk=chunk
        print 'refcount 6: ', sys.getrefcount(self.masterchunk)

    def testrecursion(self,n):

        for i in range(n):
            print 'refcount 6: ', sys.getrefcount(self.masterchunk)
            newChunk=self.masterchunk.create(1)

        return newChunk

    def testhistoryremoval(self,chunk):
        chunk.claimContainer()



if __name__ == '__main__':
    C=Container()
    middle=C.testrecursion(300)
    last=C.testrecursion(600)
    last=C.testhistoryremoval(middle)

    if middle== C.masterchunk:
        print 'SUCCESS'

Note added:

Code showing the maximum recursion depth:

import sys
from time import sleep

class Chunk(object):
    pre=None
    post=None
    def __init__(self, container,pre,n):
        print 'Chunk Created'
        self.pre=pre
        self.container=container

        if n>0:
            self.post=Chunk(self.container,self,n-1)

    def droprefs(self):
        print 'refcount droprefs start: ', sys.getrefcount(self)
        if not self.pre ==None:
            self.pre.droprefs()

        self.pre=None
        self.post=None
        self.container=None
        print 'refcount droprefs end: ', sys.getrefcount(self)

    def claimContainer(self):
        self.container.setmasterchunk(self)
        self.pre.droprefs()
        self.pre=None

class Container(object):
    masterchunk=None

    def __init__(self):
        pass

    def setmasterchunk(self, chunk):
        print 'refcount 5: ', sys.getrefcount(self.masterchunk)
        self.masterchunk=chunk
        print 'refcount 6: ', sys.getrefcount(self.masterchunk)

    def testrecursion(self,n):
        self.masterchunk=Chunk(self,None,n)



if __name__ == '__main__':
    print('Try 10')
    C0=Container()
    C0.testrecursion(10)

    sleep(2)

    print('Try 1000')
    C1=Container()
    C1.testrecursion(1000)

"When I move creating the next element in the chain to the container managing these objects the problem seems to disappear" - most likely because you're no longer recursing, or you're recursing less deeply. — user2357112, Aug 04 '16 at 22:08
You can change the recursion depth. There's an algorithm that computes it for you based on your computer's performance. — noumenal, Aug 04 '16 at 22:14
Isn't signal-processing compute-intensive? If so, recursion does not seem suitable. — Elazar, Aug 04 '16 at 22:26
@Elazar The signal-processing is computationally intensive, but the code I am aiming at is the mechanism for landing incoming information in the right place, it precedes the actual signal-processing. When it is done and published I can put an update here if you are interested. — Ronald van Elburg, Aug 05 '16 at 08:26

score 0 · Answer 1 · answered Aug 04 '16 at 22:19

No, it's a global recursion depth. The situation you describe implies that when you exceed the stack limit, you catch the exception and continue with the next object. This process removes the associated stack entries -- unravelling the recursion to its starting point.

You start fresh with the next object. If this one doesn't exceed the stack depth, it will complete smoothly -- the prior stack entries do not affect the new one.

Elazar · Answer 2 · 2016-08-05T08:57:02.387

0

In the implementation I use, setting

sys.setrecursionlimit(907)

demonstrates that this is the recursion depth you reach.

To your question, the answer is no. In the source code of CPython you can see that the recursion depth is per thread, not per object.

pystate.h:

typedef struct _ts {
    /* See Python/ceval.c for comments explaining most fields */

    //...
    int recursion_depth;
    //...
}

ceval.c:

/* the macro Py_EnterRecursiveCall() only calls _Py_CheckRecursiveCall()
   if the recursion_depth reaches _Py_CheckRecursionLimit.
   If USE_STACKCHECK, the macro decrements _Py_CheckRecursionLimit
   to guarantee that _Py_CheckRecursiveCall() is regularly called.
   Without USE_STACKCHECK, there is no need for this. */
int
_Py_CheckRecursiveCall(const char *where)
{
    PyThreadState *tstate = PyThreadState_GET();
    //...
    if (tstate->recursion_depth > recursion_limit) {
        --tstate->recursion_depth;
        tstate->overflowed = 1;
        PyErr_Format(PyExc_RecursionError,
                     "maximum recursion depth exceeded%s",
                     where);
        return -1;
     }
   //...
}

tstate is shorthand for thread-state.

edited Aug 05 '16 at 08:57

answered Aug 04 '16 at 22:22

Elazar

20,415
4
46
67

How does this explain the difference in behaviour with the second example which I now added to the original question? Are the threads automagically created in one scenario and not in the other? – Ronald van Elburg Aug 05 '16 at 08:09
@Prune OK I played around a bit with both examples given, and the difference seems to be a matter of degree. Where the creation from __init__ scenario already stops at a "naive recursion depth" of 300 the first scenario stops at a "naive recursion depth" of between 900 and 1000. So supposedly python is adding some function calls when implementing the constructor (which I think make sense.). So concluding: recursion over a chain of objects to reach the last object in the chain is not a good solution when the chain gets long. – Ronald van Elburg Aug 05 '16 at 08:17
@RonaldvanElburg you replied to the wrong answer. However, I don't get why do you think that recursing 300 and then 600 will reach the maximum depth of 1000. – Elazar Aug 05 '16 at 08:54
Because the second set of 600 goes through the objects created in the first call, you get a recursion depth of 900. That still works. If I crank it up to 1000 it fails. I thought my previous comment confirmed both your and Prune's answer. That is why I put a comment here, with a reference to Prune. Please let me know If there is a better way to handle this. – Ronald van Elburg Aug 05 '16 at 09:05

Blckknght · Accepted Answer · 2016-08-04T22:45:05.733

You can rewrite your methods to be iterative instead of recursive. This avoids the possibility of recursion depth errors regardless of how deep your data structure becomes.

The create method would become something like this:

def create(self, x): # the `x` arg is not actually used for anything?
    chunk = self

    while chunk.post is not None:
        chunk = chunk.post

    chunk.post = Chunk(self.container, chunk)

    return self.post # this matches the old code but you may actually want `return self.post`

You could do something similar with droprefs. Your current code seems to iterate from the end of the list forwards, which may or may not be what you want. Here's a direct translation to iterative behavior:

def droprefs(self):
    chunk = self

    while chunk:
        next = chunk.pre # this iterates backwards, to go forwards use `next = chunk.post`

        chunk.pre = None
        chunk.post = None
        chunk.container = None

        chunk = next

I'd also note that unless you're expect external code to hold references to earlier Chunks, you probably don't need to use droprefs at all. After claimContainer does self.pre = None, the garbage collector should be able to clean up all the earlier Chunk instances, since there are no more external references to them. Getting rid of their references to each other might make it work faster (since the pre and post attributes form reference cycles), but it is not strictly necessary.

This is the solution I am planning but it requires quite a bit of work and mightbreak my code. I wanted to make sure I understand the call stack sufficiently before taking off on this adventure. The original code already has a lot of reference removal to allow the garbage collector to do its work. — Ronald van Elburg, Aug 05 '16 at 08:19

Is python maximum recurrence depth per object?

3 Answers3