Einleitung

Dieser PEP diskutiert Änderungen, die am Kern von Python erforderlich sind, um Generatoren, Microthreads und Coroutinen effizient zu unterstützen. Er steht im Zusammenhang mit PEP 220, das beschreibt, wie Python erweitert werden sollte, um diese Einrichtungen zu unterstützen. Der Fokus dieses PEPs liegt ausschließlich auf den Änderungen, die erforderlich sind, damit diese Erweiterungen funktionieren.

Während diese PEPs auf Christian Tismers Stackless [1] Implementierung basieren, betrachten sie Stackless nicht als Referenzimplementierung. Stackless (mit einem Erweiterungsmodul) implementiert Continuations, und aus Continuations kann man Coroutinen, Microthreads (wie von Will Ware [2] durchgeführt) und Generatoren implementieren. Aber in über einem Jahr hat niemand einen anderen produktiven Nutzen für Continuations gefunden, sodass es offenbar keine Nachfrage nach ihrer Unterstützung gibt.

Die Stackless-Unterstützung für Continuations ist jedoch ein relativ kleiner Teil der Implementierung, sodass man sie als "eine" Referenzimplementierung (anstatt als "die" Referenzimplementierung) betrachten könnte.

Hintergrund

Generatoren und Coroutinen wurden in einer Reihe von Sprachen auf verschiedene Weise implementiert. Tatsächlich hat Tim Peters reine Python-Implementierungen von Generatoren [3] und Coroutinen [4] unter Verwendung von Threads durchgeführt (und eine Thread-basierte Coroutinen-Implementierung existiert für Java). Der horrende Overhead einer Thread-basierten Implementierung schränkt jedoch die Nützlichkeit dieses Ansatzes stark ein.

Microthreads (auch "green" oder "user" Threads genannt) und Coroutinen beinhalten Kontrolltransfers, die in einer auf einem einzelnen Stack basierenden Sprachimplementierung schwer zu unterbringen sind. (Generatoren können auf einem einzelnen Stack realisiert werden, können aber auch als ein sehr einfacher Fall von Coroutinen betrachtet werden.)

Echte Threads weisen jedem Kontrollfaden einen voll dimensionierten Stack zu, und dies ist die Hauptursache für den Overhead. Coroutinen und Microthreads können jedoch in Python auf eine Weise implementiert werden, die fast keinen Overhead verursacht. Dieser PEP bietet daher einen Weg, Python in die Lage zu versetzen, Tausende von separaten "Threads" von Aktivitäten realistisch zu verwalten (im Gegensatz zur heutigen Begrenzung auf vielleicht Dutzende von separaten Threads von Aktivitäten).

Eine weitere Rechtfertigung für diesen PEP (erforscht in PEP 220) ist, dass Coroutinen und Generatoren oft einen direkteren Ausdruck eines Algorithmus ermöglichen als im heutigen Python möglich ist.

Diskussion

Das erste, was zu beachten ist, ist, dass Python, obwohl es Interpreterdaten (normale C-Stack-Nutzung) mit Python-Daten (dem Zustand des interpretierten Programms) auf dem Stack vermischt, die beiden logisch getrennt sind. Sie benutzen nur zufällig denselben Stack.

Ein echter Thread erhält etwas, das einem prozessgroßen Stack nahekommt, weil die Implementierung nicht weiß, wie viel Speicherplatz der Thread benötigen wird. Der für einen einzelnen Frame benötigte Stack-Speicher ist wahrscheinlich angemessen, aber Stack-Wechsel sind ein obskurer und nicht portabler Prozess, der von C nicht unterstützt wird.

Sobald Python jedoch aufhört, Python-Daten auf dem C-Stack zu platzieren, wird der Stack-Wechsel einfach.

Der grundlegende Ansatz des PEP basiert auf diesen beiden Ideen. Erstens, die C-Stack-Nutzung von der Python-Stack-Nutzung trennen. Zweitens, jedem Frame genügend Stack-Speicher zuweisen, um die Ausführung dieses Frames zu bewältigen.

Im normalen Gebrauch hat Stackless Python eine normale Stack-Struktur, nur dass sie in Blöcke unterteilt ist. Aber in Anwesenheit einer Coroutinen-/Microthread-Erweiterung unterstützt derselbe Mechanismus einen Stack mit einer Baumstruktur. Das heißt, eine Erweiterung kann Kontrolltransfers zwischen Frames außerhalb des normalen "Aufruf / Rückkehr"-Pfades unterstützen.

Probleme

Die größte Schwierigkeit bei diesem Ansatz ist das Aufrufen von Python durch C. Das Problem ist, dass der C-Stack nun eine verschachtelte Ausführung des Bytecode-Interpreters enthält. In dieser Situation darf einer Coroutinen-/Microthread-Erweiterung kein Transfer zu einem Frame in einer anderen Ausführung des Bytecode-Interpreters gestattet werden. Wenn ein Frame abgeschlossen wäre und von der falschen Interpreter-Ausführung zurück an C gehen würde, könnte der C-Stack beschädigt werden.

Die ideale Lösung ist die Schaffung eines Mechanismus, bei dem verschachtelte Ausführungen des Bytecode-Interpreters nie benötigt werden. Die einfache Lösung besteht darin, dass die Coroutinen-/Microthread-Erweiterung(en) die Situation erkennen und Transfers außerhalb der aktuellen Ausführung verweigern.

Wir können Code, der C beim Aufrufen von Python beinhaltet, in zwei Lager einteilen: die Implementierung von Python und C-Erweiterungen. Und hoffentlich können wir einen Kompromiss anbieten: Die interne Nutzung von Python (und C-Erweiterungsschreiber, die sich die Mühe machen wollen) werden keine verschachtelte Interpreter-Ausführung mehr verwenden. Erweiterungen, die sich nicht die Mühe machen, bleiben sicher, aber werden nicht gut mit Coroutinen / Microthreads zusammenspielen.

Im Allgemeinen erfordert die Umwandlung eines rekursiven Aufrufs in eine Schleife zusätzliche Buchführungsarbeit. Die Schleife muss ihren eigenen "Stack" von Argumenten und Ergebnissen beibehalten, da der tatsächliche Stack nur das Neueste aufnehmen kann. Der Code wird ausführlicher sein, da es nicht ganz so offensichtlich ist, wann wir fertig sind. Obwohl Stackless nicht auf diese Weise implementiert ist, muss es mit denselben Problemen fertig werden.

Im normalen Python wird PyEval_EvalCode verwendet, um einen Frame zu erstellen und auszuführen. Stackless Python führt das Konzept eines FrameDispatcher ein. Wie PyEval_EvalCode führt er einen Frame aus. Der Interpreter kann jedoch den FrameDispatcher signalisieren, dass ein neuer Frame hineingewechselt wurde und der neue Frame ausgeführt werden soll. Wenn ein Frame abgeschlossen ist, folgt der FrameDispatcher dem Rückwärtszeiger, um den "aufrufenden" Frame fortzusetzen.

Stackless transformiert Rekursionen also in eine Schleife, aber es ist nicht der FrameDispatcher, der die Frames verwaltet. Dies geschieht durch den Interpreter (oder eine Erweiterung, die weiß, was sie tut).

Die allgemeine Idee ist, dass C-Code, der Python-Code ausführen muss, einen Frame für den Python-Code erstellt und dessen Rückwärtszeiger auf den aktuellen Frame setzt. Dann wird der Frame hineingewechselt, der FrameDispatcher signalisiert und sich aus dem Weg geräumt. Der C-Stack ist nun sauber - der Python-Code kann die Kontrolle an jeden anderen Frame übertragen (wenn eine Erweiterung ihm die Mittel dazu gibt).

Im Standardfall kann dieser Zauber vor dem Programmierer (sogar, in den meisten Fällen, vor dem Programmierer für Python-Interna) verborgen bleiben. Viele Situationen stellen jedoch eine weitere Schwierigkeit dar.

Die eingebaute `map`-Funktion stellt zwei Hindernisse für diesen Ansatz dar. Sie kann nicht einfach einen Frame erstellen und sich aus dem Weg räumen, nicht nur wegen der Schleife, sondern weil jeder Durchlauf der Schleife eine "Nachbearbeitung" erfordert. Um mit anderen gut zu funktionieren, erstellt Stackless einen Frame für `map` selbst.

Die meisten Rekursionen des Interpreters sind nicht so komplex, aber ziemlich oft sind einige "Nachbearbeitungs"-Operationen erforderlich. Stackless behebt diese Situationen nicht aufgrund der Menge der erforderlichen Codeänderungen. Stattdessen verbietet Stackless Transfers aus einem verschachtelten Interpreter. Dies ist zwar nicht ideal (und manchmal verwirrend), aber diese Einschränkung ist kaum nachteilig.

Vorteile

Für normales Python besteht der Vorteil dieses Ansatzes darin, dass die C-Stack-Nutzung viel kleiner und besser vorhersehbar wird. Unbegrenzte Rekursion in Python-Code wird zu einem Speicherfehler anstelle eines Stack-Fehlers (und damit auf Nicht-Cupertino-Betriebssystemen etwas, von dem man sich erholen kann). Der Preis sind natürlich die zusätzliche Komplexität, die sich aus der Umwandlung von Rekursionen der Bytecode-Interpreter-Schleife in eine Schleife höherer Ordnung (und die damit verbundene Buchführung) ergibt.

Der große Vorteil ergibt sich aus der Erkenntnis, dass der Python-Stack wirklich ein Baum ist und der Frame-Dispatcher die Kontrolle frei zwischen Blattknoten des Baumes übertragen kann, was Dinge wie Microthreads und Coroutinen ermöglicht.

Referenzen