Warum man in Shadern die bedingte Auswahl-Optimierung mit `mix()`+`step()` vermeiden sollte

 (iquilezles.org)
1 Punkte von GN⁺ 2025-02-10 | 1 Kommentare | Auf WhatsApp teilen
  • Code in GPU-Shadern, der Werte mit dem ternären Operator oder einem einfachen if auswählt, wird in der Regel nicht als bedingter Sprung, sondern als bedingte Verschiebung/Auswahl (select) umgesetzt.
  • Auch wenn man ihn durch step() und arithmetische Maskierung ersetzt, verschwindet kein Sprung, der ohnehin nicht da wäre; die Annahme einer sogenannten Branch-Elimination-Optimierung ist also schon grundsätzlich falsch.
  • In der Compiler-Ausgabe von AMD und Microsoft erscheinen Vergleichs- und bedingte Masken-/Move-Instruktionen, aber keine Jump- oder Branch-Instruktionen.
  • Die step()-Variante erzeugt zunächst eine 0.0/1.0-Maske und setzt das Ergebnis dann mit Multiplikationen und Additionen zusammen, wodurch gegenüber direkter bedingter Auswahl unnötige Rechenoperationen hinzukommen.
  • GPU-Branches, die je nach Bedingung große Rechenblöcke überspringen, sind weiterhin nützlich, aber bei einfacher Wertauswahl ist es sicherer, den erzeugten Maschinencode zu prüfen.

Einfache Wertauswahl ist kein GPU-Branch

  • Die Beispielfunktion snap45() berechnet aus dem Eingabevektor zunächst x = abs(v.x) und gibt dann mit zwei ternären Operatoren eines von drei vec2-Ergebnissen zurück.
  • Dieselbe Logik bleibt auch erhalten, wenn man sie mit einem normalen if schreibt.
  • Die problematische „Optimierung“ besteht darin, den ternären Operator durch step() und gewichtete Zusammensetzung zu ersetzen.
    • w0, w1, w2 werden mit step() erzeugt.
    • res0, res1, res2 werden jeweils berechnet.
    • Mit w0*res0 + w1*res1 + w2*res2 wird das Endergebnis zusammengesetzt.
  • Diese Umformung beruht auf dem Missverständnis, dass der ursprüngliche Code einen bedingten Branch erzeugt.
  • Die einfache Auswahl von Registerwerten verändert den Instruction Pointer nicht und verursacht weder Fehlvorhersagen noch Pipeline-Flushes oder Invalidierungen des Instruction Caches.
  • Echte GPU-Branches können schnell und nützlich sein, wenn sie abhängig von einer Bedingung große Rechenblöcke überspringen.
  • Wenn jedoch wie im Beispiel nur einfache Werte oder Rechenergebnisse ausgewählt werden, kann man davon ausgehen, dass im erzeugten Maschinencode kein Branch entsteht.

Was die Compiler-Ausgabe zeigt

  • Der ursprüngliche GLSL-Code mit ternärem Operator wird im AMD-Compiler in Vergleichs- und bedingte Masken-Instruktionen übersetzt.
    • Vergleich: v_cmp_gt_f32, v_cmp_ngt_f32
    • Bedingte Maske: v_cndmask_b32
  • Auch die Compiler-Ausgabe von Microsoft zeigt dieselbe Struktur.
    • Vergleich: lt
    • Bedingtes Move: movc
  • In beiden Compiler-Ausgaben gibt es keine Jump-/Branch-Instruktionen.

Warum der step()-Ansatz teurer wird

  • Der auf step() basierende Ansatz erzeugt zunächst per bedingtem Move eine 0.0- oder 1.0-Maske und maskiert dann mehrere Kandidatenergebnisse mit Multiplikationen und Additionen.
  • Der ursprüngliche Code wählt die benötigten Werte direkt per bedingtem Move aus und ist deshalb sparsamer als der step()-Ansatz, bei dem Maskenerzeugung und arithmetische Zusammensetzung hinzukommen.
  • Auf unterschiedlicher Hardware kann die step()-Variante deutlich langsamer gemessen werden als die ursprüngliche Version.
  • Einige abs()-Aufrufe im GLSL-Beispielcode werden nicht als eigene GPU-Instruktion ausgeführt, sondern als Instruction Modifier eingebettet; in solchen Fällen ist ein abs()-Aufruf praktisch kostenlos.
  • float a = mix(b, c, step(y, x)); als Optimierung von float a = x < y ? b : c; zu empfehlen, ist ein falscher Ansatz.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-10
Meinungen auf Hacker News

  • Die Schlussfolgerung des Artikels scheint zu stimmen, aber die Argumentation wäre stärker gewesen, wenn nicht nur das Codegenerierungs-Ergebnis der besseren Version gezeigt worden wäre, sondern die Codegenerierungs-Ergebnisse beider Versionen
    Im Zitat heißt es: „Die Version, die angeblich optimiert wurde, ist viel langsamer als die ursprüngliche … sie verschwendet zwei Multiplikationen und ein oder zwei Additionen … schauen wir uns den erzeugten Maschinencode an“, tatsächlich wird aber nur die gute Version ohne Multiplikationen oder Additionen gezeigt
    Das beweist nur, dass die gute Version in Ordnung ist, aber noch nicht, dass die schlechte Version schlechter ist

    • Der Kernpunkt ist, dass die Bedingung keinen tatsächlichen Branch erzeugt hat
      Hätte man den generierten Code der anderen Version gezeigt, hätte das wahrscheinlich nur gezeigt, dass er länger ist; auch dort wäre nicht zu erwarten gewesen, dass ein Branch entsteht, daher hätte das wohl keinen großen Mehrwert gehabt
    • Der generierte Code für RDNA 1 ist hier: https://shader-playground.timjones.io/5d3ece620f45091678dcee...

  • Es wäre gut, eine verlässliche Methode zu haben, um zu erkennen, wann ein if tatsächlich einen Branch erzwingt und wann nicht
    Der Grund, warum Leute das möglicherweise teurere mix/lerp verwenden, ist, dass sie trotz eines gewissen Overheads Angst vor Branches haben
    Es ist gut, dass der klarste Code wie v = x > y ? a : b; tatsächlich gut funktioniert, aber es ist beunruhigend, dass dieselbe if-Syntax manchmal ein Branch ist und manchmal nicht
    In Kontexten, in denen wirklich kein Branch entstehen darf, würde ich mir wünschen, dass branch-if und ein nicht-branchendes if unterschiedliche Keywords wären; das nicht-branchende Keyword sollte einen Compilerfehler auslösen, wenn der Compiler es nicht ohne Branch erzeugen kann, und das Branch-Keyword sollte warnen, wenn es ohne Branch erzeugt werden kann

    • Hintergrund ist die verwirrende Dokumentation von NVIDIA und den cg/CUDA-Compilern
      Anfangs wollte man Programmierer offenbar nicht abschrecken, versteckte daher das Ausführungsmodell und erklärte es über die Abstraktion „Threads“; später wurde auch in der GPU-Werbung weiter in der Art „CUDA hat unglaublich viele Threads“ darüber gesprochen
      Dadurch entstanden seltsame Mythen rund um GPU-Programmierung
      Tatsächlich ist es oft gut, Branches im Code zu haben, und Branches an sich sind schnell
      Das Problem ist, dass SIMD-Lanes nicht jeweils in unterschiedliche Branches abbiegen können; deshalb gibt der Compiler statt eines Branches den Code für beide Seiten aus und maskiert das Ergebnis abhängig von der Bedingung
      Berechnungen, die auf Shader-Eingabewerten, Vertices, Compute-Shader-Indizes usw. basieren, verzweigen daher nicht tatsächlich, sondern werden per Maskierung sequenziell ausgeführt
      Auch im Beispiel des Artikels werden beide Werte des ?-Operators berechnet, und Bedingungen auf SIMD-Werten verhalten sich im Allgemeinen ebenso
      Es kann zwar einen kurzen Branch geben, der die Berechnung schnell überspringt, wenn alle Lanes denselben Wert haben, aber im Allgemeinen werden sowohl die true- als auch die false-Seite berechnet
      Nur Bedingungen auf Basis von Skalarregistern, also Shader-Konstanten oder uniform-Werten, erzeugen echte Branches, und solche Branches sind sehr schnell
    • Auf skalaren CPUs ist es genauso
      Zum Beispiel wurde die CMOV-Instruktion 1995 mit dem P6-Core eingeführt
      Branches sind auch auf skalaren Architekturen teuer, und Compiler versuchen so gut wie möglich zu entscheiden, wann sie eine Ersatzstrategie verwenden sollten
      Manchmal liegen sie falsch, aber nicht sehr oft
    • Auf GPUs sollte man es eher umgekehrt betrachten
      Conditional Move ist der Normalfall, und ein echter Branch ist nur dann eine mögliche Performance-Optimierung, wenn es sich um einen uniformen Branch handelt, bei dem die gesamte Workgroup in dieselbe Richtung geht
    • Man kann sich so ein Beispiel vorstellen: a = f(z); b = g(z); v = x > y ? a : b;
      Wenn die Aufrufe von f() und g() relativ teuer sind, ist es ein Trade-off, ob bedingter Code ausgegeben wird oder ob beide berechnet und anschließend ausgewählt werden
      Das ist keine einfache Wahl; die Entscheidung trifft der Compiler
    • Eine solche Funktion in Shader-Sprachen wäre interessant
      Man könnte alle Funktionen im Code wie mit Farben in branchbar/nicht-branchend unterscheiden und dafür sorgen, dass Funktionen, die als nicht-branchend markiert sind, if zu einem Conditional Move kompilieren müssen und nur nicht-branchende Funktionen aufrufen dürfen

  • Ein großer Teil des Mythos „Branches sind auf GPUs langsam“ kommt daher, dass sie vor langer Zeit, in der PlayStation-3-Ära, tatsächlich ziemlich langsam waren
    In der PS3 steckte eine NVIDIA-RSX-GPU, und ich erinnere mich, dass Branches laut Dokumentation 6 Zyklen kosteten, tatsächliche Messungen aber immer langsamer ausfielen
    Das galt selbst für vollständig kohärente Branches, bei denen alle Threads eines Warps denselben Pfad nahmen; inkohärente Branches waren noch langsamer, weil die IFEH-Instruktion 6 Zyklen kostete und die GPU außerdem beide Branches ausführen musste
    Ich denke, der Mythos „GPU-Branches sind langsam“, der sich bis heute hält, begann dort
    Branches auf heutigen GPUs, insbesondere kohärente Branches, sind ziemlich günstig

    • Wenn jemand einfach nur „Branch“ sagt, sollte man davon ausgehen, dass ein inkohärenter Branch gemeint ist
      Der Overhead heutiger Branch-Mechanismen mag gesunken sein, aber die physikalische Einschränkung, dass der Durchsatz auf beiden Seiten des Branches entsprechend dem Anteil aktiver Threads sinkt, bleibt bestehen
      Wenn beide Seiten des Branches ausgeführt werden und die Instruktionslänge gleich ist, sinkt die durchschnittliche Performance beider Seiten mindestens auf die Hälfte
      Deshalb hält sich die Überzeugung, dass Branches auf GPUs langsam sind, und sie ist tatsächlich zutreffend
      Wenn möglich, lohnt es sich, mehr Aufwand zu investieren, um das Problem ohne Branches umzuformulieren
    • Kohärente Branches sind nahezu „kostenlos“, aber zusätzliche Instruktionen erhöhen den Registerdruck
      Der Hauptgrund, dynamische Branches zu vermeiden, ist weniger, dass Branches an sich inhärent langsam wären, sondern eher dieser Punkt

  • Solche Optimierungen zur Vermeidung von Branches waren früher einmal wirksam.
    Ich habe sie auf der Xbox 360 und auf älteren integrierten Intel-GPUs profiliert, aber heute sollte man das eher nicht mehr machen.
    Bit-Extraktion und andere Integer-Operationen sind ähnlich.
    Früher war es schneller, sie mit Gleitkomma-Mathematik zu emulieren, aber heute haben alle GPUs schnelle Integer-Operationen.

    • Ich frage mich, inwieweit „heute haben alle GPUs schnelle Integer-Operationen“ wirklich stimmt.
      Wenn man sich zum Beispiel die RDNA2 ISA, die Architektur von PS5 und Xbox Series S|X, ansieht, scheinen für Integer nur 32-Bit-Skalarbefehle sichtbar zu sein.
      [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
    • Zumindest auf „großen“ GPUs ist das nicht mehr so ein großes Problem wie früher, aber in diesem Artikel geht es eigentlich gar nicht um Branch-Vermeidung an sich.
      Der gezeigte Code ist bereits branchloser Code.
      Die Leute, die solche Ratschläge geben, scheinen Branch-Code nur danach zu beurteilen, ob im Quelltext etwas steht, das wie eine Bedingung aussieht, und glauben dann, sie würden das per Optimierung vermeiden.

  • Dieser Artikel passt ebenfalls dazu: https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
    „Wenn man das Internet fragt, wie man Branches auf einer GPU schreibt, kann es klingen, als würde man damit die Tore der Hölle öffnen und Dämonen hereinlassen. Man müsse sie um jeden Preis vermeiden, und man könne sie mit seltsamen mathematischen Tricks wie dem ternären Operator oder step() umgehen. Der Großteil dieses Rats ist bestenfalls veraltet und oft schlicht falsch. Räumen wir damit auf.“

  • Prozessoren ändern sich, und Compiler ändern sich ebenfalls.
    Wenn solche Details wichtig sind, ist es am besten, mehrere Varianten auszuliefern und zur Laufzeit die schnellste Version auszuwählen.
    Wie ich schon ein paar Mal gesagt habe: Ich habe schon handgeschriebenen Assembler entfernt und durch normales C oder ähnlichen Code ersetzt, wodurch es deutlich schneller wurde.
    Dieser Assembler mag vor 10 bis 20 Jahren schneller gewesen sein, aber heute ist die Lage anders.

    • Die schnellste Version eines Shaders zur Laufzeit herauszufinden, halte ich für sehr schwierig.
      Ich kenne kaum Spiele oder Engines, die das tatsächlich tun.
      Prinzipiell könnte es möglich sein.
      Die meisten APIs wie D3D, GL und Vulkan stellen Performance-Counter bereit, und je nach Anbieter sind sie unterschiedlich zuverlässig, aber man könnte repräsentative Testszenen erstellen, sie mehrfach abspielen und Optimierungen messen.
      Viele Spiele verwenden jedoch dynamisch erzeugte Szenen und dynamisch erzeugte Shader, sodass die Zahl der zu testenden Kombinationen zum Hindernis werden kann.
      Möglicherweise müsste man die Nutzer bitten, zu warten, bis ein Benchmark abgeschlossen ist.
      Wenn man die Hardware hat, könnte man vorab auf mehreren GPU-Generationen der einzelnen Anbieter messen und nur die wichtigen Entscheidungen hardcoden, aber eine solche bestehende Infrastruktur kenne ich kaum.
    • Interessanterweise macht der NVIDIA-Treiber so etwas bis zu einem gewissen Grad.
      Er fängt Game-Shader ab und ersetzt sie durch von NVIDIA optimierte Custom-Shader.
      Deshalb sieht man in Änderungsprotokollen von NVIDIA-Treibern Formulierungen wie „Spiel X optimiert, läuft 40 % schneller“.
    • Einen weiteren Shader hinzuzufügen mag noch in Ordnung sein, aber bei „modernen“ Grafik-APIs braucht man für denselben Shader manchmal Tausende von Permutationen, und jede zusätzliche Variante verdoppelt diese Zahl.
      Man kann auch nicht unendlich viel Zeit auf jeden Shader verwenden.
      Man profiliert auf der Hardware, die einem wichtig ist, und wenn der gewählte Ansatz auf irgendeinem hypothetischen zukünftigen Prozessor langsamer ist, kann man nichts machen.
      Man muss hoffen, dass dieser Prozessor schnell genug ist, sodass es kein Problem ist.

  • Der Fehler und die Verwirrung, die dieser Artikel korrigieren will, scheinen sich auch hier zu wiederholen.
    Der Artikel behauptet nicht, dass bedingte Branches kostenlos seien.
    Meiner Ansicht nach geht es darin auch nicht um die Performance-Kosten von Branch-Code.
    Die Kernaussage ist, dass bedingte Logik in der gezeigten Form nicht zu bedingtem Branch-Code kompiliert wird.
    Und dass man aufhören sollte, schädliche Ratschläge zu verbreiten, die jede sichtbar bedingte Expression zwanghaft verschleiern.
    Was echten Branch-Code betrifft, ist es offensichtlich, dass dessen Ausführung komplizierter ist.
    Kostenlose Branches gibt es nicht, und wenn man Branches in vernünftigem Rahmen vermeidet, kann praktisch jeder Code schneller werden.
    Glücklicherweise war der ursprüngliche Code bereits branchloser Code.
    Wie immer gibt es keinen universellen Maßstab, der einem sagt, ob eine Optimierung lohnend ist.
    [0] „Sichtbar“ ist hier wichtig. Gemeint sind Fälle, in denen einen der generierte Code nicht interessiert und man nur darauf achtet, ob der Quellcode nicht wie eine Bedingung aussieht.
    [1] Natürlich war das kein Glück. Ich vermute, jemand hat IQ einen scheinbar naheliegenden, aber falschen Verbesserungsvorschlag für Shader-Code geschickt.

  • Warum ist der Compiler dann nicht schlau genug, zu erkennen, dass die „optimierte“ Version derselbe Code ist?
    Sollte er step() nicht verstehen und die Fälle step() = 0.0 und step() == 1.0 separat optimieren können?
    Zumindest eine Multiplikation ließe sich entfernen, daher sollte es normalerweise immer ein Gewinn sein, selbst wenn es am Ende durch bedingte Loads/Stores oder etwas anderes ersetzt wird.

    • In der Praxis kann das durchaus passieren.
      Manche Compiler werden diese Optimierung in manchen Fällen sehr wahrscheinlich durchführen, aber es ist definitiv auch möglich, eine Version zu schreiben, die der Compiler nicht versteht.
    • Ein weiteres Problem bei Optimierungen ist, dass es nicht zu lange dauern darf, alle Möglichkeiten auszuprobieren.
      Die meisten Optimierungen finden auf Treiberseite statt, und Arbeiten, die zu lange dauern, zeigen sich als Shader-Compile-Stottern.
      Ich kann nicht sagen, ob genau diese Optimierung tatsächlich passiert oder nicht, aber das ist ein Faktor, den man immer berücksichtigen muss.

  • Der Grund, warum die fragliche „optimierte“ Version langsamer ist, liegt darin, dass die Funktion step() tatsächlich ungefähr so implementiert ist:
    float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
    Woher soll man wissen, ob eine OpenGL-Funktion ein GPU-Primitive aufruft oder emuliert wird?

    • Der einzige Weg ist, wie im Originalbeitrag den Shader zu kompilieren, ihn zu disassemblieren und dann den Assembly-Code zu lesen.
      Ich habe das bei HLSL-Shadern oft gemacht und dabei viel über den virtuellen Befehlssatz gelernt.
      Interessant ist zum Beispiel, dass GPUs zwar eine sincos-Instruktion haben, inverse trigonometrische Funktionen aber beim Kompilieren emuliert werden.
    • Ob man das wissen muss, hängt vom Zweck ab.
      Wenn Performance wichtig ist, kann es nötig sein.
      Aber allein die Tatsache, dass step nicht als dedizierte Instruktion, sondern als Library-Funktion über einer Bedingung implementiert ist, sagt noch nichts über die Performance im Vergleich zu einer dedizierten Instruktion aus; man sollte sich also nicht zu sehr an der Implementierung selbst festbeißen.
      Wenn einen die GPU-Architektur interessiert, kann man sich Disassemblies, Open-Source-Treibercode, LLVM und ISA-Dokumentation ansehen.
    • Abgesehen von Funktionen, wie man sie auch in PC-Assembly erwarten würde, habe ich noch nicht gesehen, dass GPUs besondere Primitives dafür hätten.
      Jedes Mal, wenn ich dekompilierte Shader gesehen habe, entsprach das im Großen und Ganzen dem, was man aus C erwarten würde.
      Spezifikationen wie OpenGL legen das Verhalten vieler Built-in-Funktionen fest, und die Implementierung erfüllt diese Spezifikation dann mit Standard-Assembly-Instruktionen.
      Man kann nach Online-Seiten suchen, die in mehrere Architekturen dekompilieren.
    • Das ist eine gute Frage, die in der Programmierung generell häufig auftaucht, und auch ein zentraler Grund, warum man beim Optimieren zuerst messen sollte.
      Normalerweise muss man nicht wissen und sich auch nicht darum kümmern, wie Built-in-Funktionen implementiert sind.
      Wenn man sich doch darum kümmert, denkt man vermutlich über Optimierung nach, und dann lautet die Antwort: „Messen und prüfen, was besser ist.“
    • Der Punkt, der mich verwirrt hat, scheint zu sein, dass „Branching“ hardwareabhängig eine stärker definierte Bedeutung hat als die, mit der ich aufgewachsen bin.
      In dem Sinn, den ich gelernt habe, ist eine Bedingung ein Branch.
      Da auf Maschinencode-Ebene der Kontrollfluss zur Laufzeit ausgewählt wird, ist ein bedingter Sprung per Definition ein Branch.
      step() zu verwenden bedeutet für mich nicht, Logik in Arithmetik umzuwandeln, sondern nur, die Logik in einem Library-Funktionsaufruf zu verstecken.
      Dass step() eine Built-in-Funktion ist oder eine Funktion, die in mathematischen Arbeiten vorkommt, ändert daran nichts.
      Auch in der Mathematik ist die Definition von step() wortwörtlich eine Bedingung.
      Wenn man wirklich ohne Bedingung optimieren will, muss man eine stetige Funktion wählen, die dem gewünschten Ergebnis ähnelt, und die Parameter so anpassen, dass sie dem Ziel möglichst nahe kommt.
      Üblicherweise wählt man ein Polynom, lässt ein standardmäßiges iteratives Näherungsverfahren laufen und erhält am Ende ein f(x), das ohne Branches nur aus Additionen, Multiplikationen und „seltsam spezifischen“ Konstanten besteht.
      Den Teil, in dem der Autor nachdrücklich sagt, eine bedingte Zuweisung sei kein „Branch“, verstehe ich nicht so recht.
      Dass abs() keine GPU-Instruktion ist, sondern zu einem Instruktionsmodifikator wird und damit kostenlos ist, liegt daran, dass man dank Zweierkomplement-Darstellung bei Integern und IEEE-754-Gleitkommadarstellung das Vorzeichenbit als höchstwertiges Bit behandeln kann.
      Deshalb läuft abs() letztlich darauf hinaus, das höchstwertige Bit immer auf 0 zu setzen oder es beim lesenden Befehl zu maskieren.
      step(), beliebige ternäre Operatoren und, soweit ich weiß, Conditional-Move-Instruktionen sind aber keine solchen Spezialfälle.
      Grundlegende Dinge wie abs(), sqrt() und trigonometrische Funktionen gehören eher zum Standardwissen; beim Rest frage ich mich ohnehin, ob es wichtig ist.
      step() muss irgendwo eine Bedingung haben, und ob man sie selbst schreibt, einer Library überlässt oder der Hardware übergibt, ändert nichts an ihrer grundlegenden Natur.

  • Ich bin schon einmal in diese Falle getappt.
    Auch Claude oder ChatGPT schlagen das gern als Optimierung vor.
    Aber jedes Mal, wenn ich gemessen habe, wurde die Performance schlechter, manchmal sogar deutlich.

    • Das ist nicht überraschend.
      LLMs wiederholen nur, was in ihrem Trainingskorpus steht.
      Wenn ein Großteil des Internets falsche Dinge wie diese Conditional-Move-„Optimierung“ empfiehlt, empfehlen LLMs das ebenfalls.
    • LLMs wiederholen, was Leute im Internet sagen, und Menschen liegen häufig falsch.