... & Kontext: Koroutinen

Babel-Bulletin  –  0 Kommentare

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "… & Kontext" deren jeweiligen eher theoretischen Hintergrund.

Eine der genialsten Erfindungen, die unser Leben als Softwareentwickler ungemein prägt, ist der Funktionsaufruf. Wird nämlich eine Funktion oder allgemeiner eine Routine aufgerufen, dann wird man, was auch immer man gerade macht, angehalten, die formalen Parameter mit den aktuellen Werten zu versorgen, und diese Funktion durchlaufen. Anschließend werden das Ergebnis geeignet verpackt und der angehaltene Teil wieder aktiviert, wobei das Ergebnis verwendet werden kann.

Das Schöne daran ist auch noch, dass sich die Funktion selbst nicht dafür interessieren muss, wer sie eigentlich aufgerufen hat. Das bedeutet in der Regel sogar, dass sich die Funktion selbst aufrufen kann. Noch viel besser daran ist, dass man sich nicht darum kümmern muss, wie das Programm es schafft, wieder genau an der Stelle eines Aufrufs zu landen, und dass dies auch bei beliebigen Verschachtelungen gelingt (wenn man mal von einem endlich großen Stack absieht – ohne hier verraten zu wollen, was das mit dem Stack zu tun hat).

Das Konzept der Funktion erlaubt also das Implementieren von Abläufen, die sich durch Funktionen unterbrechen lassen, um logisch unabhängige Teile separat und wiederverwendbar auszuführen. Die aufgerufenen Funktionen liefern dann irgendwelche Zwischenergebnisse, die der Aufrufer weiter verarbeiten kann. Das hat natürlich auch Konsequenzen für die aufgerufene Funktion. Beispielsweise muss sie terminieren, um das Ergebnis liefern zu können.

Warum nicht rekursiv?

Schade eigentlich. Denn gerade rekursive Funktion wären hervorragend dazu geeignet, rekursive Strukturen wie Bäume zu durchforsten und etwa nach bestimmten Elementen zu suchen. Kommen dabei mehrere Baumelemente in Frage, lassen sich diese natürlich auch akkumulieren. Leider hat das zur Folge, dass der ganze Baum zu durchsuchen ist, obwohl vielleicht nur einige der gefundenen Elemente benötigt werden. Und nachdem nichts so effizient ist wie Dinge, die weder berechnet werden müssen noch irgendeinen Platz benötigen, ist es also schade um jede Instruktion, die vergeblich ausgeführt wurde.

Leider zwingt hier einen das Terminieren dazu, dass die Funktionen, wenn die gefundenen Elemente einzeln geliefert werden sollen, immer wieder mit der Suche von vorn beginnen muss. Das kann man optimieren, indem man sich in irgendeiner Form merkt, wo man beim letzten Mal aufgehört hat, aber dazu wird wieder Speicher benötigt, der zu verwalten und schließlich freizugeben ist.

In den letzten Blog-Einträgen wurde bereits das yield vorgestellt, womit dieses Problem gelöst werden konnte: Die Suchfunktion durchläuft den Baum und bei dem ersten brauchbaren Element wird dieses mit yield zurückgeliefert. Bei erneutem Zugriff auf die Suchfunktion kann dann an eben dieser Stelle die Arbeit wieder aufgenommen werden. Allerdings wurde dabei erwähnt, dass hierfür möglicherweise der Compiler den Code so umformuliert, dass aus der Suchfunktion eine Zustandsmaschine wird. Das ist insofern nicht zufriedenstellend, weil dadurch ja gerade der Verwaltungsaufwand entsteht, der eigentlich vermieden werden sollte.

Jetzt stellt sich natürlich die Frage, wo hier eigentlich das Problem liegt. Damit die Suchfunktion nicht terminieren muss, müsste sie doch eigentlich nur autark arbeiten können. Und immer dann wenn ein Element gefunden wird, legt es dieses an einer wohldefinierten Stelle und wartet ab, ob noch nach einem weiteren Element gesucht werden soll. Der Aufrufer gibt beim ersten Mal dadurch Bescheid, dass er die Suchfunktion aufruft und wie bisher darauf wartet, dass ein Element geliefert wird. Wird eines gefunden, holt er dieses an der vereinbarten Stelle ab und verarbeitet es. Wird ein weiteres Element benötigt, benachrichtigt er die Suchfunktion und wartet wieder so lange, bis ein Element ankommt usw.

Aber das erinnert einen doch an …

… Threads. Also könnte man doch einfach beim ersten Aufruf der Suchfunktion einen Thread starten, in dem diese Suchfunktion läuft. Die Kommunikation findet dann über eine 1-elementige, blockierende Queue statt. Wann immer ein Element benötigt wird und keines da ist, blockiert der aufrufende Thread und wartet so lange, bis das Element angekommen ist. Der Such-Thread traversiert den Baum und legt jedes gefundene Element ab. Ist das zuletzt abgelegte Element noch nicht abgeholt worden, muss er blockieren, da ja nur Platz für ein einzelnes Element ist. Und wenn die Suche beendet ist, muss noch irgendwas gemacht werden, aber da würde uns schon etwas Passendes einfallen.

Das scheint eigentlich eine recht brauchbare Lösung zu sein. Allerdings gibt es aber auch an der etwas herumzumäkeln. Zum einen können beide Funktionen parallel arbeiten. Während der Aufrufer das erste Element bearbeitet, kann der Sucher bereits nach dem nächsten Element suchen. Das kann erwünscht sein, würde aber dem Anspruch widersprechen, dass auch wirklich nur dann nach einem neuen Element gesucht wird, wenn der Aufrufer danach verlangt. Und zum anderen sind Threads einfach zu teuer, um unser Problem auf diese Weise zu lösen.

Die C-Programmierer lachen sich jetzt ins Fäustchen, weil sie die passende – wenngleich nicht ganz standardkonforme – Lösung parat haben: longjmp. Was wir brauchen, ist einfach ein Sprung über Funktionsgrenzen hinweg. Ist nämlich die Suchfunktion einmal aktiviert, beendet sich diese nicht, sondern springt an die aufrufende Stelle zurück. Wird ein neues Element gesucht, springt der Aufrufer an die letzte Stelle der Suchfunktion. Und so springen die beiden Funktionen hin und her, bis die Suchfunktion keine Elemente mehr liefert oder der Aufrufer keine Elemente mehr benötigt.

Im Wesentlichen handelt es sich dabei immer noch um so etwas wie Threads, allerdings ohne die Notwendigkeit des Blockierens. Der Aufrufer hat ja sowieso schon seinen eigenen Stack, den er dazu benutzt, um sich die aktuelle Aufrufhierarchie zu merken. Die Suchfunktion benötigt dann auch einen eigenen Stack, damit diese selbst auch Routinen aufrufen und nutzen kann. Der Unterschied liegt nun aber darin, dass die anderen Teile eines Threads überflüssig sind, da es ja keinen zweiten Thread gibt. Der aktuelle Thread springt jetzt einfach nur herum und nimmt beim Rückweg immer das gefundene Element mit.

Koroutinen in Theorie und Praxis

Wegen dieses engen Zusammenspiels der in unserem Beispiel aufrufenden und der suchenden Routinen spricht man bei beiden von Koroutinen. Man hat es hier also mit extrem leichtgewichtigen "Threads" zu tun, die praktisch keinen Verwaltungsaufwand benötigen. So gibt es etwa für das Da Vinci Machine Project eine JVM-Implementierung, die derartige Koroutinen unterstützt. Diese ist in der Lage, die sonst übliche Grenze von nur mehreren tausend Threads auf mehrere zehntausend dieser leichtgewichtigen "Threads" bei der Verwendung von Koroutinen zu erhöhen.

Aber nicht, dass es einen falschen Eindruck hinterlässt: Es gibt neben Generatoren und Baumsuche beliebige andere Anwendungszwecke für solche Koroutinen. Ein typisches Beispiel ist etwa das Zusammenspiel zwischen einem Lexer und Parser, bei denen Token ausgetauscht werden. Hier muss der Lexer zustandsbehaftet sein, damit er weiß, an welcher Stelle er beim nächsten Mal weiter lesen muss. Kann man dieses Duo mit Koroutinen implementieren, wird der Lexer deutlich einfacher, muss er sich doch immer nur um ein einzelnes Token kümmern.

Und das Ganze ist nicht – wie es besonders das Beispiel mit den Generatoren suggerieren mag – auf zwei beteiligte Komponenten beschränkt. Vergleichbar zu einer Pipeline (etwa mit der Unix-Pipe) lassen sich beliebige Arbeitsschritte miteinander verknüpfen. Eine Implementierung mit Koroutinen ist dann genauso elegant und einfach zu programmieren wie Funktionen, da die einzelnen Schritte (fast) unabhängig voneinander betrachtet werden können. Darüber hinaus kann hiermit durchaus eine bessere Performanz als mit mehreren Threads erzielt werden, weil keine Nebenläufigkeitsprobleme auftreten können, dadurch kein Synchronisationsaufwand entsteht und der "Thread"-Wechsel unschlagbar schnell ist.

Leider hinken die technischen Möglichkeiten weit hinter dem praktischen Nutzen der Koroutinen hinterher. Aber dennoch ist es ein nicht zu unterschätzendes Konzept, dass hoffentlich noch in vielen Umgebungen Einzug halten wird.