Schnelleres memset auf Basis von MOVDQU



  • Ahoy, Leute.

    Ich wollte mir die vergangene Woche eine kleine Herausforderung stellen und ein memset schreiben, welches annähernd so schnell oder schneller als das der glibc unter meinem System (Gentoo Linux) arbeitet. Es handelt sich dabei allerdings nur um eine Herausforderung und ein Weg, ein bisschen was dazuzulernen.

    Meine sämtlichen Ansätze waren jedoch immer 50% bis 100% langsamer als die glibc-Variante. Glibc kam auf 1200 Cycles auf 20000 Bytes, meine Variante auf 1900 Cycles. Ich habe auf korrektes Alignment und atomare Zuweisung der verschiedenen Werte auf meiner Zielmaschine (x64) geachtet.

    Schließlich wurde es mir zu bunt, immer hinterherzuhinken, und ich habe mir den Assemblercode des Glibc- memset s angeschaut. Und was soll ich sagen, der gcc mogelt, scheint mir:

    8d:   f3 44 0f 7f 44 17 f0    movdqu XMMWORD PTR [rdi+rdx*1-0x10],xmm8
      94:   f3 44 0f 7f 47 10       movdqu XMMWORD PTR [rdi+0x10],xmm8
      9a:   f3 44 0f 7f 44 17 e0    movdqu XMMWORD PTR [rdi+rdx*1-0x20],xmm8
      a1:   f3 44 0f 7f 47 20       movdqu XMMWORD PTR [rdi+0x20],xmm8
      a7:   f3 44 0f 7f 44 17 d0    movdqu XMMWORD PTR [rdi+rdx*1-0x30],xmm8
      ae:   f3 44 0f 7f 47 30       movdqu XMMWORD PTR [rdi+0x30],xmm8
      b4:   f3 44 0f 7f 44 17 c0    movdqu XMMWORD PTR [rdi+rdx*1-0x40],xmm8
    

    Meine Routine hingegen:

    4009a8:       48 89 02                mov    QWORD PTR [rdx],rax
    

    Glib- memset prüft immer auf 128 Bytes, die noch übrig sein könnten, und schreibt diese dann in 16 Byte-Chunks (ein Double-Quadword), 8 Mal in jeder Iteration.

    Über den gcc kann ich Inline-Assembler mit angeben, aber:

    1. ist mein Assembler ziemlich grottig - immer mal wieder angefangen, aber nie wirklich weitergekommen.
    2. Habe ich auch noch keine Erfahrung mit SSE - wenn ich nach dem Namen der Register google, finde ich die im Zusammenhang mit SSE. Auch, wenn ich ein wenig verwirrt bin, weil SSE eher im Zusammenhang mit Gleitkommazahlen erwähnt wird. Aber wird man wahrscheinlich "missbrauchen" können, oder ich habe das nicht verstanden, kann ich erstmal mit leben.

    Meine Frage wäre jedenfalls, wie ich den gcc dazu bringe, dass er SSE-Funktionen für mich "freischaltet", und wie ich dies in C ausdrücken kann. Äh, nun, eigentlich habe ich dem gcc schon gesagt, dass er SSE verwenden darf:

    -O2 -pipe -march=core-avx-i -mmmx -msse -msse2 -msse3 -mssse3 -msse4 -msse4.1 -msse4.2 -mrdrnd -mavx -mavx2 -maes -mpclmul -mf16c -mfma
    

    Also wäre eigentlich eher die C-Code-Seite interessanter. Der gcc hat einen nativen Typen für 128-Bit-Variablen, den ich auch auf ein Register mappen kann:

    void* my_memset(void*s,int c,size_t n)
    {
            /*Wert auf 64 Bit aufweiten.*/
            register uint64_t x64=(c&0xff)*0x0101010101010101ULL;
    
            /*Und dann auf 128 aufweiten.*/
            register unsigned __int128 x128 asm("xmm8")=x64<<64ULLL|x64;
    
            /*Und dann halt Magie für das Schreiben in den angegebenen Buffer.*/
    }
    

    Aber mit der __int128 -Implementierung im gcc war es das auch irgendwie. Denn die Anweisung x64<<64ULLL|x64 führt zu einer Warnung:

    Warnung: Links-Schiebe-Weite >= Breite des Typs [standardmäßig aktiviert]
    

    Und wenn ich auch sonst nichts weiß, dann doch, dass ich spätestens jetzt Experten frage, die wissen, wie man sowas ordentlich macht. 🙂 Vor allem, weil ich hier einen sehr starken Fokus auf den gcc habe, aber andere Compiler außer Acht lasse. Und das ist auch blöd.

    Danke für die Aufmerksamkeit und für etwaige Lösungsvorschläge im Voraus.



  • Ach, Mensch, jetzt habe ich mich auch noch vertippt. Sollte

    x64<<64ULL|x64 /*Mit nur zwei und nicht drei 'L'*/
    

    sein.


  • Mod

    -O2 -pipe -march=core-avx-i -mmmx -msse -msse2 -msse3 -mssse3 -msse4 -msse4.1 -msse4.2 -mrdrnd -mavx -mavx2 -maes -mpclmul -mf16c -mfma
    

    ziemlich redundant oder?

    dachschaden schrieb:

    Der gcc hat einen nativen Typen für 128-Bit-Variablen

    der wahrscheinlich nicht durch sse/avx-Instruktionen implementiert wird (habe ich aber nicht überprüft).

    dachschaden schrieb:

    Und wenn ich auch sonst nichts weiß, dann doch, dass ich spätestens jetzt Experten frage, die wissen, wie man sowas ordentlich macht.

    Einfach den Compiler machen lassen? Das ist doch schon ordentlich.



  • camper schrieb:

    ziemlich redundant oder?

    Immer sicherstellen, dass die Leute, die dir helfen sollen, alle Informationen besitzen. Kann sein, dass es einen Bug gibt, von dem ich nur nichts weiß, dass wenn ich alle SSE-Optionen aktiviere, keine zum Tragen kommt.

    camper schrieb:

    der wahrscheinlich nicht durch sse/avx-Instruktionen implementiert wird (habe ich aber nicht überprüft).

    Notfalls kann ich das auch manuell machen, durch das Mapping auf ein 128-Register sollten die von mir in Angriff genommenen Anweisungen funktionieren.
    Meine vorherigen Versuche liefen ja, wie ich bereits beschrieben hatte (atomar) auf 64-Bit-Zugriffen ab. Jetzt will ich auf 128-Bit wechseln, aber sauber halt.

    camper schrieb:

    Einfach den Compiler machen lassen? Das ist doch schon ordentlich.

    Wenn meine Funktion doppelt so lange braucht, weil 128-Bit-Operationen nicht generiert werden, ob dies eigentlich der Fall sein sollte, würde ich das nicht unbedingt als "ordentlich" bezeichnen.


  • Mod

    Es gibt ja Intrinsics für SSE/AVX - ich würde versuchen, damit etwas zusammenzubauen, ausgehend von reinem Assemblercode,
    der ansatzweise ungefähr so aussieht

    typedef unsigned char ymmd __attribute__ ((vector_size(32)));
    
    void* my_memset(void* s, int c, size_t n)
    {
        ymmd reg;
        asm(
            "andl      $0xff, %[c]\n\t"
            "imul      $0x01010101, %[c]\n\t"
            "add       %[n], %[s]\n\t"
            "neg       %[n]\n\t"
            "vmovd      %[c], %x[reg]\n\t"
            "vshufps   $0, %[reg], %[reg], %[reg]\n\t"
            "0:\n\t"
            "vmovdqu   %[reg], (%[s],%[n],1)\n\t"
            "add       $32, %[n]\n\t"
            "jnz       0b\n\t"
            :: [s] "r" (s),
               [reg] "x" (reg),
               [c] "r" (c),
               [n] "r" (n));
        return s;
    }
    

    ohne loop-unrolling und der Einfachkeit halber bloss für 32Byte-Blöcke.



  • Camper, ich weiß, dass das gut gemeint ist.
    Aber wie ich bereits oben schrieb: mein Assembler ist eher mau, und ich hatte gehofft, der Compiler würde mir das abnehmen (warum sage ich dem Compiler sonst, dass der SSE verwenden darf)?

    Ich warte noch ein bisschen - vielleicht hat hier jemand noch eine andere Idee, wie man sowas auf C-Level realisiert bekommt. Es handelt sich eh nur um eine Herausforderung.
    Aber trotzdem vielen Dank. 🙂





  • @hustbaer: Genau das, was ich haben wollte:

    #include <xmmintrin.h>
    
    void* my_memset(void*s,int c,size_t n)
    {
            register __m128i*p128=(__m128i*)(s);
            register __m128i*e128=(__m128i*)(s+n);
            register __m128i x128=_mm_setr_epi32
            (
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101
            );
    
            while(p128<=--e128) *e128=x128;
    
            return s;
    }
    

    Ist auch 200 Cycles schneller als das normale memset (wobei hier noch etliche Sachen fehlen, das ist mir bewusst). Aber da ich noch keine Erfahrung mit diesen Funktionen habe, wird die Codequalität wohl entsprechend sein ... egal. Ich habe jetzt eine Basis, mit der ich arbeiten kann.

    Danke. 🙂

    EDIT: Kriegt man auch mit AVX2 hin:

    #include <immintrin.h>
    
    void* my_memset(void*s,int c,size_t n)
    {
            register __m256i*p256=(__m256i*)(s);
            register __m256i*e256=(__m256i*)(s+n);
    
            register __m256i x256=_mm256_setr_epi32
            (
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101,
                    (c&0xff)*0x01010101
            );
    
            while(p256<=--e256) *e256=x256;
    
            return s;
    }
    

    Benötigt dann sogar nur 750 Cycles statt 1000 (SSE), 1200 (Glibc) oder 1900 (mein naiver Versuch). Was ich jedoch als Verlierer für den gcc verwerte.


Anmelden zum Antworten