Koroutinen: Weniger warten, asynchron arbeiten

Inhaltsverzeichnis

Services und die zugehörigen Daten sind in modernen IT-Architekturen in der Regel verteilt organisiert und über Netzwerke miteinander verbunden. Mit jedem Zugriff auf entfernte Daten ist daher eine Wartezeit (Latenz) verbunden, die in der traditionellen Programmierung jedoch unberücksichtigt blieb. Beim Aufruf einer Funktion innerhalb eines Programms wird erwartet, dass sie bei der Rückkehr die Berechnung abgeschlossen hat und das fertige Ergebnis ausliefert.

Die Welt ist asynchron, Programmiersprachen traditionell aber nicht

Im folgenden Beispiel ist httpClient.send() ein Funktionsaufruf und das Programm wartet auf die Beendigung der Funktion, bevor der Ablauf mit der nächsten Anweisung in der nächsten Zeile fortgesetzt wird.

val response: HttpResponse<String> = httpClient.send("https://swapi.co/api/planets/")
val planets: List<Planet> = parse(response.body())

Der Programmablauf erreicht die Zeile mit planets also erst, wenn der angesprochene HTTP-Server geantwortet hat. Die Abarbeitung der Funktion erfolgt synchron. Dieses Beispiel ist in der Programmiersprache Kotlin verfasst. Als noch recht junge objekt-funktionale JVM-Programmiersprache hat Kotlin einige spezielle Syntaxeigenheiten. Im folgenden Pseudocode ist beispielhaft eine Konstante val (Abkürzung von "value") mit dem Datentyp Typ mit dem Ergebnis des angegebenen Ausdrucks definiert.

val name: Typ = Ausdruck

Variablen, die auch wieder geändert werden können ("mutable"), sind in Kotlin nicht als val, sondern mit dem Schlüsselwort var definiert.

To block or not to block

Typischerweise stellt ein Betriebssystem Funktionen zur Durchführung von IO bereit und Programmiersprachen wie Java oder Kotlin greifen über die Java Virtual Machine (JVM) darauf zu.

Wenn ein Thread eine IO-Funktion durchführen möchte, ist es am einfachsten, auf die Beendigung des IOs zu warten. Der Thread ist so lange blockiert – daher spricht man in diesem Fall von "blockierendem IO".

Im obigen Beispiel dauert die Thread-Blockade innerhalb der Funktion httpClient.send, bis das Ergebnis vom Server zurückgekommen ist. Dieses Verhalten zieht jedoch erhebliche Nachteile bei der Skalierung des Programms mit sich, wenn beispielsweise viele IO-Requests gleichzeitig durchzuführen sind:

• Der Scheduler des Betriebssystems könnte einen anderen Thread ausführen. Das Wechseln von Threads benötigt allerdings ebenfalls Zeit und bringt Performanceeinbußen mit sich, weil der Kontext des geblockten Threads gespeichert und der des neu angefangenen Threads wiederhergestellt werden muss.
• Darüber hinaus belegt jeder Thread Speicherressourcen des Betriebssystems, die beim Blockieren brachliegen und nicht genutzt werden können. Bei der JVM sind es bis zu 2 MByte pro Thread.

Auch die Erstellung eines Threads und dessen Beendigung benötigen Zeit zur Synchronisation mit dem Betriebssystem. Daher ist es aus Performancegründen ratsam, einen sogenannten Thread-Pool anzulegen. Dabei handelt es sich um eine Gruppe fertiger Threads, denen ein eigener Scheduler Aufgaben zuweist. Allerdings hilft auch ein Thread-Pool mit k Threads nichts, wenn diese alle gerade blockierenden IO durchführen. Daher ist es wichtig, die Größe des Thread-Pools richtig zu wählen.

Waiting und Computing

Programme lassen sich in einen wartenden Anteil W ("waiting") und einen rechnenden Anteil C (“computing”) unterteilen. Bei einer optimal implementierten Matrizenmultiplikation beispielsweise arbeitet der Prozessor ununterbrochen, weil alle Daten verfügbar sind und W = 0 sowie C = 1,0 sind. Programme mit W = 0 nennt man auch CPU-bound oder computation bound.

Bei einem typischen Web-Client zeigt sich hingegen die umgekehrte Situation: W >> C führt zu langen Wartezeiten und wenig Rechenaktivität der CPU. Hier gibt es zwei Möglichkeiten, zu warten: Bei "bandwidth bound" ist der Übertragungskanal voll ausgelastet, etwa bei einem Download von einem schnellen Fileserver. Ist der Übertragungskanal noch nicht ausgelastet, aber die Daten kommen nur langsam vom Server, spricht man von "latency bound".

Das Verhältnis W/C beeinflusst die optimale Größe eines Threadpools (vergleiche [1]):

Nthreads = NCPU * U_CPU * (1 + W/C)

Hierbei ist NCPU die Anzahl der Kerne und U_CPU die gewünschte Auslastung des Systems (von 0,0 bis 1,0).

Mit NCPU = 8 und U_CPU = 1,0 (volle Auslastung) lässt sich anhand der folgenden Beispieltabelle einfach erkennen, dass die Anzahl der Threads in einem Pool umso größer sein muss, je höher das Verhältnis W/C ausfällt.

W	C	N_threads
0	1	8
1	1	16
1	2	12
2	1	24
10	1	88
100	1	808
1000	1	8008

Da aber, wie bereits erwähnt, jeder Thread ein gewisses Maß an Speicherressourcen belegt, lassen sich nicht beliebig viele anlegen. Das Ziel der Performanceoptimierung ist daher, das Verhältnis von W/C zu minimieren.

Und was hat das mit Koroutinen zu tun?

Eine Koroutine ist eine Funktion, die an sogenannten Unterbrechungspunkten (suspend points) ansetzen (im LLVM-Kontext suspension points genannt). Koroutinen verfügen über einen raffinierten Mechanismus, der es ihnen erlaubt, statt zu warten, die Kontrolle zurückzugeben, um später genau an der gleichen Stelle die Berechnung wieder aufzunehmen. Statt auf das Fertigstellen des IOs zu warten, signalisiert die Koroutine, dass sie unterbrochen werden könnte. Der Scheduler schaltet dann zu einer anderen Koroutine um. Dadurch tragen Koroutinen zur Reduzierung von Wartezeiten bei und verkleinern das Verhältnis von W/C.

Um Koroutinen genauer zu verstehen, ist es ratsam, Schritt für Schritt in die Details zu schauen und mit den sogenannten Generatoren und yield-Funktionen zu beginnen. Eine Generator-Funktion erzeugt eine Collection mit nichtstrikter Auswertung – man spricht auch von "lazy Listen". Der folgende Beispielcode (der sich im Browser ausführen lässt) erstellt eine Sequence namens ps mit den Potenzen von 2^i für i=1 … und gibt anschließend die ersten fünf Werte aus:

val ps: Sequence<Int> = sequence {
    var i = 1
    while (true) {
          print("Gen $i ")
        yield(i)
        i *= 2
    }
}
for (i in ps.take(5)) {
    print("Use $i ")
}

Dabei ist zu beachten, dass das Erzeugen nur bei Bedarf elementweise erfolgt, denn es wird die folgende Ausgabe erzeugt:

Gen 1 Use 1 Gen 2 Use 2 Gen 4 Use 4 Gen 8 Use 8 Gen 16 Use 16 

In der traditionellen Programmierung löst die Berechnung von ps eine Endlosschleife aus. Die Funktion yield hingegen fügt das Element der Sequence hinzu und gibt die Kontrolle wieder an den Aufrufer ab. Sobald in der for-Schleife dann ein Zugriff auf das nächste Element erfolgt, kann mit dem Statement, dass auf yield folgt, weitergemacht werden.

• Der lokale Zustand, im obigen Beispiel die Variable i, bleibt zwischen zwei Aufrufen persistent.
• yield ist eine Art erweitertes return. Im Gegensatz zu return, das eine Funktion für immer verlässt, erlaubt yield, wieder am gleichen Punkt in die Funktion einzusteigen.

Zusammenfassend lässt sich sagen, dass yield die Komplexität des Unterbrechens und der Wiederaufnahme einer Berechnung inklusive Herstellung des Zustands kapselt. Generatoren mit yield finden sich auch in anderen Programmiersprachen wie JavaScript (ab ES6), Python 3, C# und Lua sowie der Game-Engine Unity.

Produzenten und Konsumenten

Generatoren sind der einfachste Fall einer Koroutine und heißen daher oft auch Semi-Koroutinen. Die eigentlichen Koroutinen gehen noch einen Schritt weiter: Anstatt mit yield direkt an den aufrufenden Code zurückzugeben, schaltet sich ein Scheduler/Dispatcher dazwischen, der eine beliebige andere Koroutine ausführen kann.

Die "lazy Liste" aus dem obigen Beispiel ist die einfachste Variante des Produzenten-Konsumenten-Patterns. Mit Koroutinen lassen sie sich verallgemeinern. Die folgende Funktion sendet analog zur obigen Generator-Funktion die Potenzen an einen sogenannten Channel:

suspend fun produce(channel: SendChannel<Int>){
    var i = 1
    while (true) {
        print("G $i,")
        channel.send(i)
        i *= 2
    }
}

Die Funktion channel.send() ist eine unterbrechbare Funktion (suspending function), sobald die Buffergröße des Channels erreicht ist. So lassen sich Endlosschleifen vermeiden. Unterbrechbare Funktionen sind in Kotlin explizit durch das Schlüsselwort suspend zu kennzeichnen. Programmierer werden dadurch unmittelbar auf eine mögliche nebenläufige Auswertung aufmerksam gemacht.

Um die auf diesem Wege produzierten Werte zu verwenden, kommt analog die folgende Funktion consume() zum Einsatz:

suspend fun consume(id: String, channel: ReceiveChannel<Int>) {
    repeat(2) {
        val v = channel.receive()
        print("C$id $v,")
        delay(100L) // äquivalent zu Thread.sleep() aber "suspendable"
    }
}

Das Lesen des Werts v übernimmt channel.receive(). Falls zu diesem Zeitpunkt der Channel leer ist, kommt es zur Unterbrechung der Funktion und der Ausführung einer anderen Koroutine – im Beispiel der Produzent.

Mit folgendem Code lässt sich schließlich ein Channel erstellen, über den ein Produzent und die zwei Konsumenten A und B kommunizieren:

val channel = Channel<Int>(Channel.RENDEZVOUS)
launch {  // starte Koroutine für Produzent
    produce(channel)
}
launch { // starte Koroutine für Konsument A
    consume("A", channel)
}
launch { // starte Koroutine für Konsument B
    consume("B", channel)
}

Im vorliegenden Fall ist der Kanal ein sogenannter Rendevouz-Kanal, weil er eine Buffergröße von 1 hat und send und receive daher sofort unterbrechen, falls sich bereits ein Element im Kanal befindet, beziehungsweise wenn noch kein Element im Kanal enthalten ist. Mit launch lassen sich die drei Koroutinen starten: ein Produzent und zwei Konsumenten. Damit sich die beiden Konsumenten in dem Beispiel verschachteln (interleaved) lassen, definiert delay() eine kurze Wartezeit zum Unterbrechen eines der Konsumenten.

Das obige Programm (das sich ebenfalls im Browser nachvollziehen lässt), erzeugt dann beispielsweise die folgende Ausgabe:

G 1,CA 1,G 2,G 4,CB 2,CA 4,G 8,CB 8,G 16,

Hierbei ist zu beachten, dass die Ausgaben nicht zwingend in der richtigen Reihenfolge stehen, weil println nicht atomar, das heißt in einem Schritt mit send oder receive ausgeführt wird. So folgt beispielsweise CB 2 in der Ausgabe auf G 4, wird aber sicherlich davor ausgeführt.

Einen detaillierteren Einblick in die Funktionsweise von Koroutinen in Kotlin gewährt Roman Elizarov, einer der Entwickler, im folgenden Video:

Koroutinen im Detail

Koroutinen zeichnen sich durch folgende Eigenschaften aus:

• Sie sind unterbrechbar an "suspension points".
• Sie nehmen ihre unterbrochene Berechnung wieder an der exakt gleichen Stelle mit dem gleichem Zustand auf.
• Sie kommunizieren am besten über Kanäle.
• Sie setzen die Kooperation mit dem Scheduler voraus. Sie werden nicht wie Threads einfach von außen unterbrochen, sondern müssen die Kontrolle freiwillig abgeben (kooperatives Multitasking).

Koroutinen sind unterdessen keine neue Erfindung, Melvin E. Conway erwähnte sie bereits 1963 zum ersten Mal in seinem Artikel Design of a Separable Transition-Diagram Compiler. Später erfolgte ihre Implementierung in Simula (1967) und Erlang (1986) sowie schließlich 2009 in Go. Bis dahin hatten es Koroutinen nie richtig geschafft, sich im Mainstream der Programmierfunktionen zu etablieren. In einführenden Lehrbüchern zur Nebenläufigkeit (siehe [2]) sind sie nicht einmal erwähnt.

Go und die Goroutinen

Der Verdienst für das Revival der Koroutinen ist sicherlich der Programmiersprache Go und deren Goroutinen zuzuschreiben. Im Rahmen der Google I/O 2012 präsentierte Rob Pike, einer der Go-Entwickler, die in der Programmiersprache unter der Bezeichnung Goroutinen implementierten Concurrency Patterns.

Der folgende Go-Code setzt das obige Kotlin-Beispiel mit einem Produzenten und zwei Konsumenten um:

package main

import (
    "fmt"
    "strconv"
    "time"
)

func produce(c chan int) {
    i := 1
    for j := 0; j < 5; j++ {
        fmt.Println("G " + strconv.Itoa(i))
        c <- i
        i *= 2
    }
}

func consume(id string, c chan int) {
    for i := 0; i < 2; i++ {
        v := <-c
        fmt.Println("C" + id + " " + strconv.Itoa(v))
        time.Sleep(100 * time.Millisecond)
    }
}

func main() {
    channel := make(chan int)
    go produce(channel)
    go consume("A", channel)
    go consume("B", channel)
    time.Sleep(time.Second)
}

Eine Koroutine lässt sich in Go mit dem Statement go starten. Innerhalb der main-Funktion (die ebenfalls eine Goroutine ist) starten demnach drei Koroutinen. Das Sleep-Kommando am Ende ist notwendig, damit die Ausgaben angezeigt werden. Aus einem Kanal chan kann mit <-c gelesen und mit c <- geschrieben werden.

Wie das Beispiel zeigt, sind Koroutinen in Go und Kotlin auf den ersten Blick sehr ähnlich. Das erleichtert den Einstieg, wenn man bereits eine der Varianten kennt. Allerdings liegt der Teufel im Detail, denn unter der Haube gibt es doch größere Unterschiede.

Weitere Sprachen

Koroutinen stehen auch in vielen anderen Sprachen wie Python, C#, Ruby, Lua, Erlang und F# zur Verfügung. Die einzelnen Implementierungen unterscheiden sich zum Teil jedoch deutlich voneinander. So gibt es beispielsweise verschiedene Ansätze, die entweder auf eigene sogenannte Green-Threads aufbauen oder aber Threads nutzen, die das Betriebssystem zur Verfügung stellt. Eine detaillierte Diskussion der Koroutinen-Implementierungen würde den Rahmen des Artikels sprengen. Eine Übersicht der Implementierung findet sich beispielsweise bei Wikipedia.

Das LLVM-Projekt bietet Werkzeuge und Bibliotheken zur Erstellung von Compilern an, darunter Clang. Seit Version 5 unterstützt dieser Compiler Koroutinen experimentell. Dieser Vorstoß lässt sich durchaus als Vorbereitung darauf interpretieren, dass Koroutinen ab dem C++20-Standard offizielle Unterstützung erfahren.

Fazit

Koroutinen bieten die Möglichkeit, nebenläufige Programme modular, wartbar und skalierbar zu implementieren. Da sie das Verhältnis W/C reduzieren, lassen sich deutlich mehr Requests pro Sekunde bearbeiten. Darüber hinaus zeigen Programme mit Koroutinen häufig eine bessere Auslastung der CPU.

Koroutinen kommen in den letzten Jahren immer öfter zum Einsatz. Zuerst unter den Go-Entwicklern, dank Kotlin nun aber auch in der JVM-Welt und auf Android-Geräten. Im Zuge der offiziellen Aufnahme in den C++20-Standard stünde Koroutinen schließlich das Gros der Plattformen offen.

Koroutinen sind jedoch keine "niedrig hängenden Früchte", da sich ihre Funktionsweise grundlegend von Threads unterscheidet und es an Best Practises mangelt. Softwareentwickler benötigen Einarbeitungszeit, um optimalen Nutzen aus ihnen ziehen zu können. Insbesondere im Hinblick auf die Performance-Optimierung sind detaillierte Kenntnisse des Koroutinen-Schedulers unabdingbar.

Jörn Dinkla
ist Software-Entwickler und Berater bei ThoughtWorks Deutschland.

Quellen:

1. Brian Goetz et al.; Java Concurrency in Practice; Addison-Wesley, 2006
2. Butcher, Paul; Seven Concurrency Models in Seven Weeks; Pragmatic Programmers, 2014

(map)