2016-08-04 36 views
0

Ich überarbeite ein Python-Signalverarbeitungsframework wegen eines maximalen Wiederholungstiefefehlers, den wir erfahren haben.Ist Python maximale Wiederholungstiefe pro Objekt?

Die wahrscheinlichste Erklärung für den Fehler ist, dass manchmal eine große Anzahl von Instanzen einer einzelnen Klasse rekursiv aus der Klasse 'init Methode erstellt wird. In der Tat führen Experimente, die diese Situation simulieren, zu einem Exception RuntimeError: "Maximale Rekursionstiefe überschritten".

Wenn ich das nächste Element in der Kette zu dem Container verschiebe, der diese Objekte verwaltet, scheint das Problem zu verschwinden, obwohl dies in meinem naiven Verständnis einen Call-Stack von gleicher Tiefe erzeugt. Ich rufe Create über alle zuvor erstellten Objekte auf. (siehe Beispielcode).

Ich neige zu der Schlussfolgerung, dass die Rekursionstiefe Grenze irgendwie pro Objekt (sei es eine Klasse oder eine Instanz) festgelegt ist. Was beim rekursiven Erzeugen über init wahrscheinlich alles auf den Stack der Klasse stellt, wobei wir, als ob wir sie rekursiv durch eine Reihe von Instanzen derselben Klasse erzeugen würden, alle Objekte eine sehr begrenzte Rekursionstiefe hätten.

Ich suche eine Bestätigung für diese Hypothese, aber finde es schwierig, entweder Bestätigung oder Widerlegung zu erhalten.

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' 

Anmerkung hinzugefügt:

-Code die maximale Rekursionstiefe zeigt:

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) 
+0

"Wenn ich das nächste Element in der Kette zum Container verschiebe, der diese Objekte verwaltet, scheint das Problem zu verschwinden" - höchstwahrscheinlich, weil Sie nicht mehr rekursiv sind oder weniger rekursiv sind. – user2357112

+0

Sie können die Rekursionstiefe ändern. Es gibt einen Algorithmus, der es basierend auf der Leistung Ihres Computers für Sie berechnet. – noumenal

+0

Related: http://StackOverflow.com/A/26873813/2289509 – Elazar

Antwort

0

Bei der Umsetzung I,

zeigt
sys.setrecursionlimit(907) 

Einstellung verwenden, dass dies die Rekursionstiefe ist Sie zu erreichen.


Auf Ihre Frage ist die Antwort nein. Im Quelltext von CPython sehen Sie, dass die Rekursionstiefe pro Thread ist, nicht pro Objekt.

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 ist eine Abkürzung für faden Zustand.

+0

Wie erklärt dies den Unterschied im Verhalten mit dem zweiten Beispiel, das ich jetzt zur ursprünglichen Frage hinzufügte? Werden die Threads automatisch in einem Szenario erstellt und nicht in dem anderen? –

+0

@Prune OK Ich habe ein bisschen mit beiden Beispielen gespielt, und der Unterschied scheint eine Frage des Grades zu sein. Wo die Erzeugung aus dem __init__ -Szenario bereits bei einer "naiven Rekursionstiefe" von 300 aufhört, stoppt das erste Szenario bei einer "naiven Rekursionstiefe" zwischen 900 und 1000. So fügt Python angeblich einige Funktionsaufrufe bei der Implementierung des Konstruktors hinzu (was ich denke Sinn ergeben.). Fazit: Rekursion über eine Kette von Objekten, um das letzte Objekt in der Kette zu erreichen, ist keine gute Lösung, wenn die Kette lang wird. –

+0

@RonaldvanElburg Sie antworteten auf die falsche Antwort. Ich verstehe jedoch nicht, warum 300 und dann 600 die maximale Tiefe von 1000 erreichen. – Elazar

0

Nein, es ist eine globale Rekursionstiefe. Die Situation, die Sie beschreiben, impliziert, dass Sie die Ausnahme abfangen und mit dem nächsten Objekt fortfahren, wenn Sie das Stapellimit überschreiten. Dieser Prozess entfernt die zugehörigen Stapeleinträge - Entschlüsselung der Rekursion zu ihrem Startpunkt.

Sie beginnen mit dem nächsten Objekt neu. Wenn diese die Stapeltiefe nicht überschreitet, wird sie reibungslos abgeschlossen - die vorherigen Stapeleinträge wirken sich nicht auf die neue aus.

0

Sie können Ihre Methoden so umschreiben, dass sie iterativ statt rekursiv sind. Dies vermeidet die Möglichkeit von Rekursionstief Fehlern, unabhängig davon, wie tief Ihre Datenstruktur wird.

Die create Methode wäre so etwas wie dieses werden:

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` 

Sie etwas Ähnliches tun könnte mit droprefs. Ihr derzeitiger Code scheint vom Ende der Liste nach vorne zu iterieren, was vielleicht nicht das ist, was Sie wollen. Hier ist eine direkte Übersetzung iteratives Verhalten:

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 

Ich würde auch beachten, dass es sei denn, Sie erwarten, sind externer Code Verweise auf frühere Chunk s zu halten, werden Sie wahrscheinlich nicht droprefs brauchen überhaupt zu benutzen. Nach claimContainer tut self.pre = None, sollte der Garbage Collector in der Lage sein, alle früheren Chunk Instanzen aufzuräumen, da es keine externen Referenzen mehr gibt. Werden die Referenzen voneinander entfernt, kann es schneller funktionieren (da die pre und post Attribute Referenzzyklen bilden), aber es ist nicht unbedingt notwendig.

+0

Dies ist die Lösung, die ich plane, aber es erfordert eine Menge Arbeit und kann meinen Code brechen. Ich wollte sicherstellen, dass ich den Call-Stack ausreichend verstehe, bevor ich auf dieses Abenteuer losfahre. Der ursprüngliche Code hat bereits eine Menge von Verweis entfernen, damit der Garbage Collector seine Arbeit erledigen kann. –