Protobuf mit mehr als 2 GB/s parsen: Warum ich in C Tail Calls lieben gelernt habe (2021)

• Tail Call: Ein Funktionsaufruf, der direkt vor der Rückgabe einer Funktion erfolgt. Wenn Tail-Call-Optimierung greift, wird der jmp-Befehl verwendet, um den Aufruf-Stack zu verkleinern.
• Vorteile:
  • Reduziert die Nutzung von Stack-Speicher von O(n) auf O(1).
  • Beseitigt den Performance-Overhead von Funktionsaufrufen und kann als effiziente iterative Kontrollstruktur verwendet werden.

Probleme der Interpreter-Schleife

• Probleme:
  • Je größer eine Funktion wird und je komplexer der Kontrollfluss ist, desto schwieriger ist es, wichtige Daten in Registern zu halten.
  • Wenn schneller und langsamer Pfad vermischt werden, leidet die Code-Qualität.

Verbesserung der Interpreter-Schleife mit Tail Calls

• Lösung: Mit Tail Calls wird jede Aufgabe in kleine Funktionen aufgeteilt, und jede Funktion ruft die nächste Aufgabe per Tail Call auf.
• Vorteile:
  • Die Registerzuweisung lässt sich steuern.
  • Schneller und langsamer Pfad lassen sich trennen, sodass die Code-Qualität erhalten bleibt.
  • Unabhängige Befehlssequenzen können optimiert werden.

Grenzen

• Probleme bei nicht-Tail-Calls: Wenn nicht-Tail-Calls vorhanden sind, werden Stack-Frames erzeugt und Daten auf dem Stack gespeichert, was die Performance verschlechtert.
• Komplexe Ausnahmebehandlung: Wenn die Ausnahmebehandlung komplex ist, nehmen Codeduplizierung und Komplexität zu.
• Portabilitätsproblem: Da das Attribut musttail kein Standard ist, wird es nicht von allen Compilern unterstützt.

Zusammenfassung von GN⁺

• Tail-Call-Optimierung spielt eine wichtige Rolle für Performance-Verbesserungen und zeigt besonders beim Protobuf-Parsen große Wirkung.
• Diese Technik lässt sich auch auf wichtige in C geschriebene Sprachinterpreter anwenden, darunter Python, Ruby, PHP und Lua.
• Das Portabilitätsproblem des Attributs musttail bleibt eine offene Aufgabe.
• Projekte mit ähnlicher Funktionalität sind unter anderem LuaJIT und der WebAssembly-Interpreter wasm3.

[GN⁺]

Hacker-News-Kommentare

• Ein Vorschlag für den C-Standard enthält Tail Calls in der Form return goto (expression);

  • Im Vergleich zur Standardisierung von [[musttail]] ist dadurch die Lebensdauer lokaler Objekte garantiert, sodass keine umfassende Escape-Analyse nötig ist

• Für Rust-Enthusiasten gab es ein altes RFC zur Einführung des Schlüsselworts become

  • Es wurde verschoben, um sich auf die Ziele der Edition 2018 zu konzentrieren, wird aber in letzter Zeit erneut diskutiert
  • Es könnte wieder auftauchen

• In C++ werden Interpreter meist mit computed goto beschleunigt

  • Damit lassen sich Probleme mit Calling Conventions vermeiden
  • Sowohl ein computed-goto-Stil als auch ein Tail-Call-Stil können den Druck auf den Branch Predictor verringern

• Das Problem beim Wechseln des Kontexts mit Tail Calls ist, dass eine Funktion benötigt wird, die die Calling Convention verwendet

  • Dabei werden Register verschwendet, um den Zustand beim Verlassen der Funktion wiederherzustellen
  • Der Blog zum luajit-Remake bietet Alternativen und eine Analyse dazu

• Es wird gehofft, dass sich das Attribut [[musttail]] auf GCC, Visual C++ und andere populäre Compiler ausbreitet

  • Das Attribut [[musttail]] befindet sich im Prozess der Aufnahme in GCC

• Mit Verweis auf die C++-Unterstützung wird angemerkt, dass es in C++ kaum Tail Calls gibt

  • Wenn zum Beispiel ein Objekt einer Klasse mit Destruktor zurückgegeben wird, ist das kein Tail Call

• Es wird gefragt, was passiert, wenn in einer C++-[[musttail]]-Funktion eine Ausnahme geworfen wird

  • Es wird gefragt, ob der Exception-Stack dadurch vollständig getrennt wird

• Es wird angemerkt, dass einfache Beispiele für gute Code-Erzeugung kein __attribute__((musttail)) benötigen

  • Auf die Geschwindigkeit von Aufrufen von Fehlerbehandlungsfunktionen würde man wahrscheinlich keinen großen Wert legen
  • Eine bestimmte Struktur erzeugt zuverlässig eine Jump Table

• Es wird gefragt, wie schnell der Ansatz ist, bei dem ein per Trampolin zurückgegebener Funktionszeiger in einer äußeren Schleife aufgerufen wird

  • Dieser Ansatz hat den Vorteil von portablem C

• Es gibt die Bitte, ein Beispiel für mit [[musttail]] umhüllte Ausnahme-Pfade klarer zu machen

  • Es wird erklärt, warum [[musttail]] das Anlegen von Stack Frames und das Spilling von Registern verhindert
  • Stack Frames werden angelegt und Register nur dann gespillt, wenn der Ausnahme-Pfad tatsächlich aufgerufen wird
  • Da der Ausnahme-Pfad selten aufgerufen wird, hat das keinen großen Einfluss auf die Performance
  • Durch Branch-Prediction-Effekte kann schon die Möglichkeit zusätzlicher Arbeit den schnellen Pfad verlangsamen