Protobuf mit mehr als 2GB/s parsen: Entwurf eines Hochgeschwindigkeits-Interpreters in C mit Tail Calls (2021)

• Mit der Ergänzung von musttail in Clang lassen sich nun auch in C-artigen Sprachen garantierte Tail Calls nutzen; angewendet auf einen Protobuf-Parser wurde damit eine Leistung von mehr als 2GB/s demonstriert
• Der Kern besteht darin, Funktionsaufrufe eher wie jmp statt wie call zu machen, sodass sich die Stack-Nutzung bei aufeinanderfolgenden Aufrufen von O(n) auf O(1) reduziert und wie eine Schleife behandeln lässt
• Das Protobuf-Wire-Format interpretiert Tag/Wert-Paare und muss zu Feldern in beliebiger Reihenfolge verzweigen; damit hat die klassische Struktur aus while + switch ein ähnliches Optimierungsproblem wie die Opcode-Dispatch eines Interpreters
• Der experimentelle Parser von upb verbindet statt einer einzigen großen Funktion kleine Parserfunktionen per Tail Call und vermeidet auf dem schnellen Pfad Stack-Nutzung, Register-Spills sowie Prolog/Epilog
• Dieser Ansatz hat die Einschränkung, dass eingemischte Non-Tail-Calls die Codequalität stark verschlechtern und musttail eine nicht standardisierte Erweiterung ist; für den produktiven Einsatz eines schnellen Parsers braucht es daher Aufrufkonventionen und Maßnahmen zur Portabilität

---

Hochgeschwindigkeits-Protobuf-Parsing durch Clang musttail

• Dem Clang-Main-Branch wurde das Statement-Attribut [[clang::musttail]] / __attribute__((musttail)) hinzugefügt, das in C, C++ und Objective-C garantierte Tail Calls ermöglicht
• Tail Calls werden hier nicht als Technik aus der funktionalen Programmierung genutzt, sondern als Optimierungswerkzeug zur Senkung von Verzweigungskosten in Parsern und Interpretern
• Die Anwendung dieser Technik auf das Protobuf-Parsing demonstrierte in upb pull/310 eine Parsing-Leistung von mehr als 2GB/s
  • Vorgestellt wurde das als Ergebnis, das mehr als doppelt so schnell wie der bisherige Spitzenwert sei
  • Da mehrere Techniken gemeinsam dazu beigetragen haben, wäre die Aussage „allein Tail Calls machten es doppelt so schnell“ nicht korrekt
  • Tail Calls waren jedoch einer der entscheidenden Faktoren, die diese Leistungssteigerung ermöglichten
• Spätere Änderungen werden in A Tail Calling Interpreter For Python (And Other Updates) behandelt

Warum Tail Calls wie eine Schleife funktionieren

• Ein Tail Call ist der letzte Funktionsaufruf, den eine Funktion unmittelbar vor ihrer Rückkehr ausführt
• Wenn Tail-Call-Optimierung angewendet wird, erzeugt der Compiler statt eines normalen call eine jmp-Instruktion
  • Das Anlegen eines neuen Stack-Frames und das Speichern der Rücksprungadresse entfallen
  • Der Aufrufer f() springt direkt zum Aufgerufenen g()
  • g() kehrt dann direkt zu der Funktion zurück, die f() aufgerufen hatte
• Aufgrund dieser Eigenschaft können Tail Calls eine Schleifenstruktur ersetzen
  • Selbst bei n aufeinanderfolgenden Tail Calls sinkt die Stack-Nutzung von O(n) auf O(1)
  • Der Overhead von call entfällt, sodass sich Funktionsaufrufe wie gewöhnliche Verzweigungen behandeln lassen
• Die Idee ist nicht neu und reicht bis zu Guy Steeles Paper von 1977 und den „Lambda Papers“ aus den Jahren 1975 bis 1980 zurück
• Clang konnte Tail Calls bereits in optimierten Builds wie -O2 optimieren, aber das bisherige Verhalten war eher best effort
  • In nicht optimierten Builds konnte weiterhin ein echter call erzeugt werden
  • Um Tail Calls sicher als Schleifenstruktur nutzen zu können, muss die Optimierung in allen Build-Modi garantiert sein
  • musttail liefert genau diese Garantie

Der gleiche Engpass in Interpreter-Schleifen und Protobuf-Parsern

• Mike Pall von LuaJIT schrieb den LuaJIT-2.x-Interpreter nicht in C, sondern in Assembler, und sah darin einen wichtigen Grund für dessen hohe Geschwindigkeit
• C-Compiler stoßen im Hauptloop eines Interpreters vor allem auf zwei Probleme
  • Je größer die Funktion und je komplexer der Kontrollfluss, desto schwerer kann der Register-Allokator wichtige Daten in Registern halten
  • Wenn schneller und langsamer Pfad in derselben Funktion vermischt sind, verschlechtert der langsame Pfad auch die Codequalität des schnellen Pfads
• Auch das Protobuf-Wire-Format hat eine interpreterähnliche Struktur
  • Das Wire-Format besteht aus einer Folge von Tag/Wert-Paaren
  • Ein Tag enthält Feldnummer und Wire Type
  • Das Tag verhält sich ähnlich wie ein Opcode, der vorgibt, wie die zugehörigen Felddaten zu parsen sind
  • Feldnummern können in beliebiger Reihenfolge auftreten, daher muss der Code darauf vorbereitet sein, an nahezu jede Stelle zu dispatchen
• Klassische Protobuf-Parser nutzten meist eine Struktur mit switch innerhalb einer while-Schleife; über den Großteil der Existenz von Protobuf galt das als State of the Art
• In realen Parsing-Abläufen können an fast jedem Schritt Ausnahmen wie falscher Wire Type, beschädigte Daten oder das Erreichen des Pufferendes auftreten
  • Der schnelle Pfad sollte möglichst kurz und stabil bleiben
  • Schwierige Fälle benötigen größeren und komplexeren Fallback-Code und teils auch Out-of-Line-Funktionsaufrufe

Entwurf des Tail-Call-basierten upb-Parsers

• Der experimentelle Parser von upb verwendet nicht eine einzige große Parsing-Funktion, sondern trennt jede Operation in eine kleine Funktion auf
• Jede Funktion ruft die nächste Operation per Tail Call auf
  • Dank der x86-64-Aufrufkonvention werden gemeinsame Parsing-Argumente in Registern übergeben
  • Alle Parsing-Funktionen verwenden dieselbe Argumentmenge, um Datenbewegungen zwischen Aufrufen zu minimieren
• Die beispielhafte Parserfunktion für ein Fixed-Width-Feld mit 4 Byte arbeitet wie folgt
  • Sie dekodiert Feldinformationen aus data
  • Wenn der Wire Type nicht passt, macht sie MUSTTAIL return nach fallback()
  • Sie überspringt das Tag und speichert die Daten in der Nachricht
  • Danach liest sie das nächste Tag und tail-callt dispatch(), das zum passenden Feldparser verzweigt
• Der von Clang erzeugte Assembler enthält auf dem schnellen Pfad keinen Prolog/Epilog, keine Register-Spills und keine Stack-Nutzung
  • Die einzigen Ausstiegspunkte sind jmp zu fallback oder dispatch
  • Da sich die Argumente bereits in den richtigen Registern befinden, ist kein zusätzlicher Code zur Parameterübergabe nötig
• Konzeptionell behandelt diese Struktur den großen Interpreter-Loop als eine einzige komplexe Funktion; die tatsächliche Implementierung zerlegt ihn jedoch in Funktionen auf Basis von Basic Blocks und übergibt den Kontrollfluss per Tail Call
• Wenn schneller und langsamer Pfad auf getrennte Funktionen aufgeteilt werden, ist es weniger wahrscheinlich, dass Änderungen am Fallback-Code die Codequalität des schnellen Pfads beeinträchtigen
  • Bei Bedarf kann noinline Inlining verhindern
  • Die Assembler-Sequenz des schnellen Pfads lässt sich damit praktisch festschreiben

Codegenerierungsqualität in einem LuaJIT-Beispiel

• Wendet man dasselbe Muster auf ein LuaJIT-Beispiel an, lässt sich in C Code erzeugen, der nahe an handgeschriebenen Assembler herankommt
• Die Beispiel-Funktion ADDVN führt folgende Schritte aus
  • Sie extrahiert Register- und Konstantenindex aus der Instruktion
  • Bei fehlgeschlagener Typprüfung springt sie in den Fallback
  • Sie addiert eine Konstante zum Registerwert
  • Sie liest den nächsten Opcode und tail-callt die passende Funktion aus der Opcode-Tabelle
• Die verbleibenden Verbesserungsmöglichkeiten im erzeugten Assembler sind relativ klein
  • Hinter einer bedingten Verzweigung entsteht noch ein separates jmp
  • Statt jmp qword ptr [rsi + 8*rax] wird erst in rax geladen und dann jmp rax verwendet
• Solche Punkte werden als kleine, in Clang verbesserbare Fragen der Codegenerierung behandelt

Einschränkungen durch Non-Tail-Calls und Portabilität

• Der wichtigste Vorsichtspunkt bei diesem Ansatz ist, dass Non-Tail-Calls innerhalb einer Funktion die Assemblerqualität stark verschlechtern
  • Schon ein einzelner Non-Tail-Call erzwingt die Erzeugung eines Stack-Frames
  • Viele Daten können daraufhin auf den Stack gespillt werden
• Um das zu vermeiden, braucht es die Disziplin, andere Funktionsaufrufe entweder zu inlinen oder ausschließlich als Tail Call auszuführen
• Beim Protobuf-Parsing ist die Verarbeitung von Varints ein typischer schwieriger Punkt
  • Der häufige und schnelle Fall ist ein 1-Byte-Varint
  • Längere Varints sind kein Fehler, kommen aber seltener vor
  • Wenn diese Sonderbehandlung inline erfolgt, kann sich die Codequalität des schnellen Pfads verschlechtern
  • Erfolgt der Wechsel in eine Fallback-Funktion per Tail Call, lässt sich die ursprüngliche Operation nach der Verarbeitung nicht einfach wiederaufnehmen; der Fallback muss die Operation also vollständig zu Ende führen
  • Das führt zu Codeduplizierung und zusätzlicher Komplexität
• Im Update vom 2025-01-27 wurde ergänzt, wie sich dieses Problem über Aufrufkonventionen abmildern lässt
  • __attribute__((preserve_most)) ist eine Aufrufkonvention für Fallback-Funktionen, die die Verantwortung für das Erhalten fast aller Register auf den Callee verlagert und damit die Spill-Kosten in Richtung Fallback verschiebt
  • Ein Clang-Crash-Bug im Zusammenhang mit diesem Attribut wurde 2023 behoben
  • __attribute__((preserve_none)) ist eine Aufrufkonvention für Tail-Calling-Funktionen, die den Aufwand für Register-Erhalt eliminiert und mehr Register für Argumente nutzt
  • Von beiden Ansätzen wird preserve_none als weniger invasiv und damit als die bessere Wahl bewertet
• Eine weitere Einschränkung ist, dass musttail eine nicht standardisierte Compiler-Erweiterung ist
  • Es bleibt zu hoffen, dass sie sich auch in GCC, Visual C++ und darüber hinaus verbreitet und standardisiert wird, kurzfristig ist das jedoch nicht zu erwarten
  • Ohne musttail ist pro konzeptioneller Schleifeniteration mindestens ein echtes return nötig
  • In upb ist dieser Fallback bislang noch nicht implementiert; voraussichtlich wird ein Makro benötigt, das je nach Verfügbarkeit von musttail entweder per Tail Call an dispatch weitergibt oder einfach zurückkehrt

Stand der Anwendung in upb und Erweiterungspotenzial

• Der Parser mit mehr als 2GB/s wurde bei upb eingereicht, einer kleinen in C geschriebenen Protobuf-Bibliothek
• Der betreffende Code funktioniert vollständig und besteht alle Protobuf-Conformance-Tests, war zum Zeitpunkt des Schreibens jedoch noch nirgendwo ausgerollt
• In der C++-Version von Protobuf ist dieses Design nicht umgesetzt
• Durch das spätere Update von upb auf die Nutzung von musttail wurde eine große Hürde für die Produktivsetzung des schnellen Parsers beseitigt
• Dieselbe Technik könnte auch großen in C geschriebenen Sprachinterpretern wie Python, Ruby, PHP und Lua erhebliche Leistungsvorteile bringen

[GN⁺]

Meinungen auf Hacker News

• Im C-Standardvorschlag gibt es eine Syntax für Tail Calls, und zwar return goto (expression);
  Was mir daran besser gefällt als am Standard-[[musttail]], ist, dass garantiert wird, dass die Lebensdauer lokaler Objekte endet. Dadurch wird eine Implementierung auch ohne umfassende Escape Analysis möglich
  [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

  • Ich frage mich, warum return goto leichter zu implementieren ist. Auch [[musttail]] scheint auf den ersten Blick die Lebensdauer lokaler Objekte zu beenden
    Beim schnellen Überfliegen steht dort, dass die an einer Tail-Position aufgerufene Funktion denselben Typ wie das Aufrufziel haben muss. Das ist eine Bedingung, damit keine Rückgabewert-Konvertierung nötig ist und der Platz für die Argumentübergabe sowie die Calling Convention erhalten bleiben
    Eine Beschwerde, die ich häufig zu dem von mir in Clang implementierten [[musttail]] gesehen habe, ist, dass diese Einschränkung unnötig streng sei. Manche Architekturen erlauben Tail Calls auch dann, wenn die Typen nicht vollständig übereinstimmen: https://github.com/llvm/llvm-project/issues/54964
    „Dann wird der Code nicht portabel“ stimmt zwar, aber Tail-Call-Optimierung ist an sich nicht wirklich portabel. Manche Targets unterstützen Tail-Call-Optimierung grundsätzlich nicht, etwa WASM ohne Tail-Call-Erweiterung
  • Dass der Drang, C neue Features hinzuzufügen, wieder stärker wird, ist einerseits spannend, andererseits ziemlich beunruhigend
    Es gibt Änderungen und Ergänzungen, die unbedingt hinein sollten, und sogar Ideen, die klarer gefasst werden müssen, daher freue ich mich darauf. Aber der aggressive Aktualisierungszyklus von C++ scheint am Ende eher einen Buckel auf den nächsten gesetzt zu haben
    Besonders problematisch ist es, wenn Features viel früher als erwartet schlecht miteinander interagieren. Ich hoffe, der Standardisierungsprozess stützt sich nicht nur auf Begründungsdokumente, sondern testet Features ausgiebig in großen und vielfältigen Codebasen und wählt sie sehr konservativ aus

• Falls man sich für Rust interessiert: Es gibt ein älteres RFC, das ein become-Keyword hinzufügen wollte, um garantierte Tail-Call-Optimierung bereitzustellen
  Ursprünglich wurde es verschoben, um sich auf die Ziele der Edition 2018 zu konzentrieren, und diese Entscheidung war richtig, aber kürzlich wurde die Idee wieder geprüft. Sie könnte zurückkommen
  [0]: https://github.com/rust-lang/rfcs/pull/1888
  [1]: https://github.com/rust-lang/rfcs/pull/3407

• Die Art, wie Interpreter in C++ normalerweise solche Geschwindigkeitsgewinne erzielen, ist die Verwendung von computed goto. Dann gibt es auf dem Weg von einem Opcode zum nächsten kein Rauschen durch Calling-Conventions
  Der Hauptgrund, warum der computed-goto-Ansatz oder der Tail-Call-Ansatz schneller ist als eine klassische switch-Schleife, liegt darin, dass sie den Branch Predictor entlasten. Statisch entsteht pro Opcode ein indirekter Branch, statt einer Struktur mit statisch nur einem einzigen indirekten Branch

  • Wie auch im Artikel gesagt wird, ist bei computed goto der Control-Flow-Graph der Funktion so komplex, dass die Registerallokation für häufig genutzte Variablen fragil ist
    Wenn jede Funktion klein ist und die wichtigen Variablen als Argumente erhält, wird die Registerallokation deutlich weniger fragil
  • Ich frage mich, was mit „statisch ein indirekter Branch pro Opcode“ gemeint ist. Es wäre gut, etwas genauer zu erklären, was das im Vergleich zu einem einzigen indirekten Branch bedeutet und wie man das erreicht
  • Ich hatte gehört, dass dieser Ansatz seit einiger Zeit aus der Mode gekommen ist. Die Begründung war, dass Branch Predictors inzwischen gut genug seien und man ihn nicht mehr brauche
    Allerdings frage ich mich, ob das bei größer werdenden Interpretern weiterhin gilt

• Das verbleibende Problem bei der Verwendung von Tail Calls für Context Switching ist, dass man Funktionen nutzt, die eine Calling Convention verwenden müssen. Leider werden Register verschwendet, um beim Funktionsende den Zustand wiederherzustellen
  Eine ausführliche Analyse und eine Alternative mit einem Zwischen-Compiler gibt es im LuaJIT-Remake-Blog: https://sillycross.github.io/2022/11/22/2022-11-22/

  • In den letzten Jahren habe ich gesehen, wie einige Sprachen eine JIT-Schicht entfernt und später wieder hinzugefügt haben. Teilweise lag das an den Fähigkeiten der Programmierer und an gelernten Lektionen, teilweise aber auch an Veränderungen der CPU-Generationen
    Wie bei allem anderen in der Informatik kann sich, wenn sich das Kostenverhältnis der einzelnen Rechenarten ändert, der beste Algorithmus wieder zu dem entwickeln, was vor 15 oder 20 Jahren verwendet wurde. Deshalb wirkt Programmierung oft wie Mode. Wenn man etwas wiederbelebt, heißt das nicht, dass es keinen Grund dafür gibt; problematisch bleibt aber, zu vergessen, warum es beim letzten Mal kein Allheilmittel war
    Wenn der Haupt-JIT schneller oder langsamer wird, ändert sich der Nutzen im Verhältnis zu den Ausführungskosten, und auch die Schwellenwerte, die ihn auslösen, werden angepasst. Dadurch ändert sich die Menge an Code, die in anderen Schichten ausgeführt wird, und auch die amortisierten Kosten dieser Schichten können schlechter werden. Es ist wie das Austarieren eines Doppelpendels
    Wenn man eine JIT-Schicht schnell und grob genug machen kann, kann man den Interpreter ganz überspringen. Von außen betrachtet scheint die kognitive Last, zwischen einem Interpreter und etwa zwei JITs Buch zu führen, hoch zu sein; einige Sprachen wirken daher so, als hätten sie den Interpreter zurückgestellt und einen JIT verwendet, der eher auf Compile-Zeit als auf Ausgabegeschwindigkeit optimiert ist
    Ich erinnere mich nicht, welche Sprache es war, aber soweit ich weiß, hat mindestens ein Team wegen dieses Gleichgewichtsproblems am Ende auch den Zwischen-Compiler entfernt. Es war besser, sich auf zwei Dinge zu konzentrieren, statt drei zu handhaben
  • In Clang ist kürzlich eine neue Calling Convention hinzugekommen, die solche Tail Calls deutlich billiger macht. Sie vermeidet, dass der Aufrufer einige Register erhalten muss
    Beim Namen komme ich jedes Mal durcheinander; es dürfte preserve_all oder preserve_none sein. Die Frage ist, aus wessen Perspektive das Erhalten gemeint ist

• Soweit ich weiß, wird das Attribut musttail gerade zu GCC hinzugefügt. Der Patch wird geprüft, und die Semantik ist mit Clang kompatibel.

  • Ich frage mich, was aus dem Attribut preserve_most wird. Könnte etwas Ähnliches in GCC landen? Ohne das machen Nicht-Tail-Calls den Interpreter kaputt.
  • Das ist ein schwieriges Problem. Viele ABIs können selbst in sehr grundlegenden Fällen wie Aufrufen externer Funktionen mit passenden Argument- und Rückgabetypen keinen Tail-Call ausführen.
    Clang scheint Heuristiken zu haben, die für musttail-Aufrufe die Aufrufsequenz ändern. Auf i686 wird der Aufruf zum Beispiel in einen noplt-Call umgewandelt. Das steht nicht in der Clang-Dokumentation: https://clang.llvm.org/docs/AttributeReference.html#musttail
    Realistisch machbar ist wohl nur, dass der Compiler eine Diagnosemeldung ausgibt, wenn er keinen Tail-Call erzeugen kann. Für viele Nutzer dürfte das ausreichen. Eine Garantie für Tail-Calls wie in Scheme scheint schwer vorstellbar.
  • GNUC hat ziemlich viele Scheme-ähnliche Funktionen; es ist überraschend, dass es bei dieser Funktion hinterherhinkt.

• C++-Support wird ebenfalls erwähnt, aber in C++ dürfte es nur sehr wenige Tail-Calls geben.
  Zum Beispiel ist foo() { auto a = SomeClassWithADestructor(); return bar(); } kein Tail-Call, weil nach dem Aufruf von bar() noch a zerstört wird.

  • Wenn der Compiler beweisen kann, dass es zwischen diesen Zeilen keine weitreichenden Seiteneffekte gibt, könnte er dann nicht den Destruktor aufrufen, bevor bar ausgeführt wird?
    Ich frage mich, ob der C++-Standard zwingend vorschreibt, dass Destruktoren am Ende des Blocks aufgerufen werden müssen, oder ob sie auch aufgerufen werden dürfen, sobald die Variable nicht mehr verwendet wird.

• Vielleicht sind die Beispiele zu einfach, aber für gute Codegenerierung scheint __attribute__((musttail)) nicht unbedingt nötig zu sein.
  Wenn die Fehlerbehandlungsfunktion ein seltener Pfad ist, dürfte auch die Aufrufgeschwindigkeit nicht sehr wichtig sein.
  Eine Struktur wie if (unlikely(malformed)) return error(); switch (data_type) { case x: return handle_x(); case y: return handle_y(); } scheint ziemlich zuverlässig eine gute Sprungtabelle zu erzeugen.

  • Natürlich machen Compiler seit langer Zeit Tail-Call-Eliminierung, aber bei dieser Technik reicht „wird ziemlich zuverlässig erzeugt“ nicht aus. Es muss unbedingt garantiert sein, oder die Kompilierung muss fehlschlagen.
    Andernfalls funktioniert diese Struktur nicht und der Stack läuft sofort über. Der Punkt von [[musttail]] ist, dass Tail-Call-Eliminierung zwingend erforderlich ist. Der Compiler hat keine andere Wahl.
  • Wie das Disassembly im Artikel zeigt, ist der Fallback-Pfad nicht problematisch, weil dieser Aufruf selbst besonders schnell oder langsam wäre. Schon die bloße Existenz dieses Aufrufs kann den Compiler dazu bringen, für die ganze Funktion einen Stack-Frame anzulegen und Register dorthin auszulagern. Das wirkt sich auch auf den schnellen Pfad aus.
    Natürlich ist die Formulierung „erzwingt“ möglicherweise nicht ganz korrekt. Es ist nicht festgelegt, dass der Compiler für alle Ausführungspfade einer Funktion eine einzige Stack-Frame-Struktur verwenden muss, und ebenso wenig, dass er für interne Funktionen, deren Adresse nicht genommen wird, oder für Funktionen in anonymen Namespaces die Standard-ABI verwenden muss. Aber alle Compiler, die ich gesehen habe, einschließlich Clang, machen es in der Praxis so. Deshalb braucht man eine Möglichkeit, ihnen zu sagen, dass sie sich keine ABI-Sorgen machen und keine Zeit damit verschwenden sollen, Register über Aufrufe hinweg zu erhalten.
    Sprungtabellen werden natürlich gut erzeugt. Wenn man das Ergebnis aber mit etwas wie perf report laufen lässt und der Test-Bytecode keine kurze Schleife darstellt, sieht man eines von zwei Dingen: Entweder gibt es bei jedem Dispatch eine Fehlvorhersage der Verzweigung, oder der Compiler denkt sich „Sieht aus, als wolle hier jemand einen Interpreter schreiben“ und verschiebt den indirekten Sprung ans Ende jedes case. Ich habe so etwas in Clang gesehen. In beiden Fällen ist die Registerallokation des resultierenden Codes mit hoher Wahrscheinlichkeit ziemlich schlecht.

• Ich frage mich, wie schnell ein Trampolin wäre, also eine Variante, bei der die nächste Funktion als Funktionszeiger zurückgegeben und in einer äußeren Schleife aufgerufen wird. Der Vorteil wäre, dass es portables C ist.

  • C wird häufig als Zielsprache für Compiler höherer Programmiersprachen verwendet.
    Die Programmiersprache Scheme verlangt, dass kein Tail-Call den Stack wachsen lässt. Deshalb haben Implementierer verschiedene Techniken untersucht, darunter Trampoline.
    Ich habe keine konkrete Quelle zum Zitieren, aber Antworten dürfte man in Arbeiten finden, die Scheme nach C kompilieren. Wenn die Zielsprache keine garantierte Tail-Call-Optimierung bietet, wird das erzeugte Programm langsamer sein.
    Nebenbei bemerkt ist das auch der Grund, warum insbesondere Implementierer höherer Programmiersprachen unzufrieden damit sind, dass die Tail-Call-Optimierung aus der JavaScript-Spezifikation entfernt wurde. Es gibt auch Lösungen, die sowohl Tail-Call-Optimierung als auch Stack-Prüfungen beibehalten.
    https://github.com/schemedoc/bibliography/blob/master/page8....
  • Ich denke, Tail-Call-Optimierung ist schnell, weil die resultierende Schleife vorhersagbar ist und dadurch CPU-Instruktions-Prefetch und Speicher-Prefetch gut funktionieren.
    Wenn man über Funktionszeiger springt, ist das vermutlich nicht ebenso gut vorhersagbar, und man bekommt denselben Vorteil wohl nicht.
    Natürlich müsste man das messen, und ich habe es bisher nicht getan.

• Ich habe Protobuf-Decoder/-Encoder, einen IML-Parser und Python-Bindings in C geschrieben und habe einiges zur Messung der Parsing-Geschwindigkeit zu sagen.
  Wenn diese Bibliothek nur mit Bindings für verwaltete Sprachen angeboten wird, kommt in Sachen Performance ein zusätzlicher Faktor hinzu, der alles andere überlagert. Zu Ruby oder PHP kann ich nichts sagen, aber in Python habe ich dramatische Geschwindigkeitssteigerungen gesehen, wenn man keine Enumeratoren verwendet. Wenn man Protobuf-Enumeratoren in Python-Enumeratoren umwandelt, werden alle Vorteile, die man im C-Code erzielen kann, von der Zeit für das Erzeugen der diversen Python-Objekte zunichtegemacht. Der Unterschied liegt bei mehreren Größenordnungen. Darüber hinaus könnte man alle Hilfsdatenstrukturen in C implementieren und Python nur ein minimales Interface bereitstellen. Wie fair ein solcher Vergleich gegenüber Code ist, der Pythons eingebaute Strukturen nutzt, ist schwer zu beantworten.
  Googles Protobuf-Parser für Python kann immer noch „schneller“ als über 2 GB/s sein. Der Grund ist, dass er außer der Top-Level-Message nichts parst. Die interne Struktur der Message wird erst bei Bedarf geparst. Wenn der Code den geparsten Inhalt sofort vollständig liest, ist er wahrscheinlich langsamer als 2 GB/s; die Frage ist aber, wie man diese beiden Ansätze praktisch vergleichen kann. Je nach Art der Anwendung fallen die realen Ergebnisse unterschiedlich aus, daher gibt es keine eindeutige Antwort.
  Im allgemeinen Fall lässt sich Protobuf-Parsing wegen redundanter Verarbeitung nicht streamen. In der Praxis stößt Code, der Protobuf-Inhalte parst, auf einen I/O-Flaschenhals, weil er auf das Ende der Message warten muss, bevor er mit dem Parsen beginnen kann. Unabhängig davon kann je nach den typischen Protobuf-Messages einer Anwendung eine Parallelisierung des Parsings möglich sein, womit man einen Single-Thread-Parser wahrscheinlich meist überholen würde. Aber wie bei den vorherigen Beispielen lässt sich das nicht allgemein als überlegene Strategie bezeichnen.
  Üblicherweise ist es deutlich effizienter, Parsing und Erzeugung von Domain-Objekten zu kombinieren. Anwendungen müssen diesen Schritt fast immer durchlaufen. Wie ein Parser Zugriff auf diese Funktion ermöglicht, entscheidet in vielen Fällen darüber, welcher Parser gewinnt.
  Unterm Strich sind Protobuf – und vielleicht Parser im Allgemeinen – kein gutes Ziel für Geschwindigkeitsmessungen und Vergleiche. Es ist zu low-level und auch das Design ist nicht gut genug, um als Maßstab für Performance-Benchmarks zu dienen.

  • Den Teil, dass „Protobuf-Parsing im allgemeinen Fall wegen redundanter Verarbeitung nicht gestreamt werden kann“, verstehe ich nicht.
    Es wäre gut, wenn genauer erklärt würde, wie die Regel „das letzte Feld gewinnt“ Streaming-Parsing verhindert.

• GCC und Clang haben schon lange die Option -foptimize-sibling-calls, mit der man Tail Calls auch in Debug-Builds bekommen konnte.
  Natürlich ist es eine große Verbesserung, wenn diese Funktion standardisiert, garantiert und auf Funktionsebene steuerbar wird.
  [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
  [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#t...