branchless programming



  • Hallo zusammen

    ich habe ein für mich komplett neues Thema entdeckt: Branchless programming, also der Verzicht auf jegliche Arten von Verzweigungen ( if, switch, etc. ).

    Der etwa skurille 80er-Jahre-Kamerad hier im Video beschreibt das ganz gut:
    https://www.youtube.com/watch?v=bVJ-mWWL7cE

    Das Branchless-programming ist natürlich eine eher spezieller Anwendungsfall, den man nicht überall einsetzen kann. Intuitiver Quellcode kommt scheinbar auch nicht raus.

    Habt ihr damit Erfahrungen gemacht? Macht das Sinn, in Ausnahmefällen diese Technik anzuwenden?



  • @It0101

    Witzig, wir haben scheinbar ähnliches Youtube-Verhalten; wurde mir jedenfalls die Tage auch vorgeschlagen.
    Hab es mir angeschaut und fand es super langweilig. Habe da keine Erfahrung und habe aber auch kein Interesse "Branchless" zu programmieren.
    Jedenfalls nicht aus Performance-Gründen. Das lange switch-listen und sowas nicht so dolle sind steht auf einem anderen Blatt, aber irgendwelche Mini-Funktionen unleserlich zu machen, nur um keinen branch zu haben, davon halte ich gar nichts.



  • Branches vermeiden kann Sinn machen als Mikrooptimierung in bestimmten Fällen. Auf aktuellen CPUs ist das weniger wichtig als auf CPUs von vor 10~15 Jahren, aber es kann immer noch einen Unterschied machen.

    Wie bei fast allem, kommt es auch dabei stark darauf an was man typischerweise so programmiert. Die meisten Programmierer werden kaum bis gar keine Fälle haben wo sie davon merklich profitieren würden. Andere, die sehr speziellen Code schreiben, werden solche Fälle öfter haben.

    Was man auch noch dazusagen sollte: Compiler sind auch nicht blöd, und generieren z.T. von selbst branchless Code.
    Beispielsweise sind sowohl GCC als auch Clang schlau genug, hierfür mit -O2 branchless Code zu generieren:

    int clamp(int x) {
        if (x < 0)
            return 0;
        else if (x > 100)
            return 100;
        else
            return x;
    }
    

    ICC und MSVC generieren dagegen Code mit einem Branch.



  • Mach halt deine Branches so, das sie immer gleich branchen. Dann ist es für praktische Zwecke branchless.



  • @hustbaer sagte in branchless programming:

    Beispielsweise sind sowohl GCC als auch Clang schlau genug, hierfür mit -O2 branchless Code zu generieren

    Hm, ist denn ein cmovle, was hier z.B. der gcc10.1 -O2 erzeugt, "branchless"? Da ist doch schon "conditional" im Namen der Instruktion. Klingt für mich wie ein "Branch" innerhalb des Prozessors (im Gegensatz zu einem Branch mit einer zusätzlichen Jump-Instruktion). Oder zählt das nicht? Ist das dann schon eine philosophische Frage?

    Mach halt deine Branches so, das sie immer gleich branchen. Dann ist es für praktische Zwecke branchless.

    👍 🙂



  • @hustbaer sagte in branchless programming:

    int clamp(int x)
    

    ICC und MSVC generieren dagegen Code mit einem Branch.

    Vor C++17 mit std::clamp wäre so eine Funktion IMHO ein Kandidat für Branchless Programming gewesen, wenn es Compiler gibt, die das nicht selbständig hinbekommen - zumindest wenn zu erwarten ist, dass die Funktion ausgiebig in vielen heissen Loops verwendet wird wie es z.B. bei Grafik- und Bildverarbeitung der Fall wäre.

    @It0101 Ansonsten verwende ich solche Techniken in regulärem C++-Code eigentlich gar nicht, sondern vertraue auf die Compiler. Es ist aber trotzdem gut zu wissen, dass es sowas gibt, wenn man doch mal irgendwann eine kritische Codepassage manuell (mikro-)optimieren muss.

    Die meisten Berührungspunkte hatte ich mit Branchless Programming bisher bei der Shaderprogrammierung. Das wäre so ein Bereich wo man solche Handoptimierungen noch recht häufig anwendet (GPUs konnten lange Zeit gar keine echten bedingten Sprünge und auch heute sollte man aus Performancegründen meist gut überlegen, ob es nicht auch anders geht).



  • @wob sagte in branchless programming:

    @hustbaer sagte in branchless programming:

    Beispielsweise sind sowohl GCC als auch Clang schlau genug, hierfür mit -O2 branchless Code zu generieren

    Hm, ist denn ein cmovle, was hier z.B. der gcc10.1 -O2 erzeugt, "branchless"? Da ist doch schon "conditional" im Namen der Instruktion. Klingt für mich wie ein "Branch" innerhalb des Prozessors (im Gegensatz zu einem Branch mit einer zusätzlichen Jump-Instruktion). Oder zählt das nicht? Ist das dann schon eine philosophische Frage?

    Mach halt deine Branches so, das sie immer gleich branchen. Dann ist es für praktische Zwecke branchless.

    👍 🙂

    Was der mit "Branches sind teuer" meint, ist "branch misprediction is teuer". Wenn die CPU anfängt den falschen Code auszuführen, werden alle Ergebnisse komplett weggeworfen sobald die Misprediction erkannt wird. Ein conditional move wird in diesem Sinne nicht mispredicted.

    Beispiel:
    "Replacing conditional jumps with conditional moves also has the advantage that it can avoid branchprediction penalties that may be caused by conditional jumps. "

    https://www.cs.tufts.edu/comp/40-2011f/readings/amd-cmovcc.pdf



  • @wob sagte in branchless programming:

    Hm, ist denn ein cmovle, was hier z.B. der gcc10.1 -O2 erzeugt, "branchless"?

    Ja, sicher. Fallunterscheidungen "in der CPU" hast du bei jedem Arithmetischen oder Logischen Befehl. Bei x * y kommt auch was anderes raus, je nachdem ob z.B. y == 1 oder y == 0. Der Knackpunkt ist dass die CPU trotzdem immer weiss mit welchem Befehl sie als nächstes weiter macht. In modernen CPUs hast du typischerweise zig Befehle (pro Core/Hardware-Thread) gleichzeitig in der sog. Pipeline in Bearbeitung, in verschiedenen Stufen. Einige sind gerade erst dabei decodiert zu werden, andere warten auf etwas, andere sind mit der Adressberechnung beschäftigt etc. Das muss dann alles weggeworfen und neu gestartet werden wenn ein Branch falsch vorhergesagt wurde.



  • @It0101 sagte in branchless programming:

    Habt ihr damit Erfahrungen gemacht? Macht das Sinn, in Ausnahmefällen diese Technik anzuwenden?

    Ja, aber viele Erfolgsmomente hatte ich damit bisher nicht. Das ist nicht einfach. Vor allem finde ich das in Kombination mit AVX interessant, aber unser Code ist da wohl etwas widerspenstig. Ist wie gesagt alles nicht so einfach...



  • @It0101 sagte in branchless programming:

    Habt ihr damit Erfahrungen gemacht? Macht das Sinn, in Ausnahmefällen diese Technik anzuwenden?

    Ja, das ergibt sehr viel Sinn, wenn man das z.B. im HPC verwendet und signifikant Rechenzeit (z.B. Die Simulation läuft anstatt 7 Tagen nur noch 5 Tage auf dem Cluster) einsparen kann. D.h man sollte auch nur die zentralen Schleifen, in denen die meiste Zeit verbracht wird, sich genauer anschauen. I.d.R. profitieren Programme von solchen Mikrooptimierungen nicht.


Log in to reply