Übergeben Sie auf AMD64 keine Strukturen, die größer als 16 Byte sind

• Der Aufstieg von Neat im Benchmark-Ranking von related_post_gen kam nicht durch High-Level-Optimierungen zustande, sondern durch eine kleine ABI-Änderung: Arrays werden statt als 24-Byte-Struktur als drei Pointer-Argumente übergeben
• Neat-Arrays benötigen wegen des Referenzzählers neben Start- und End-Pointer auch einen Pointer auf Basis des Array-Objekts; anders als die 16-Byte-Arrays in D landen sie damit im Speicher-Übergabepfad der SystemV AMD64 ABI
• Bestimmte Aggregate mit mehr als 16 Byte werden beim Aufruf zunächst als Wert auf den Stack kopiert und dann per Pointer übergeben; dadurch gehen die Vorteile der Registerübergabe verloren und die Kosten für Stack-Shuffling steigen
• Im Beispiel-Benchmark dauert eine Milliarde Ausführungen 12,3 Sekunden, wenn struct Vector { double x, y, z; } als Struktur übergeben wird; bei Übergabe der Felder als einzelne Argumente sinkt die Zeit auf 5,3 Sekunden
• C-APIs müssen der C-ABI folgen, aber für Typen wie Arrays, Tupel und Sumtypes innerhalb einer Sprachruntime lohnt es sich, bei mehr als 16 Byte die Übergabe aufgetrennter Felder zu benchmarken

---

Der in Neat sichtbar gewordene Flaschenhals

• Neat ist im Benchmark related_post_gen um einige Plätze im Ranking gestiegen
• Der Performancegewinn kam nicht durch einen neuen High-Level-Optimierungspass, sondern durch eine Änderung der Array-Übergabe
  • Vorher: ein Strukturargument mit drei Pointern
  • Nachher: Übergabe der drei Pointer jeweils als eigene Argumente
• Neat war im Vergleich zu D langsamer als erwartet, und im Profiler war zu sehen, dass für Funktionsaufrufe große Bereiche des Stacks verschoben wurden
• Der Flaschenhals lag weniger in der Berechnung selbst als in den Kosten der Stack-Umordnung zum Zeitpunkt des Aufrufs

Warum Neat-Arrays 24 Byte groß sind

• Anders als D-Arrays verwendet Neat Referenzzählung
• Ein Neat-Array enthält die folgenden drei Pointer
  • Start-Pointer
  • End-Pointer
  • Pointer auf Basis des Array-Objekts, in dem der Referenzzähler gespeichert ist
• Drei Pointer sind 24 Byte groß; damit nehmen sie in den AMD64-Regeln zur Argumentübergabe einen anderen Pfad als 16-Byte-Arrays mit zwei Pointern
• Der Grund, warum D-Arrays schnell und Neat-Arrays langsam waren, lag darin, dass sie mit 24 Byte die 16-Byte-Grenze überschritten

Die 16-Byte-Grenze der SystemV AMD64 ABI

• Die SystemV AMD64 ABI specification legt fest, dass bestimmte Aggregate, deren Größe zwei Eightbytes überschreitet, als ganzes Argument im Speicher übergeben werden
• Um eine Struktur im Speicher zu übergeben, muss die Aufruferseite Folgendes tun
  • Auf dem Stack Platz in Größe der Struktur reservieren
  • Diesen Platz mit dem zu übergebenden Wert füllen
  • Der Funktion den Pointer auf diese Strukturposition übergeben
• In diesem Fall muss der Wert zwingend auf dem Stack liegen, wodurch LLVM weniger Optimierungsspielraum hat
• Der Wert muss aus Registern auf den Stack kopiert werden, und es muss nachverfolgt werden, welche Teile des Stacks belegt sind und welche wiederverwendet werden können
• Bei dieser Nachverfolgung der Stack-Wiederverwendung zeigte LLVM kein gutes Verhalten

Benchmark mit einem Vektor aus drei double-Werten

• Der Benchmark verwendet einen Vektor mit drei Feldern in der Form struct Vector { TYPE x, y, z; };
• TYPE ist als double definiert
• Die beiden Funktionen führen dieselbe Addition aus, unterscheiden sich aber in der Art der Argumentübergabe
  • vector_add_struct(struct Vector left, struct Vector right) nimmt große Strukturen als Argumente entgegen
  • vector_add_fields(...) nimmt left_x, left_y, left_z, right_x, right_y, right_z als einzelne Argumente entgegen
• mode und die Ausführungslänge werden als Kommandozeilenargumente entgegengenommen, damit der Optimierer die gesamte Berechnung nicht per Constant Folding zusammenfaltet
• impl.c wird separat kompiliert, um Inlining zu vermeiden

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Das Ergebnis lag bei 12,3 Sekunden für die Strukturübergabe und 5,3 Sekunden für die Übergabe einzelner Felder

Der Unterschied im Assembly

• Die Version mit Strukturübergabe verwendet viele Instruktionen für Stack-Shuffling
• Die Feld-Version hat den Vorteil, dass die Parameter beim Eintritt in die Funktion bereits in SSE-Registern liegen
• Die Version mit Strukturübergabe muss die Werte jedes Mal vom Stack laden
• Die SystemV ABI zielt darauf ab, Werte möglichst über Register zu übergeben, aber in diesem Fall verschwindet dieser Vorteil wegen der Struktur mit mehr als 16 Byte
• Angesichts der Anzahl der auf AMD64 verfügbaren Register wäre Wertübergabe auch für Typen mit mehr als 16 Byte nützlich gewesen

Eine Situation, die cdecl ähnelt

• Die Methode, Felder auf den Stack zu schreiben und einen Pointer zu übergeben, ähnelt letztlich der alten x86-cdecl-ABI, bei der alles über den Stack übergeben wurde
• cdecl galt als langsam, und es entstanden verschiedene Calling Conventions, um dies schneller zu machen
• Problematisch ist, dass die AMD64 System V ABI wegen der Strukturgröße in diesem Fall wie die frühere Stack-Übergabe arbeitet

Ausnahmen durch Inlining und LTO

• In realem Code könnten solche Funktionen alle inline gesetzt werden
• Wenn man bei gcc LTO aktiviert, verschwindet der Performanceunterschied zwischen den beiden Versionen
• Bei clang ergibt sich nicht dasselbe Resultat
• Nicht jede Funktion kann oder sollte inline gesetzt werden

Hinweise für Sprachimplementierer und API-Optimierung

• Beim Aufruf von C-APIs muss man der C-ABI folgen
• Hochrangige Typen innerhalb einer Nicht-C-Sprache müssen jedoch nicht zwingend als eine einzelne Struktur dargestellt werden, selbst wenn sie für das Backend wie eine Struktur aussehen
• Sprachimplementierer können selbst festlegen, wie Arrays, Tupel, Sumtypes und Ähnliches übergeben werden
• In Neat wurde entschieden, solche Typen mit mehr als 16 Byte als einzelne Felder zu übergeben, und im Benchmark zeigte sich ein Vorteil
• Wer auf AMD64 eine Sprache implementiert oder eine API feinoptimiert, sollte benchmarken, ob das manuelle Aufteilen von Strukturen mit mehr als 16 Byte hilft
• Besonders in inneren Schleifen kann der Performanceunterschied größer sein als erwartet

Ergänzung: double-Strukturen und SSE

• Die Frage ist, warum eine Struktur nicht in SSE-Registern übergeben wird, obwohl double laut Spezifikation zur SSE-Klasse gehört
• Die Antwort ist, dass der Grund unbekannt ist, es in der Praxis aber nicht so übergeben wird

[GN⁺]

Hacker-News-Meinungen

• Das Problem hier ist die SysV amd64 ABI. Man muss für eine sprachinterne ABI nicht SysV verwenden. Wenn sie nicht gegenüber SysV-C-Callern offengelegt wird, kann man auch eine beliebige Calling Convention verwenden.
  https://llvm.org/docs/LangRef.html#calling-conventions
  Für Interessierte: Die entsprechende Änderung in neatlang ist hier: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Das wirkt deutlich komplizierter, als einfach die ausgegebene LLVM-Calling-Convention zu ändern. Vermutlich wollte der Autor diese Typen mit einer deterministischen Calling Convention gegenüber C-Programmen exponieren.

  • Eigentlich gilt das für ABIs insgesamt. Wer Assembler programmiert, weiß: Das ist eine der niedrig hängenden Früchte, bei denen man den Compiler leicht schlagen kann.
    Man sollte Konventionen nicht blind folgen, sondern in der jeweiligen Situation die sinnvollste Variante wählen.
  • Die Frage, die mir zuerst in den Sinn kam, war bereits beantwortet. Interessant ist, wie viel sich an Dinge wie ABIs hält, die vor langer Zeit entworfen wurden.
    Gerade ABIs sind oft eher auf Kompatibilität mit älteren CPUs ausgerichtet, und neuere CPUs könnten mit Funktionen wie erweiterten Registern Verbesserungen ermöglichen, ohne Struct-Größen zu reduzieren. Software, die auf bestimmte Hardware oder Generationen zugeschnitten ist, ist natürlich weniger attraktiv, weil sie auf manchen Maschinen nicht läuft. Aber es wäre schon cool, einen Compiler zu haben, der solchen Output erzeugen kann, wenn man Code extrem auf die Hardwarefähigkeiten des eigenen Systems optimieren möchte.

• Die Kosten der Argumentübergabe werden oft nicht gut verstanden, deshalb sind solche Artikel willkommen. Selbst an Orten wie Google ist es üblich, 24-Byte-Objekte per Wert zu übergeben, und diese Kosten verteilen sich breit über alle Funktionen, sodass sie in Profilern kaum auffallen.

  • Übergabe per Wert und per Referenz wirkt sich praktisch auf ABI/API aus und erzeugt daher eine ziemlich hohe kognitive Last. Zig versucht, das nicht zu erzwingen: Auch wenn man „per Wert“ übergibt, kann der Compiler entscheiden, tatsächlich per Referenz zu übergeben.
    Allerdings werden dabei auch solche Stolperfallen sichtbar: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • „Orte wie Google“ — ist das eigene Erfahrung? Als ehemaliger Googler kann ich sicher sagen, dass es die Guideline gibt, alles, was kein primitiver Typ ist, per Pointer oder Referenz zu übergeben.
    Die einzige Ausnahme, die mir einfällt, ist etwa string_view.
  • Gut, dass darauf hingewiesen wird, dass breit verteilter Overhead wie jener, der in Calling Conventions eingebaut ist, durch Profiling fast nicht zu finden ist.
  • Wenn man ein 24-Byte-Objekt stattdessen per Pointer übergibt, besteht der Trade-off darin, dass man den Pointer dereferenzieren muss, sobald man das Objekt tatsächlich verwenden will. Es gibt aber keine Garantie, dass dieses Objekt in der Nähe liegt.
    Mit Pech gibt es einen Cache Miss, und man wartet ungefähr 100 Nanosekunden darauf, das 24-Byte-Objekt aus dem Hauptspeicher zu holen. Übergibt man dasselbe Objekt direkt, liegt es auf dem Stack und ist daher mit höherer Wahrscheinlichkeit im Cache.
  • Ich frage mich, ob die C++-ABI bei jedem Aufruf auch 24-Byte-Objekte auf den Stack auslagert. Ich würde nicht erwarten, dass std::string- oder std::function-Parameter schnell sind, aber überraschend ist es trotzdem.

• Als wir erstmals auf x64 umgestiegen sind, machte ich mir Sorgen, dass vec3-Objekte in der Grafikprogrammierung (3 floats) nicht sizeof()=12, sondern 16 Byte groß würden, und habe die Grafik-Engine ausgiebig gebenchmarkt.
  Wenig überraschend waren 16 Byte dank 8-Byte-ausgerichteter Lesezugriffe schneller als 12 Byte. Das galt intern genauso wie auf der GPU. Also wurde vec3 stillschweigend zu vec4, und separat gibt es weiterhin auch vec4. Wie immer gilt: Man sollte nicht lokal benchmarken, sondern aus Gesamtperspektive benchmarken.

  • Das hat einen sehr guten Nebeneffekt: Es passt auch gut zur SSE-Größe. Dadurch kann man \_mm\_load\_ps direkt verwenden, der Code wird sauberer, und Vektorisierung wird sehr einfach.
  • Vermutlich ist es nicht viel schneller. Außerdem dürfte es, unabhängig davon, was man mit diesen Daten macht, auch stark von der CPU abhängen.
    Bei 16 Byte verstehe ich, dass viele Zugriffe statt 3x4 Byte als ausgerichtete 2x8 Byte oder 1x16 Byte erfolgen können. Bei anderen Zugriffen trifft das aber weniger zu, und es gibt auch das Problem des erhöhten Cache-Drucks.
  • Die x64-ABI ist auch deutlich besser als die x86-ABI.

• Nach gesundem Menschenverstand können Werte, die in Registern übergeben werden, dank spekulativer Ausführung vorab geladen werden und sind schneller als Stack-Writes; Stack-Manipulation ist wiederum schneller als Heap-Allokation.
  Deshalb ist schmutziger Spaghetti-Code mit lauter globalen Variablen enorm schnell, während elegante rekursive Funktionen oder Tuple-/Struct-/Listen-Argumente unglaublich langsam sind. Ersterer lässt sich viel leichter zu dichten Assembler-Loops optimieren.

  • Natürlich setzt das voraus, dass der Spaghetti-Code denselben Algorithmus implementiert wie der elegante Code.
    Wenn der elegante Code O(n) ist und der Spaghetti-Code O(n^2), wird man den Unterschied möglicherweise spüren. Wartbarkeit muss man ebenfalls berücksichtigen. In gewissem Sinne existiert der Compiler, um unsere elegante Lösung in Spaghetti-Code zu verwandeln.
  • „Parameter in Registern statt auf dem Stack übergeben“ ist fast Allgemeinwissen, aber „Parameter größer als 16 Byte werden immer über den Stack übergeben“ ist nicht ganz so offensichtlich.
  • Manche heutige CPUs können Memory Renaming, wodurch die Kosten für das Auslagern auf den Stack geringer werden können.
    Globale Objekte behindern außerdem Compiler-Optimierungen.

• Zur Einordnung: Bei MSVC liegt die Cut-off-Größe bei 8 Byte, bevor ein Struct über den Stack übergeben wird. Das ist ein ABI-Detail, auf das man sich in portablem Code nicht verlassen sollte.
  Bei Funktionen, die nicht häufig aufgerufen werden, muss man sich aber auch nicht zu sehr stressen. Bei kleinen Funktionen, die wie im Beispiel oft aufgerufen werden, sollte man dem Compiler etwa mit LTO ermöglichen, den Code zu inlinen. Dadurch werden Optimierungen möglich, die weit nützlicher sind, als Argumente in Registern zu übergeben.

• Solche Artikel ordne ich unter „gerade genug Wissen, um Ärger zu machen“ ein. Selbst wenn man den Anweisungen folgt und separat kompiliert, um den Compiler zu zwingen, eine über das ABI aufrufbare Funktion zu erzeugen, kann LTO diesen Fehler wieder rückgängig machen.
  Baut man dieses Programm mit LTO, wird es in beiden Modi dramatisch schneller als ein Programm ohne LTO in irgendeinem Modus. Bei performancekritischen Programmen sollte man profilieren und erst dann, nachdem man den Bottleneck bis ans Limit optimiert hat, so etwas wie das Aufdröseln von Structs in einzelne Argumente committen.

  • Das ist zwar ein guter Rat, aber ich habe noch keinen Compiler gesehen, der so etwas sichtbar macht. Erstens ist es über die gesamte Codebasis verteilt, und wenn es nicht zufällig zu einem Hotspot wird, habe ich auch noch keinen Profiler gesehen, der die Auswirkungen zeigt.
    Das betrifft fast allen vom Compiler erzeugten Code. Valgrind könnte es messen, aber Sampling-Profiler vermutlich nicht, und es gibt kein Tool, das verstreute Codegenerierungsprobleme hervorhebt.
  • Außerdem wird hier Reference Counting verwendet, während gleichzeitig von der absoluten Wichtigkeit von Performance die Rede ist.

• Unter Windows’ standardmäßiger cdecl-Aufrufkonvention werden Structs, die größer als 8 Byte sind, nicht in Registern übergeben [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• Auf amd64 ist es mit dem SysV-amd64-ABI durchaus möglich, Structs, die größer als 16 Byte sind, per Wert zu übergeben und zurückzugeben. Es ist nur langsam.
  Trotzdem lohnt sich Übergabe per Wert oft, um den Code klarer zu machen. In diesem Fall natürlich nicht, aber wie loeg angemerkt hat, kann man innerhalb der eigenen Sprache ein benutzerdefiniertes ABI verwenden, wie es C++-Compiler, Go, OCaml oder SBCL tun.

• Im gegebenen Beispiel ließe sich das beheben, ohne die Aufrufer zu beeinflussen, indem man den Parametertyp von „struct Vector“ auf „const struct Vector &“ ändert und ihn per Referenz übergibt.
  Ich habe viel C++-Code mit Pointer-Bugs gesehen, der ohne Not Pointer verwendet hat, obwohl Übergabe per Referenz gereicht hätte und einfacher sowie sicherer gewesen wäre.

  • Nein. Genau das ist hier tatsächlich das Kernproblem. Wegen des ABI macht der Compiler im Grunde genau das.
    Da das ABI vorschreibt, den Wert als Pointer zu übergeben, muss er irgendwo gespeichert werden, um einen Pointer zu erhalten, und genau dasselbe passiert, wie wenn man explizit const-ref schreibt. Wenn man den Struct-Wert in separate Argumente umwandelt, können die Argumente in Registern übergeben werden.
  • Als ich dieses Problem entdeckt habe, war es Code mit zwanzig oder dreißig allocas, um Pointer für byval zu übergeben. Jede Funktion begann mit einem separaten alloca für jeden Parameter, der an einen Aufruf weitergereicht wurde.
    Ich hatte immer irgendwie angenommen, dass LLVM so etwas gut aufräumen würde, aber wie sich herausstellte, war das nicht der Fall.
  • Trotzdem muss der Compiler drei Register auf den Stack serialisieren, um einen Struct-Pointer an den Callee zu übergeben.
    Der beschriebene Vorteil besteht darin, die Serialisierung von Registern auf den Stack vollständig zu vermeiden; mit Übergabe per Referenz scheint das nicht vermeidbar zu sein.
  • Das war kein C++-Beispiel, sondern ein C99-Beispiel. In vielen Umgebungen kann man die Tools schon wegen minimaler Trägheit nicht einfach beliebig wechseln.
    Wenn C++ erlaubt ist, hat man mehr Optionen, etwa Move-Argumente, um Kopien zu reduzieren.

• Die Faustregel, die ich in C++ immer gehört habe, lautet: Alles, was kein primitiver Typ ist, per Referenz übergeben, sofern es keinen guten Grund gibt, es per Wert zu übergeben, und nur wenn wirklich nötig per Pointer.
  Das liegt am ABI, aber auch daran, Copy-Konstruktoren oder Move-Konstruktoren zu vermeiden. Langweilige Low-Level-Details, aber wenn man in C++ maximale Performance will, muss man darauf achten. Um es klar zu sagen: Das ist nur eine Performance-Optimierung; Code, der Structs übergibt, funktioniert korrekt, er ist nur weniger schnell.