Macht euch nicht über den Happy Fun Branch Predictor lustig (2023)

 (mattkeeter.com)
1 Punkte von GN⁺ 2024-07-05 | 1 Kommentare | Auf WhatsApp teilen
  • Eine Optimierung, die in AArch64-Assembly eine Verzweigung in einer Schleife einsparen sollte, wurde stattdessen 4-mal langsamer; die Ursache war, dass ein bl/ret-Call-Return-Paar asymmetrisch verwendet wurde und dadurch der Branch Predictor verwirrt wurde
  • Der ursprüngliche Code verzweigt pro Schleifendurchlauf zweimal mit bl foo und b loop, während der geänderte Code mit einem einmaligen bl loop x30 fixiert und mehrere ret an dieselbe Adresse zurückkehren lässt, um die Zahl der Branches zu reduzieren
  • Beim Addieren eines Arrays mit 1024 float-Werten auf einem M1 Max brauchte der normale bl/ret-Code 969 ns, die Struktur mit einem bl und mehreren ret dagegen 3,85 µs; ersetzt man ret durch br x30, erholt sich die Laufzeit auf 913 ns
  • Performance Counter in Instruments zeigten beim Summieren von 1 Milliarde Elementen, dass die Fehlvorhersagen für Return-Branches in der asymmetrischen bl/ret-Struktur bei etwa 93 % lagen; auch FETCH_RESTART, MAP_DISPATCH_BUBBLE und MAP_REWIND stiegen stark an
  • Schnellere Implementierungen reichen von Inlining von foo über Rust iter().sum() bis zu NEON SIMD und manuellem Loop Unrolling; die finale SIMD-Version kommt auf 94 ns, kann wegen geänderter Reihenfolge der Gleitkomma-Additionen aber andere Ergebnisse liefern

Ein unerwünschter Effekt in einer AArch64-Schleife

  • Die Beispielfunktion läuft über ein float-Array, übergibt jeden Wert an foo, und foo aktualisiert den akkumulierten Wert g
  • Eine einfache AArch64-Übersetzung hat folgenden Ablauf
    • Am Schleifenanfang wird geprüft, ob n == 0 ist
    • Mit ldr s1, [x0], #4 wird der Wert gelesen
    • Mit bl foo wird die Subroutine aufgerufen
    • Das ret in foo kehrt zur Anweisung nach bl zurück
    • Mit b loop wird wieder zum Schleifenanfang gesprungen
  • foo ist fast eine naked function, die denselben Stack Frame und dieselben Register wie die Elternfunktion verwendet, s1 liest und in s0 akkumuliert

Die Rollen von bl und ret

  • bl ist die Anweisung branch and link: Sie springt zum angegebenen Label und speichert dabei die Adresse der nächsten Anweisung im Link Register lr bzw. x30
  • ret springt zu der Adresse, die im Link Register steht
  • In der ursprünglichen Struktur passen bl foo und ret zusammen, und ret kehrt immer zur Anweisung direkt nach diesem bl zurück

Die gescheiterte Optimierung „einen Branch einsparen“

  • Die geänderte Struktur versucht, einen Branch in der Schleife einzusparen, ohne foo zu ändern
    • Am Funktionsanfang wird mit bl loop aufgerufen, wodurch die Startadresse von loop in x30 abgelegt wird
    • Nach Prüfung der Abbruchbedingung fällt der Code ohne separaten Branch in den Code von foo durch
    • Das ret in foo kehrt zu loop zurück, dessen Adresse in x30 steht
  • In dieser Struktur ändert sich x30 im Schleifenkörper nicht, daher kehren die wiederholten ret immer an dieselbe Adresse zurück
  • Das einfache foo ist nur eine einzeilige Routine, die wie folgt einen float addiert
foo:
    fadd s0, s0, s1
    ret
  • In diesem Fall berechnet die gesamte Funktion die Summe des eingegebenen float-Arrays

Benchmark-Ergebnisse und Branch-Prediction-Problem

  • Mit criterion wurde auf einer M1-Max-CPU ein Array mit 1024 Elementen benchmarked
    • Normales bl/ret: 969 ns
    • Ein bl, mehrere ret: 3,85 µs
  • Der Code, der einen Branch einspart, ist etwa 4-mal langsamer als der ursprüngliche Code mit zwei Branches
  • Cliff und Dan vermuteten, dass der Branch Predictor durch das nicht zusammenpassende bl/ret-Paar verwirrt wurde
  • Laut ARM-Dokumentation lässt RET den Prozessor eine Funktionsrückkehr erkennen und ermöglicht so genauere Branch Prediction
    • BR LR kann funktional dasselbe leisten
    • RET ist jedoch eine separate Anweisung, die der Prozessor als Funktionsrückkehr erkennen kann
    • Wenn die Branch Prediction stimmt, gelangen die richtigen Anweisungen in die Pipeline, und Wartezeit auf Anweisungen aus dem Speicher wird vermieden

Return Address Stack und das Experiment mit br x30

  • Der Branch Predictor hält intern möglicherweise einen Stack von Funktions-Rücksprungadressen vor
    • Bei der Ausführung von bl wird die Rücksprungadresse auf den Stack gepusht
    • Bei ret wird angenommen, dass zur Rücksprungadresse des jüngsten bl zurückgekehrt wird
    • Auf Basis dieser Adresse werden Prefetching und spekulative Ausführung gestartet, danach wird sie vom Stack gepoppt
  • Dieses Verfahren funktioniert gut, wenn bl/ret als Paar zusammenpassen
  • Wenn mehrere ret wiederholt dieselbe Adresse verwenden, können Vorhersagen fehlschlagen und nutzloses Prefetching, falsche spekulative Ausführung sowie Pipeline-Stalls oder Flushes entstehen
  • Auf Dans Vorschlag hin verschwand der Performance-Einbruch, als ret durch br x30 ersetzt wurde
    • Normales bl/ret: 969 ns
    • Ein bl, mehrere ret: 3,85 µs
    • Ein bl, mehrere br x30: 913 ns
  • Die Version mit br x30 ist etwas schneller als der ursprüngliche Code, weil sie pro Schleifendurchlauf nur einen Branch ausführt

Performance Counter in Instruments

  • Mit Instruments wurden die Performance Counter der ersten beiden Programme geprüft
  • Gemessen wurde während des Summierens eines Arrays mit 1 Milliarde Elementen
  • Beim asymmetrischen bl/ret traten bei Return-Branches etwa 93 % Fehlvorhersagen auf
Counter Normales bl/ret Ein bl, mehrere ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928.644.975
FETCH_RESTART 61.121 987.765.276
MAP_DISPATCH_BUBBLE 1.155.632 7.350.085.139
MAP_REWIND 6.412.734 2.789.499.545
  • Apple dokumentiert diese Counter nicht vollständig
  • Die anderen Counter werden als Downstream-Effekte schlechter Branch Prediction vermutet
    • FETCH_RESTART: möglicherweise fehlerhaftes Prefetching
    • MAP_DISPATCH_BUBBLE: möglicherweise mit Pipeline-Stalls verbunden
    • MAP_REWIND: möglicherweise falsche spekulative Ausführung, die zurückgespult werden muss

Wege zu mehr Geschwindigkeit

  • Das Beispiel ist Lehrcode, und der Grund dafür, dass foo eine Subroutine ist, liegt eher in der erklärenden Struktur als in „maximal schnellem Code“
  • Wenn der Inhalt von foo zur Build-Zeit bekannt und kürzer als die maximale Sprungdistanz ist, können bl und ret vollständig entfernt und inline ersetzt werden
    • Dadurch wird es von 969 ns auf 911 ns etwa 6 % schneller
  • Schreibt man es in Rust schlicht als f.iter().sum(), sinkt die Laufzeit auf 833 ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD und manuelles Loop Unrolling

  • Die manuelle AArch64-SIMD-Implementierung besteht aus drei Schleifen
    • loop: addiert einzelne Werte zu s0, bis die Zahl der verbleibenden Werte ein Vielfaches von 4 ist
    • simd: addiert 4 Werte auf einmal in das Vektorregister v1 und wiederholt dies, bis die Zahl der verbleibenden Werte ein Vielfaches von 8 ist
    • simd2: rollt simd um den Faktor 2 aus, verarbeitet pro Iteration 8 Werte und summiert in v1 und v2
  • Am Ende der Funktion werden die Werte aus v1 und v2 in s0 akkumuliert und zurückgegeben
  • Type Punning behandelt x0, das ein float* ist, wie ein double*, um 128 Bit, also 4 float-Werte, als d3 und d4 zu lesen
    • mov v3.d[1], v4.d[0] verschiebt die 64 Bit von d4 in die oberen 64 Bit von v3
    • In fadd v1.4s, v1.4s, v3.4s sorgt das Suffix .4s dafür, dass die Daten wie vier float-Werte behandelt werden
  • Diese SIMD-Implementierung läuft in 94 ns und ist damit etwa 8,8-mal schneller als die zuvor beste Rust-Version mit 833 ns

Gesamte Performance-Übersicht und Hinweis

Implementierung Zeit
Normales bl/ret 969 ns
Ein bl, mehrere ret 3,85 µs
Ein bl, mehrere br x30 913 ns
Gewöhnliche Schleife mit b 911 ns
Neu in Rust geschrieben 833 ns
SIMD + manuelles Loop Unrolling 94 ns
  • Der SIMD-Code ändert die Reihenfolge der Gleitkomma-Additionen
  • Für Gleitkomma-Addition gilt das Assoziativgesetz nicht, daher liefert die SIMD-Version möglicherweise nicht dasselbe Ergebnis wie der lineare Code
  • Das ist vermutlich auch der Grund, warum der Compiler für die Summierung keine SIMD-Anweisungen erzeugt hat
  • Der gesamte Code ist auf GitHub veröffentlicht
  • Auf einer ARM64-Maschine lässt sich der Benchmark mit cargo bench reproduzieren

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-05
Hacker-News-Kommentare

  • Der letzte Optimierungscode summiert ein Array aus 1024 32-Bit-Gleitkommazahlen in 94 ns
    In diesen 94 ns hätte der alte 1-MHz-6502 gerade erst angefangen zu überlegen, ob er dem Speicherchip wohl ein Signal schicken soll, um das erste Byte des ersten Programmbefehls zu holen
    Das setzt allerdings vollständig voraus, dass dieser Code komplett im Cache läuft. Andernfalls hätte selbst der im Artikel erwähnte leistungsstarke M1 Max stillgestanden und auf den ersten Speicherzugriff gewartet. DRAM ist langsam

    • Ein Glück, dass die gesamte L1-Cache-Größe inzwischen so groß ist wie der gesamte Speicher, den ein 6502 adressieren konnte. Wir leben wirklich in erstaunlichen Zeiten

  • Raymond Chen hat im Grunde schon vor fast 20 Jahren dasselbe behandelt: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Als jemand, der die gedruckten Handbücher zur Intel-x86/64-Befehlsreferenz besitzt, die sogenannten dicken blauen Bücher, und Datenblätter sowie Dokumentation aufmerksam liest, bin ich immer vorsichtig, wenn ich höre: „Intuitiv würde man X erwarten, aber es passiert Y“
      Abgesehen von einem grundlegenden Verständnis der Halbleitereigenschaften von Silizium und des Dotierens gibt es hier fast nichts Intuitives. Wenn man nicht das Schaltbild des Dies, die Verdrahtung und die Pfade gesehen hat, gibt es kaum einen Grund anzunehmen, dass A schneller als B ist, sofern Ingenieure und Datenblatt das nicht ausdrücklich sagen. Bei ARM gilt das meiner Meinung nach noch mehr
    • Der Beitrag von Raymond Chen ist großartig und liefert einen guten Kontext für die Einordnung dieses Artikels
      Was dieser Artikel zusätzlich zeigt, ist die einfache Korrektur, ret durch eine andere br-Instruktion zu ersetzen. Damit wird das Paar wieder „symmetrisch“, und man kann etwas schnelleren Code bekommen, ohne den Branch Predictor kaputtzumachen
    • Raymond Chen ist wirklich ein Schatz. Ich bin dankbar, dass Microsoft ihm den Freiraum gibt, weiter zu bloggen, und ich lerne dort enorm viel
    • Bei aktuellen x86-Prozessoren scheint das nicht mehr zu stimmen: https://news.ycombinator.com/item?id=40767676

  • Natürlich ist alles möglich, und eine gewöhnliche Schleife zur Arraysumme weist den Computer tatsächlich an, die Elemente einzeln aufzuaddieren
    Aber zum Beispiel mit SIMD vier Akkumulatoren parallel zu bilden und sie am Ende zusammenzuzählen, ist kaum falscher, als die Elemente einzeln zu addieren
    Bei Gleitkommasummen muss man grundsätzlich von einem Fehlerspielraum ausgehen, und jede Antwort innerhalb dieses Bereichs sollte gültig sein. Wenn man etwas Besonderes über die Eingabe-Gleitkommazahlen weiß, sollte die Sprache Mittel bieten, diese Absicht explizit auszudrücken. Da die einfachste Schleife der Standard ist, sollte sie standardmäßig meiner Ansicht nach auch die beste Performance liefern

    • Selbst für die einfache Aufgabe, eine Liste von Zahlen zu addieren, gibt es überraschend viele Summationsalgorithmen
      Die naive Methode, sie in einer Schleife nacheinander zu addieren, ist naheliegend, aber es gibt ausgefeiltere Verfahren mit besseren Schranken für den gesamten akkumulierten Fehler; ein bekanntes Beispiel ist die Kahan-Summation: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Bei Streaming-Daten bleibt einem womöglich nichts anderes übrig, als einzeln zu addieren. Wenn man aber N Puffer fester Größe verwenden kann, stellt sich die Frage, welche Teilmengen bei Eingang neuer Zahlen zu Teilsummen zusammengefasst werden sollen, wie diese zur Gesamtsumme addiert werden und ob diese Wahl eine nachweisbare Verbesserung des Fehlers bringt
    • Wenn sich die Größenordnungen der Gleitkommawerte stark unterscheiden, wird das zu einem ernsten Problem
      Berechnet man zum Beispiel [1e50, -1e50, 1e3, 1e3] als (((1e50 + -1e50) + 1e3) + 1e3), erhält man 2e3, aber bei ((1e50 + 1e3) + (-1e50 + 1e3)) kommt 0 heraus
      Ähnlich ist es, wenn man viele kleine Werte zu einem großen addiert: (((1e3 + 1e3) + 1e3) ... + 1e50) und (((1e50 + 1e3) + 1e3) ... + 1e3) unterscheiden sich erheblich
    • Es gibt viel „sollte“, aber in der Praxis passiert das fast nie. Die ursprüngliche Formel liefert nur die Reihenfolge der arithmetischen Operationen
      Wenn arithmetische Ergebnisse zwischen Builds nicht stabil sind, ist das ein absoluter Albtraum. Es darf nicht sein, dass man dieselbe Eingabe mit neu gebauter Software ausführt und andere Ergebnisse bekommt
      Ich habe auch schon den alten Intel-Sonderfall erlebt: Die FPU verwendete intern 80-Bit-Register, schrieb aber 64 Bit in den Speicher. Wenn sich also der Zeitpunkt änderte, zu dem Register gefüllt oder geleert wurden, änderte sich auch der Rundungszeitpunkt und damit das Ergebnis. Man kann beim Programmstart ein globales FPU-Flag setzen, um Rundung bei jeder Operation zu erzwingen
    • Wenn man Gleitkommawerte sortiert, verringert sich der Fehler. Deshalb können mehrere Akkumulatoren meiner Ansicht nach die Genauigkeit verschlechtern. Sortierte Daten sind auch keineswegs selten
      Es gibt immer eine richtige Antwort, und ich finde, der Compiler sollte zumindest standardmäßig keine falschen Änderungen vornehmen. Möglichkeiten für Programmierer, ihre Absicht klarer auszudrücken, sind allerdings immer willkommen
    • Viel Code verlässt sich darauf, dass Gleitkommaoperationen innerhalb einer bestimmten Instruction Set Architecture deterministisch sind
      Die Anwendung von SIMD auf Gleitkommaschleifen hätte zwar zum Standard werden können, würde aber viel bestehenden Code brechen und die Ausgabe oft nichtdeterministisch verändern, weshalb das eine Funktion ist, die der Programmierer explizit auswählen muss
      Außerdem wissen viele Programmierer das möglicherweise gar nicht, sodass sie bei float Sum(float[] values) womöglich gar nicht erkennen würden, dass veränderte Rückgabewerte durch Vektorisierung entstehen. Deshalb verwendet etwa die .NET-Standardbibliothek SIMD für integers.Sum(), aber nicht für floats.Sum()

  • Ich habe nur die Zeile gelesen: „Nachdem das Schleifenende geprüft wurde, fällt es ohne Verzweigung direkt in die Funktion foo hinein“, und dachte sofort: „Ah, das ist also das Problem.“
    Ich hatte eine tiefgehende Diskussion über ausgefeilte Heuristiken von Branch Predictors erwartet, aber letztlich war es einfach ein Verstoß gegen grundlegende Heuristiken.
    Man sollte nicht glauben, mit nicht zusammenpassenden call-/ret-Befehlen enorme Geschwindigkeitsgewinne erzielen zu können. Dass der Branch Predictor einen Shadow Stack für Rücksprungadressen führt, ist seit Jahrzehnten üblich.

    • Es ist gut, die Funktionsweise von Branch Predictors genau zu kennen, aber viele Leute tun das nicht, und für sie kann das neue und vielleicht nützliche Information sein. Der Artikel war einfach nicht für dich gedacht, und das ist auch in Ordnung.
    • Auf Systemen mit einem Shadow Call Stack auf Architekturebene als Sicherheitsfunktion kann das die Programmausführung noch grundlegender kaputtmachen, also Abstürze verursachen.
    • Einerseits ist das Designziel von RISC, die Performance von kompiliertem Code auf Kosten der meisten anderen Faktoren zu maximieren.
      Deshalb sollten solche Risiken dokumentiert sein, aber Designer sollten davon ausgehen können, dass jemand, der Assembler direkt schreibt, die Dokumentation gelesen hat.
      Andererseits schrieb Sophie Wilson ursprünglich die BBC-BASIC-Implementierung für ARM, aber damals gab es noch keine Branch Predictors. Auch wenn wegen 32 Bit andere Regeln gelten, wäre interessant, wie AArch64 Code verlangsamt, wenn sich architektonische Annahmen ändern.
    • Trotzdem war es ein nützlicher Artikel, weil er auch gezeigt hat, wie diese und andere Optimierungen tatsächlich erreicht wurden.

  • Das ist eine Anspielung auf den klassischen SNL-Sketch „Do not taunt happy fun ball“: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • Wenn aus dem happy fun Branch Predictor Rauch austritt, sollte man sofort evakuieren.
    • Wenn man die Zeile „Happy Fun Ball has been shipped to our troops in Saudi Arabia and is being dropped by warplanes over Iraq“ sieht, denkt man unweigerlich: „In welchem Jahr sind wir eigentlich!?“
    • In 16 Bundesstaaten ist es immer noch legal: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • Man sollte nicht übersehen, dass es ein Artikel von 2023 ist. Inzwischen ist er schon etwas veraltet, und seit Rust 1.78 nutzt der Compiler aggressiveres Loop-Unrolling und etwas SIMD: https://godbolt.org/z/zhbobW7rr
    Im Original hieß es „Wenn man sich den Assembler ansieht, wird bereits Loop-Unrolling gemacht“, mit einem Link auf https://godbolt.org/z/Kv77abW6c, was jedoch das sich ständig ändernde „Rust Nightly“ verwendete. Inzwischen wird noch stärker unrolled.
    Loop-Unrolling begann ab Rust 1.59: https://godbolt.org/z/5PTnWrWf7
    Laut GitHub-Code wurde Rust 1.67.0-nightly, Version 2022-11-27, verwendet.

    • Ich habe den Link aktualisiert, damit Rust 1.67 explizit ausgewählt ist.
    • Das Rust 1.67.0, das der Originalartikel offenbar gesehen hat, liefert dieses Ergebnis: https://godbolt.org/z/4Y61d9seh
      Ich habe den Benchmark auf derselben Hardware selbst mit dem aggressiven Loop-Unrolling des aktuellen nightly Rust 1.81 laufen lassen, aber es gab keinen Unterschied; die Geschwindigkeit war dieselbe wie vor 1,5 Jahren.

  • Es ist ein Artikel von 2023. Die damalige Diskussion: https://news.ycombinator.com/item?id=34520498

    • Ausgeschrieben ist es die Diskussion vom Januar 2023 zu „Do not taunt happy fun branch predictor“, und es gab 171 Kommentare: https://news.ycombinator.com/item?id=34520498
      Dass es etwa ein Jahr später noch einmal gepostet wird, ist okay, und der Link auf den alten Thread ist für Leser gedacht, die noch neugieriger sind.

  • Ich bin mit ARM/ARM64-Assembler nicht besonders vertraut und war verwirrt, wie x0 inkrementiert wird.
    const float f = *data++; wird zu ldr s1, [x0], #4, und dieser Befehl scheint den Wert zu laden und gleichzeitig x0 um 4 zu erhöhen.
    Man kann offenbar auch negative Werte verwenden, also dürfte auch eine Rückwärtsiteration möglich sein. Ziemlich cool. In x86_64 gibt es meines Wissens keinen einzelnen Befehl, der Lesen und Inkrementieren zugleich erledigt.

    • lods und stos kombinieren jeweils Lesen/Schreiben mit einem Inkrement von rsi bzw. rdi. Es gibt auch movs, das beim Kopieren zwischen zwei Speicheradressen inkrementiert.
      Meist wird es zusammen mit rep verwendet, das rcx-mal wiederholt. Ein 10-Byte-memset kann zum Beispiel als mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb umgesetzt werden.
      Mit den Suffixen w, d, q wird jeweils um 2, 4 bzw. 8 Byte weitergerückt.

  • Der Artikel war gut, aber schade war, dass ständig zwischen µs- und ns-Einheiten gewechselt wurde, was Vergleiche beim Überfliegen der Tabellen erschwerte.

    • Auch der Wechsel mitten im Artikel von C zu Rust war etwas irritierend.

  • Es überrascht mich, dass vor der Optimierung des Codes nicht zuerst ein weniger cleverer Ansatz versucht wurde.
    Wenn man den Assembler umschreibt, braucht man am Schleifenende nur noch eine Verzweigung, und auch für X1 könnte man Vergleichssubtraktion und Dekrement statt getrennt mit einer einzigen ALU-Operation erledigen.
    Noch weitergehend könnte man foo einfach inlinen und auch den RET-Befehl weglassen, ganz ohne den Trick mit nicht zusammenpassendem BL/RET. Ich habe das nicht selbst gebenchmarkt, daher weiß ich nicht, wie viel schneller es tatsächlich wäre.

    • Da ist ein Tippfehler. Die Zeile mit cbnz müsste cbz heißen. CBZ verzweigt zu einem Label, wenn das Register 0 ist, und CBNZ verzweigt, wenn es nicht 0 ist.