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.



  • @It0101 Es gibt eine sehr gute Verwendung dafür, undzwar Code, der resistent gegen Seitenkanalangriffe ist (klassisches Beispiel: Timing-Attacks bei Überprüfung einer PIN-Eingabe). Natürlich braucht man noch viel mehr, aber das ist sicherlich ein Teilaspekt.



  • @HarteWare
    Wie funktioniert das, Seitenkanal resistenter Code und branchless Programming?

    So ein Seitenkanal Angriff stell ich mir so vor, dass aufgrund einer physikalischen Größe eines Kryptographie Systems, Rückschlüsse auf den Schlüssel gezogen werden. So zum Beispiel Stromverbrauch und Schlüsselgröße bei RSA.

    Als Gegenmaßnahme kenne ich nur die Randomisierung der physikalischen Größe s.d. diese weniger mit dem Kryptographieprozess korreliert.



  • @Quiche-Lorraine
    Klassisches Beispiel:

    static char s_correctPin[8];
    
    bool checkPinBad(char const* pin) {
        for (size_t i = 0; i < 8; i++)
            if (pin[i] != s_correctPin[i])
                return false;
        return true;
    }
    
    bool checkPinBetter(char const* pin) {
        char accu = 0;
        for (size_t i = 0; i < 8; i++) {
            char const x = pin[i] ^ s_correctPin[i];
            accu |= x;
        }
        return accu == 0;
    }
    

    Bei checkPinBad kann es etliche Wege geben über die man u.U. feststellen kann welches die erste falsche Stelle war. In manchen Fällen kannst du einfach mitstoppen wie lange es dauert bis du die Antwort bekommst. In anderen Fällen kannst du checkPinBad mehrfach mit dem selben PIN aufrufen, aber so dass beim ersten Aufruf pin[0] und pin[1] in unterschiedlichen Cache-Lines liegen, beim 2. Aufruf pin[1] und pin[2] usw. Zwischen den Aufrufen stellst du irgendwie sicher dass die Daten nicht im Cache stehen. Danach schaust du welche Cache Lines jetzt im Cache vorhanden sind und welche nicht (z.B. wieder über Timing). Daraus kannst du wieder ableiten welches die erste falsche Stelle war. D.h. du brauchst max. 10 Wiederholungen dieser Prozedur pro Stelle. Nicht wirklich viel.

    Bei checkPinBetter wird es schwierig, da die Funktion immer gleich lang braucht und immer alle Speicherstellen in pin und s_correctPin ansieht. Du hast also zwei "side channels" zugemacht.

    Idealerweise kompiliert man das dann noch ohne Optimierungen oder schreibt es gleich in Assembler, damit sichergestellt ist dass der Compiler nicht Schweinchen Schlau spielt und etwas so optimiert dass sich wieder messbare Unterschiede ergeben.



  • @hustbaer

    Ok verstehe ich.

    Aber dein Code gefällt mir nicht. Nehmen wir mal an, der PIN wäre als nullterminierter String kodiert. Wenn der Benutzer nun einen PIN mit weniger als 7 Zeichen eingibt, liest deine Funktion über den Parameter pin hinaus. Eine verbesserte Version sähe so aus.

    bool checkPinBetter2(char const* pin) {
        char accu = 0;
    	
        if (strlen(pin) != strlen(s_correctPin))
    	return false;
        for (size_t i = 0; i < 8; i++) {
            char const x = pin[i] ^ s_correctPin[i];
            accu |= x;
        }
        return accu == 0;
    }
    

    Wenn nun aber der PIN binär kodiert ist und der Benutzer keine 8 Bytes angibt, so liefert deine Funktion auch manchmal true zurück obwohl der Benutzer keine 8 Zeichen eingegeben hat. Eine verbesserte Version sähe so aus.

    bool checkPinBetter2(char const* pin, unsigned int len) {
        char accu = 0;
    	
        if (len != sizeof(s_correctPin))
    	return false;
        for (size_t i = 0; i < 8; i++) {
            char const x = pin[i] ^ s_correctPin[i];
            accu |= x;
        }
        return accu == 0;
    }
    

    Und siehe da, da haben wir wieder unsere Branches... 😉



  • Das scheinst du dann nicht richtig verstanden zu haben.
    Es soll ja extra kein vorzeitiger Abbruch erfolgen. Man könnte dazu die Abfrage in die Schleife packen (so daß also immer die Maximalanzahl an Schleifendurchgängen erfolgt):

    bool checkPinBetter2(char const* pin) {
        char accu = 0;
        size_t len = strlen(pin);
        for (size_t i = 0; i < sizeof(s_correctPin); i++) {
            char const x = i < len ? pin[i] : 0;
            char const y = x ^ s_correctPin[i];
            accu |= y;
        }
        return accu == 0;
    

    Trotzdem könnte so immer noch ein Timing-Unterschied bzgl. der Abfrage möglich sein (dazu müßte man dann noch ein bißchen mehr tricksen - dazu dann statt 0 ebenfalls einen Indexzugriff durchführen).
    Besser wäre natürlich noch die Schleifenanzahl zusätzlich zu erhöhen, damit aus der Gesamtlaufzeit nicht auf die Länge des correctPin geschlossen werden kann.

    Alternativ vorher den Eingabe-Pin einfach auf eine vordefinierte Größe aufblähen und die restlichen Werte mit dem Rest des korrekten Pins auffüllen:

    const size_t max_len = 16;
    static char s_correctPin[max_len] = "ABCDEFGHxxxxxxxx"; // PIN ist nur "ABCDEFGH"
    static char   s_dummyPin[max_len] = "xxxxxxxxxxxxxxxx";
    
    static char s_checkPin[max_len];
    
    bool checkPinBetter3(char const* pin) {
       size_t len = strlen(pin);
        for (size_t i = 0; i < max_len; i++) {
            s_checkPin[i] = i < len ? pin[i] : s_dummyPin[i];
    
        // Rest von oben, nur mit Schleife bis max_len und s_checkPin anstatt pin
    }
    

    Generell mag ich aber auch diese Art der Programmierung persönlich nicht, aber in heutigen Zeiten muß man sicherheitskritischen Code doppelt und dreifach absichern.



  • @Quiche-Lorraine sagte in branchless programming:

    Aber dein Code gefällt mir nicht.

    😱



  • @Quiche-Lorraine sagte in branchless programming:

    Nehmen wir mal an,

    Nehmen wir mal an das wäre ein einfaches Beispiel gewesen 🙄

    Und siehe da, da haben wir wieder unsere Branches...

    Und wurscht ist es auch. Der einzige problematische Branch hier ist der mit len != sizeof(s_correctPin). Das hilft dem Angreifer vermutlich nicht sehr. Aber auch den könnte man vermeiden wenn es wirklich drauf ankommt. Nur ist der Code der dafür nötig ist sicher kein schönes, einfaches Beispiel mehr dafür wie man sowas branchless machen kann.

    @Th69
    Naja, den Angreifer wissen zu lassen dass der PIN die falsche Länge hat ist vermutlich kein grosses Problem. Denn dadurch spart er sich nicht viel. Egal wie lange der Code ist, alle kürzeren Kombinationen durchzuprobieren dauert immer nur einen Bruchteil der Zeit die man benötigt um alle Kombinationen mit der korrketen Länge zu probieren.



  • @Quiche-Lorraine
    Hier, bitte, ohne Branches (ausgenommen den einen für die Bedingung der Schleife, die immer gleich oft durchlaufen wird):

    char s_correctPin[] = { '1', '2', '3', '4', '5', '6' };
    
    int checkPin(char const* userPin) {
        unsigned char accu = 0;
        char const* p = userPin;
    
        for (size_t i = 0; i < sizeof(s_correctPin); i++) {
            unsigned char const cch = (unsigned char)s_correctPin[i];
            unsigned char const uch = (unsigned char)*p;
    
            accu |= (uch ^ cch);
    
            unsigned char x = uch;
            x |= x >> 4;
            x |= x >> 2;
            x |= x >> 1;
            x &= 1;
            p += x;
        }
    
        accu |= (unsigned char)*p;
    
        accu |= accu >> 4;
        accu |= accu >> 2;
        accu |= accu >> 1;
    
        return (accu & 1) ^ 1;
    }
    


  • @hustbaer
    Danke 🙂



  • @hustbaer sagte in branchless programming:

    unsigned char x = uch;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    x &= 1;
    p += x;
    

    Nachdem ich endlich gerafft habe, dass all diese Zeilen nur dafür da sind, um die Nullterminierung zu behandeln, hab ich mich gefragt, ob sich das statt kreativ pfiffig nicht auch langweilig simpel formulieren lässt.

    Auf (x86) CPU-Ebene gedacht kann man für "branchless" ja durchaus die CMP-Instruktion verwenden, nur eben ohne den sonst üblicherweise folgenden bedingten Sprung - man muss lediglich die von CMP gesetzten Flags auslesen.

    Und tatsächlich, ein simples p += (x == 0); sollte es hier auch tun:

    bool cmp(int a, int b)
    {
        return a == b;
    }
    

    ==> https://godbolt.org/z/jGb3WE

    cmp(int, int):
            cmp     edi, esi
            sete    al
            ret
    

    Ob das für andere CPUs auch so schön geht, kann ich nicht sagen, für x86 macht es den Code jedenfalls kürzer und lesbarer.

    Edit: Ich hatte schon den Verdacht, dass das eventuell nicht mit jeder CPU-Architektur geht. Für ARM sieht mir das immer noch "branchless" aus, aber AVR gcc 9.2.0 erzeugt hier:

    cmp(int, int):
            mov r19,r25
            mov r18,r24
            ldi r24,lo8(1)
            cp r18,r22
            cpc r19,r23
            breq .L2
            ldi r24,0
    .L2:
            ret
    

    breq scheint mir ein bedingter Sprung zu sein. Ich denke das Bitgefummel ist wohl letztendlich doch zuverlässiger.


Log in to reply