Bit Shifting & Performance



  • Hi, mich würde mal interessieren, ob es einen Grund gibt eine der folgenden Schreibweisen zu bevorzugen (z. B. Performance):

    Pointer Inkrementierung & Dereferenzierung:

    *chars = ((*(bytes++) & 0x07) << 18);
    *chars |= ((*(bytes++) & 0x3F) << 12);
    *chars |= ((*(bytes++) & 0x3F) << 6);	
    *chars |= (*(bytes++) & 0x3F);
    

    vs.

    Arrayzugriff auf die Elemente:

    *chars = (uint8_t)bytes[0] << 24 | (uint8_t)bytes[1] << 16 | (uint8_t)bytes[2] << 8 | (uint8_t)bytes[3];
    


  • (1. die Beispiele sind nicht equivalent)

    Nicht mit -O1 oder besser...
    EDIT: Ohne Optimierung möglichweise sogar schlimmer.

    Prinzipiell: Entscheide dich bei Mikro Sachen immer für das lesbare und vertraue dem Compiler. Wenn es notwendig ist, profile auf dem Zielsystem mit Tools wie VTune oder perf - oder mache micro benchmarks zur Entscheidung mit google-benchmark etc.

    Ich würde dir vorschlagen, dass du mal das verlinkte google benchmark benutzt und beide varianten (wenn sie dann auch wirklich equivalent sind) ausprobierst.
    Dann kannst du dir die Fragen irgendwann auch selbst schnell beantworten durch probieren. Vergiss nicht mit -O3 zu übersetzen.



  • @5cript sagte in Bit Shifting & Performance:

    Prinzipiell: Entscheide dich bei Mikro Sachen immer für das lesbare und vertraue dem Compiler. Wenn es notwendig ist, profile auf dem Zielsystem mit Tools wie VTune oder perf - oder mache micro benchmarks zur Entscheidung mit google-benchmark etc.

    QFT



  • Richtig, sind zwei unterschiedliche Beispiele. Rein vom Gefühl her hätte ich gesgat die Variante mit dem Arrayzugriff ist schneller, da ich hier nur einmal den Pointer incrementieren muss. Und wohl auch die besser lesbare Variante. Allerdings habe ich bei der ersten Variante Preincrements die ja schneller als Postincrements sind. Allerdings muss ich bei ersterer Variante den Befehl in mehrere Stückeln wegen der Optimierungen. Also wie in dem Beispiel vier mal den char Pointer dereferenzieren anstatt nur einmal im zweiten Beispiel. Naja, dann hilft wohl nur einen Benchmark schreiben :).



  • Das was du hier ansprichst sind doch zum grossen Teil nur Konzepte und keine Anweisungen auf Maschinenebene, deren Laufzeit betrachten macht nicht viel Sinn.



  • Du kannst es auch einfach mal in gcc.godbolt.org reinschreiben und gucken, was für ein Assembly generiert wird (oder g++ -O3 -c -S).

    Es scheint so, dass die einmalige Zuweisung einfach ein bswap + mov ist, während der andere Code irgendwie nicht dazu optimiert wird.

    Bevor man dann auf den Compiler/Optimierer schimpft, sollte man sich aber 100% sicher sein, dass die Codes dasselbe tun.



  • @enumerator sagte in Bit Shifting & Performance:

    Richtig, sind zwei unterschiedliche Beispiele. Rein vom Gefühl her hätte ich gesgat die Variante mit dem Arrayzugriff ist schneller, da ich hier nur einmal den Pointer incrementieren muss.

    Mikro-Benchmarks und Gefühl... Das passt so gut zusammen wie Wasser und brennendes Fett!

    Es muss überhaupt nichts inkrementiert werden. Das geht in einem mov, z.B. für das "+1" so: movzbl 1(%rsi), %eax Dein schönes ++ wird also wohl überhaupt nicht durchgeführt.

    @enumerator Allerdings habe ich bei der ersten Variante Preincrements die ja schneller als Postincrements sind.

    Ähm, erstens hast du Postinkrements, nicht Preincrements, zweitens gibt es für normale Zahlen meistens keinen (fast nie einen?) Unterschied* und drittens wird hier im Code das Inkrement eh komplett entfernt und durch +1,+2,+3 im mov ersetzt.

    [*] Hier ist zum Beispiel das letzte ++ überflüssig. Und du könntest alternativ das erste Postinkrement entfernen und die anderen drei durch Präinkrements ersetzen. Das kann der Compiler/Optimierer aber auch ohne dich, wenn er meint, dass das sinnvoll ist. Hier gibt es also keinen Unterschied.



  • Wie schon geschrieben, müsstest du eins der Beispiele umschreiben. Beim ersten Code werden nur 21 Bit aus den 4 chars gezogen (3+3*6).

    *chars = ((*(bytes++) & 0xFF) << 24);
    *chars |= ((*(bytes++) & 0xFF) << 16);
    *chars |= ((*(bytes++) & 0xFF) << 8);	
    *chars |= (*(bytes++) & 0xFF);
    

    Wenn du wirklich Mikrooptimierungen vornehmen möchtest, kannst du ja auch Folgendes in Betracht ziehen:

    uint32_t swap_uint32(uint32_t v)
    {
    	v = ((v << 8) & 0xFF00FF00) | ((v >> 8) & 0xFF00FF); 
    	return (v << 16) | (v >> 16);
    }
    
    uint32_t f1(const uint8_t* bytes)
    {
    	return swap_uint32(*((uint32_t*) bytes));
    }
    

    Besser (zumindest theoretisch) könnten intrinsics sein. Bei MSVC:

    #include <intrin.h>
    uint32_t f2(const uint8_t* bytes)
    {
    	return _byteswap_ulong(*((uint32_t*) bytes));
    }
    

    Zum Vergleichen kann man nur messen.



  • Ich schrieb doch schon, dass sowieso vom Compiler bswap generiert wird. Ist also völlig wumpe, was du schreibst. Ich behaupt einfach mal, dass von diesen Alternativen alle gleich schnell sind, ohne zu messen, da identischer Code generiert wird! (wenn man davon absieht, wie der Parameter übergeben wird, aber das ist eh außen vor und außerdem kann man das wohl inlinen)

    Siehe https://godbolt.org/g/mvg8WK



  • @wob „Vom Compiler” ist eine unzulässige Verallgemeinerung, um deine Aussage zu falsifizieren reicht es schon, sich die Outputs verschiedener Compiler anzuschauen.
    Ob sich dies merklich auf die Geschwindigkeit auswirkt und ob solche Mikrooptimierungen Sinn machen, muss eben jeder selbst beurteilen.



  • @yahendrik sagte in Bit Shifting & Performance:

    Wenn du wirklich Mikrooptimierungen vornehmen möchtest, kannst du ja auch Folgendes in Betracht ziehen:

    uint32_t swap_uint32(uint32_t v)
    {
      v = ((v << 8) & 0xFF00FF00) | ((v >> 8) & 0xFF00FF); 
      return (v << 16) | (v >> 16);
    }
     
    uint32_t f1(const uint8_t* bytes)
    {
      return swap_uint32(*((uint32_t*) bytes));
    }
    

    Gratuliere, jetzt hast du undefiniertes Verhalten gebaut. Lass das auf ner SPARC laufen und sie zu wie die Funken fliegen. Alignment und so. Mal ganz abgesehen davon dass es ganz strikt ausgelegt auch ne Verletzung der Aliasing Regeln ist.



  • @wob sagte in Bit Shifting & Performance:

    Es scheint so, dass die einmalige Zuweisung einfach ein bswap + mov ist, während der andere Code irgendwie nicht dazu optimiert wird.

    Das liegt an den Aliasing-Regeln (char und unsigned char dürfen alles alisen, und weil manche Compiler vorsichtig sind nehmen sie signed char auch noch dazu).

    Hier...

    void fun(unsigned int* chars, unsigned char* bytes) {
        *chars = ((*(bytes++) & 0xFF) << 24);
        *chars |= ((*(bytes++) & 0xFF) << 16);
        *chars |= ((*(bytes++) & 0xFF) << 8);	
        *chars |= (*(bytes++) & 0xFF);
    }
    
    void morefun(unsigned int* chars, unsigned char* bytes) {
        unsigned int temp;
        temp = ((*(bytes++) & 0xFF) << 24);
        temp |= ((*(bytes++) & 0xFF) << 16);
        temp |= ((*(bytes++) & 0xFF) << 8);	
        temp |= (*(bytes++) & 0xFF);
        *chars = temp;
    }
    

    ...wird für fun tonnenweise Code erzeugt, für morefun aber bloss ein bswap.



  • @hustbaer sagte in Bit Shifting & Performance:

    char und unsigned char dürfen alles aliasen, [...]

    und std::byte auch.



  • @swordfish Ja, std::byte auch. Vergess ich immer weil wir hier noch kein C++17 haben 😢



  • @hustbaer sagte in Bit Shifting & Performance:

    Das liegt an den Aliasing-Regeln

    Ah, danke für den Hinweis! 👍


Anmelden zum Antworten