Ich bin heute auf ein schönes Beispiel gestoßen, das gut verdeutlicht, wie schwierig Optimierungen für Prozessoren seien können und dass manch scheinbare Verbesserung keine besseren Ergebnisse liefern muss. Ich stieß auf die Methode f32.clamp in der Standardbibliothek von Rust, die wie folgt umgesetzt ist:

pub fn clamp(self, min: f32, max: f32) -> f32 {
    assert!(min <= max);
    let mut x = self;
    if x < min {
        x = min;
    }
    if x > max {
        x = max;
    }
    x
}

Spontan war mein Gedanke, als ich den Code sah, dass man doch besser ein else if x > max verwenden sollte, da sich beide Fälle logisch ausschließen. Aber da diesen Code sicher schon sehr viele Leute begutachtet haben, ist es unwahrscheinlich, dass diese Möglichkeit der Verbesserung nicht bereits aufgefallen wäre, und daher habe ich nochmal darüber nachgedacht und die Sache genauer analysiert.

Assembler

Ein Prozessor arbeitet nicht mit Anweisungen wie match und struct, weshalb der Compiler – und genau das ist seine Aufgabe – die Rust-Anweisungen in Maschinenbefehle (Binärcode) umwandeln muss. Für diesen Binärcode gibt zum Glück auch eine lesbare Form: Assembler. Die Anweisungen sind meist Funktionen mit einem oder mehreren Parametern (auch Operanden genannt), die Konstanten, Registernamen oder Speicheradressen seien können. Assemblercode ist wesentlich primitiver als Programmcode in Hochsprachen, aber daher auch so schnell und vielfältig, dass damit unterschiedliche Programmiersprachen verwirklicht werden können und gleichzeitig Prozessoren ihre bekannte Leistungsfähigkeit erreichen.

Compiler müssen oft die Anweisungen der Programmiersprache in mehrere Prozessorbefehle übersetzen – es gibt auch den umgekehrten Fall, dass mehrere Anweisungen zu einem Prozessorbefehl werden, aber dies ist schwierig, wie sich auch später zeigen wird. Eine if-Anweisung zum Beispiel wird vom Prozessor durch einen Vergleich und einen Sprung für den Fall, dass der Vergleich nicht zugetroffen hat, umgesetzt. Aus if a < b { … } werden dann Maschinenbefehle dieser Art:

    cmp a, b            ; Vergleich von a mit b
    b.ge .NOT_MATCHED   ; Sprung (branch) zu NOT_MATCHED, falls a >= b (greater equal)
    …                   ; Code für den Fall a < b
.NOT_MATCHED:           ; Sprungstelle nach dem if
    …                   ; Code nach dem if { }

Es gibt noch viele Befehle, die auch von Prozessortyp zu Prozessortyp verschieden sind und zum Teil recht umfangreiche Berechnungen ausführen. Um sich den Assemblercode anzusehen, muss man den Compiler wie folgt aufrufen: rustc --emit asm --crate-type rlib -O prog.rs. Damit entsteht statt des Programms die Datei prog.s, in der der Assemblercode für das Programm steht. (durch -O wird der Code optimiert und kompakter, durch --crate-type rlib braucht man keine main-Funktion) Allerdings geht dies auch leichter und schöner mit dem Projekt Godbolt; hier ist das Projekt für die folgenden Beispiele.

Zurück zu Ausgangsfunktion clamp. Der Rust-Compiler (Version 1.50) erstellt daraus folgendes Assemblerprogramm1:

pub fn clamp(inp: f32, lower: f32, upper: f32) -> f32 {
    let mut x = inp;
    if x < lower {
        x = lower;
    }
    if x > upper {
        x = upper;
    }
    x
}

fcmp    s0, s1              ; vergleiche inp und lower
fcsel   s0, s1, s0, mi      ; x = if kleiner { lower } else { inp }
fcmp    s0, s2              ; vergleiche x und upper
fcsel   s0, s2, s0, gt      ; x = if größer { upper } else { x }
ret

Interessanterweise enthält der Code nicht die erwarteten Sprünge, denn es wird die komplexe Anweisung fcsel verwendet, die gemäß dem vierten Operanden den zweiten oder dritten in den ersten überträgt. Die ersten beiden Befehle entsprechen somit der mathematischen Operation max(inp, lower) und die folgenden beiden Befehle der Operation min(x, upper). Mit diesen lässt sich das Ergebnis tatsächlich ohne Sprünge ermitteln.

Sprünge sind schlecht für den Prozessor

Prozessoren sind sehr komplexe Bauteile. In der einfachsten Form kann man sich ein Rechenwerk, Register (für die Daten) und Anschlüsse an externe Komponenten (wie RAM und Festplatte) vorstellen. Dieser Aufbau wurde über die Jahrzehnte sehr stark erweitert und vom Rechenwerk gibt es mehrere Ausführungen und noch einige Spezialeinheiten für zum Beispiel Vektoren oder Kryptografie. Auch von den Registern gibt es intern mehr als von außen zugänglich sind. Solche erweiterten Prozessorarchitekturen nennt man superskalar.

Da durch mehrere Rechenwerke zeitgleich mehrere Operationen ausgeführt werden können, kann es dazu kommen, dass eine später begonnene Operation vor einer früheren fertig ist, weil sie weniger Rechenzyklen benötigte. Ein moderner Prozessor bearbeitet die Befehle intern also nicht immer in der Reihenfolge ab, wie es der Programmcode vorgibt, sondern kann die Befehle auch in gewissen Grenzen umordnen; dies bezeichnet man als out-of-order execution.

Wenn dann noch der Ablauf des Programmcodes variabel ist und durch bedingt Sprünge zwei Möglichkeiten für den nächsten Befehl bestehen, muss der Prozessor die Arbeit immer wieder unterbrechen, um auf das Ergebnis des Vergleichs zu warten. Es gibt auch die Möglichkeiten, dass beide Pfade bearbeitet werden und am Ende der falsche verworfen wird oder es wird eine Prognose getätigt, welcher Pfad wahrscheinlich genommen wird, und sollte sich später herausstellen, dass die Prognose falsch war, wir alles rückabgewickelt.

Diese drei Fälle verdeutlichen schon, zu welchen Schwierigkeiten Sprünge führen, weil sie immer wieder den linearen Arbeitsfluss stören. (Die Komplexität der Sprungvorhersage hat auch zu den gravierenden Sicherheitsproblemen Spectre und Meltdown vor allem bei Intel-Prozessoren beigetragen.) Ein Compiler wird daher alles tun, um zu verhindern, dass er Sprunganweisungen erzeugen muss.

Interessanter Weise kommt es bei dem Beispielprogramm mit einer else-Anweisung zu genau solch einem Sprung. Das Rust-Programm wird zu folgendem Assembler-Programm mit deutlich mehr Anweisungen übersetzt:

pub fn with_else(inp: f32, lower: f32, upper: f32) -> f32 {
    let mut x = inp;
    if x < lower {
        x = lower;
    } else if x > upper {
        x = upper;
    }
    x
}

    fcmp    s0, s1
    b.mi    .LBB1_3
    fcmp    s0, s2
    mov     v1.16b, v0.16b
    b.le    .LBB1_3
    mov     v1.16b, v2.16b
.LBB1_3:
    mov     v0.16b, v1.16b
    ret

Der naive Ansatz, die beiden logisch getrennten Fälle durch eine else-Anweisung zu trennen, führt zu einem wesentlich schlechteren Ergebnis – so kann man in die Falle tappen. Aber es kommt schlimmer bzw. besser.

Funktionale Variante

Als ich den Code von with_else dann betrachtet habe, dachte ich »so würde ich das doch nicht schreiben« und bin damit zu folgender Lösung gekommen:

pub fn functional(inp: f32, lower: f32, upper: f32) -> f32 {
    if inp < lower {
        lower
    } else if inp > upper {
        upper
    } else {
        inp
    }
}

Diese Form der Codeorganisation entspricht einer Verkettung der Operationen resp. Funktion von min(max(inp, lower), upper). Man nennt diese Form der Programmierung daher auch funktionale Programmierung, weil man keine Reihenfolge von Befehlen konstruiert (imperative Schreibweise), sondern Funktionsaufrufe ineinander verschachtelt (Operationen verkettet). Mit Rust lässt sich auch statt if-else die match-Anweisung verwenden, womit der Code noch mehr der mathematischen Schreibweise für Funktionsdefinitionen ähnelt:

pub fn with_match(inp: f32, lower: f32, upper: f32) -> f32 {
    match inp {
        x if x < lower => lower,
        x if x > upper => upper,
        x => x
    }
}

Für diese beiden Varianten erzeugt rustc 1.50 den gleichen Code wie für clamp:

    fcmp    s0, s2
    fcsel   s2, s2, s0, gt
    fcmp    s0, s1
    fcsel   s0, s1, s2, mi
    ret

Fazit

Optimierungen sind nicht einfach und nicht immer ist im Code einer Hochsprache zu erahnen, welche Prozessorbefehle der Compiler generieren wird. Auch ist den Prozessorbefehlen nicht immer anzusehen, wie performant sie sind und manchmal hängt dies auch von den vorangegangen und folgenden Befehlen ab.

Das Ergebnis kann auch von Compilerversion zu Compilerversion variieren bzw. kann eine Verbesserung für eine CPU-Architektur vorteilhaft, für eine andere nachteilig sein; wie man an den funktionalen Funktionen sieht, wenn man bei Godbolt die Intel-Architektur wählt. Wiederum ist der Assemblercode der Funktionen für die Intel-Architektur mit u32 (statt f32) gleich. Solche Optimierungen sind nicht einfach und es kommt sehr auf den Einzelfall an!

Daher sollte man sich nicht mit solchen Fragen herumschlagen und den Code in erster Linie in einer stimmigen und lesbaren Form schreiben. Sollte sich durch eine Analyse (z. B. mittels Profiling) ergeben, dass eine Codestelle optimiert werden muss, kann man sich das entsprechende Ergebnis in Assembler ansehen und nach Verbesserungsmöglichkeiten suchen.

Bemerkenswert ist aber, dass Rust durch die funktionale Schreibweise den Programmierer zu guten Ergebnissen und lesbarem Code verleitet.