Seite 2: Waiting und Computing

Inhaltsverzeichnis

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: