Verspotte den fröhlichen, unterhaltsamen Branch Predictor nicht (2023)

Verspotte den fröhlichen Branch Predictor nicht

• In letzter Zeit wird viel AArch64-Assembly geschrieben
• Eine „clevere“ Idee, in einer Schleife einen Sprung zu entfernen, verschlechtert die Performance
• Dieser Fehler wird erklärt, damit andere ihn nicht ebenfalls machen

Codebeispiel

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

Übersetzung in AArch64-Assembly

// x0: const float* data
// x1: size_t n
// s0: zurückzugebender float
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // aus s1 lesen und in s0 akkumulieren
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Optimierungsversuch

• Die Anzahl der bl-Instruktionen sollte reduziert werden, um die Performance zu verbessern
• Stattdessen wurde die Performance schlechter

Performance-Vergleich

• Originalcode: 969 ns
• Optimierter Code: 3.85 µs

Ursachenanalyse

• Der Branch Predictor wird verwirrt, weil bl- und ret-Paare nicht zusammenpassen
• Laut der ARM-Dokumentation hilft die ret-Instruktion bei der Vorhersage von Funktionsrückgaben

Lösung

• br x30 statt ret verwenden
• Performance wiederhergestellt: 913 ns

Weitere Optimierung

• foo inline setzen, um die Performance zu verbessern
• Loop-Unrolling und SIMD-Instruktionen verwenden

Endgültige Performance

• SIMD + manuelles Loop-Unrolling: 94 ns

Fazit

• Den Branch Predictor nicht verwirren
• SIMD-Code ist schneller, aber da Gleitkommaaddition nicht assoziativ ist, können die Ergebnisse unterschiedlich sein

Meinung von GN⁺

• Dieser Artikel zeigt die Bedeutung von AArch64-Assembly-Optimierung sehr gut
• Das Verständnis der Funktionsweise des Branch Predictors ist für Performance-Optimierung unerlässlich
• Optimierungen mit SIMD-Instruktionen sind sehr effektiv, aber Genauigkeitsprobleme müssen berücksichtigt werden
• Mit High-Level-Sprachen wie Rust lässt sich die Performance durch Compiler-Optimierungen leichter verbessern
• Ein ähnliches Projekt ist Agner Fogs Leitfaden zur Assembly-Optimierung

[GN⁺]

Hacker-News-Kommentar

• Hat den Artikel zusammen mit Freunden aus der Apple-II-Ära zusammengefasst

  • Optimierter Code benötigt 94 Nanosekunden, um 1024 32-Bit-Gleitkommazahlen zu summieren
  • Ein 1-MHz-6502 würde in 94 Nanosekunden versuchen, das erste Byte der ersten Anweisung aus dem Speicher zu holen
  • Dieser Code liefert seine optimierte Leistung nur, wenn er aus dem Cache ausgeführt wird. DRAM ist langsam

• Raymond Chen hat dasselbe Thema schon vor fast 20 Jahren behandelt

  • Nach der Prüfung auf das Schleifenende geht es ohne Branch direkt in die Funktion foo
  • Das verstößt gegen grundlegende Vorhersageheuristiken
  • Dass Branch-Predictors einen Schatten-Stack von Rücksprungadressen pflegen, gibt es seit Jahrzehnten

• SIMD-Code kann Summen in anderer Reihenfolge ausführen, weil Gleitkommaaddition nicht assoziativ ist

  • Das könnte der Grund sein, warum der Compiler keine SIMD-Instruktionen erzeugt
  • Gleitkommasummierung hat grundsätzlich eine Fehlertoleranz, und jede Antwort innerhalb dieses Bereichs ist gültig
  • Bei speziellen Gleitkommaeingaben sollte die Sprache Mittel bereitstellen, dies explizit zu kodieren

• Seit Rust 1.78 verwendet der Compiler aggressiveres Loop-Unrolling und etwas SIMD

  • Loop-Unrolling begann mit Rust 1.59
  • Im Github-Code wurde die Version Rust 1.67.0-nightly verwendet

• Es gab Verwirrung darüber, wie sich x0 in ARM/ARM64-Assembly erhöht

  • Die Anweisung ldr s1, [x0], #4 lädt und erhöht dabei x0 um 4
  • Auf x86_64 gibt es keine einzelne Anweisung, die gleichzeitig lädt und erhöht

• Es war überraschend, dass zum Optimieren des Assembly-Codes keine weniger komplexen Methoden ausprobiert wurden

  • Man könnte den Assembly-Code so umschreiben, dass am Ende der Schleife nur ein einziger Branch nötig ist
  • Man könnte foo inlinen und die RET-Anweisung weglassen

• Es gab den Kommentar, dass der Autor nicht ständig die Einheiten hätte wechseln sollen