memcpy in assembly



  • ja, das zweite cld kann weg. Was ist ABI? Abitur kann ja wohl kaum gemeint sein^^



  • ABI = Application Binary Interface
    Festlegung der calling convention, Verwendung der Register (volatile, nonvolatile), FPU Einstellungen und wie es sich z.B. mit den direction Flag verhält. (u.v.m.)
    Festlegung dieser Art müsst Ihr doch gemacht haben?
    Schlau wäre es z.B. das direction flag immer gelöscht zu lassen - das erspart den Zeit intensive Befehle CLD.



  • Festlegung dieser Art müsst Ihr doch gemacht haben?

    Wüsste nicht warum. Implizit sind wir uns aber wetgehend einig. Wir legen nur das fest, was für die Community und das OS wichtig ist. Zur Zeit suchen wir einfach ein schnelles memcpy. Die oben gezeigte Version reicht momentan aus.



  • naja, soweit ich das sehe ist sie Falsch bzw. unnötig. Hier die Version aus util.h:

    void* memcpy(void* dest, const void* src, size_t bytes)
    {
        size_t dwords = bytes/4;
        bytes %= 4;
        __asm__ volatile("cld\n" "rep movsb" : : "S" (src+dwords*4), "D" (dest+dwords*4), "c" (bytes));  // Do not change order, first rest bytes, afterwards dwords. Reason: Unknown.
        __asm__ volatile(        "rep movsl" : : "S" (src), "D" (dest), "c" (dwords));
        return(dest);
    }
    

    Wenn man dies mal ausschreibt, dann sieht es, soweit ich das sehen kann, so aus (Pseudocode, Intel Syntax):

    cld
    mov esi,(src+dwords*4)
    mov edi,(dest+dwords*4)
    mov ecx,bytes mod 4
    rep movsb
    mov esi,src
    mov edi,dest
    mov ecx,bytes/4
    rep movsd
    

    so müsste es Aussehen:

    cld
    mov esi,src
    mov edi,dest
    mov ecx,bytes
    and ecx,-4
    rep movsb
    mov ecx,bytes
    shr ecx,2
    rep movsd
    

    (Wie schon gesagt, die Funktion geht davon aus, das Quelle als auch Ziel das gleiche Alginment haben ... dann währe sie sogar recht schnell)



  • da hat sich ein kleiner Fehler eingeschlichen:

    and ecx,-4

    richtig:

    and ecx,3
    

    🙄



  • ABI = Application Binary Interface
    Festlegung der calling convention, Verwendung der Register (volatile, nonvolatile), FPU Einstellungen und wie es sich z.B. mit den direction Flag verhält. (u.v.m.)
    Festlegung dieser Art müsst Ihr doch gemacht haben?

    GCC hat diese Entscheidungen für uns getroffen. Wie der gcc das Direction Flag behandelt, weiß ich nicht. Ich würde eigentlich davon ausgehen, dass der Compiler selbst, sobald er eine rep-Instruktion nutzt, cld ausführt, weil er nicht weiß, ob andere Funktionen std ausgeführt haben.

    Also ich bin jetzt kein Assembler-Guru, aber wenn du dein memcpy optimieren willst, dann wäre es imo doch ziemlich schwachsinnig auf SSE zu verzichten. Das wär doch wohl das Erste was man versuchen würde!?

    Das Problem mit SSE ist, dass es auf älteren CPUs nicht verfügbar ist. (<= Pentium 2 oder <= AMD K6). Wir müssten demnach entweder zur Laufzeit prüfen, ob SSE vorhanden ist (cpuid), oder dies per #define bei der Übersetzung ein/ausschalten. Das ist m.E. derzeit zuviel Aufwand.



  • Hier mal eine memcpy-Variante, die masms Vorschlag, eine ESI/EDI-Zuweisung zu sparen, umsetzt:

    void* memcpy(void* dest, const void* src, size_t bytes)
    {
        size_t dwords = bytes/4;
        bytes %= 4;
        __asm__ volatile("cld\n" "rep movsl" : : "S" (src), "D" (dest), "c" (dwords));
        __asm__ volatile(        "rep movsb" : : "c" (bytes));
        return(dest);
    }
    

    Und hier memset, auf vergleichbare Weise implementiert:

    void* memset(void* dest, int8_t val, size_t bytes)
    {
        size_t dwords = bytes/4; // Number of dwords (4 Byte blocks) to be written
        bytes %= 4;              // Remaining bytes
        uint32_t dval = (val<<24)|(val<<16)|(val<<8)|val; // Create dword from byte value
        __asm__ volatile("cld\n" "rep stosl" : : "D"(dest), "eax"(dval), "c" (dwords));
        __asm__ volatile(        "rep stosb" : : "al"(val), "c" (bytes));
        return dest;
    }
    


  • Mr X schrieb:

    Das Problem mit SSE ist, dass es auf älteren CPUs nicht verfügbar ist. (<= Pentium 2 oder <= AMD K6). Wir müssten demnach entweder zur Laufzeit prüfen, ob SSE vorhanden ist (cpuid), oder dies per #define bei der Übersetzung ein/ausschalten. Das ist m.E. derzeit zuviel Aufwand.

    Natürlich. Ältere CPUs bieten aber evtl. MMX oder 3DNow!. Ein optimiertes memcpy() wird natürlich nutzen was auch immer da ist.

    Ich hab jetzt keine Erfahrung wie schnell die Variante mit rep ist die ihr da verwendet, aber wenn es nicht wirklich optimiert sein soll sondern nur ein wenig würd ich vielleicht erstmal sowas wie Duff's Device versuchen und schauen dass ich nicht byteweise sondern in möglichst großen Blöcken kopiere (long long?) und möglichst viel davon ideal aligned ist (die ersten x Byte einzeln kopieren bis wir bei einer Adresse sind die ein Vielfaches von 8 ist und von da weg alles in 8er Blöcken und nur den Rest am Ende wieder einzeln), also mal probieren was man auf Ebene von C noch rausholen kann...

    Abgesehen davon bietet der GCC offenbar den Intrinsic __builtin_memcpy()...



  • dot schrieb:

    Mr X schrieb:

    Das Problem mit SSE ist, dass es auf älteren CPUs nicht verfügbar ist. (<= Pentium 2 oder <= AMD K6). Wir müssten demnach entweder zur Laufzeit prüfen, ob SSE vorhanden ist (cpuid), oder dies per #define bei der Übersetzung ein/ausschalten. Das ist m.E. derzeit zuviel Aufwand.

    Natürlich. Ältere CPUs bieten aber evtl. MMX oder 3DNow!. Ein optimiertes memcpy() wird natürlich nutzen was auch immer da ist.

    Wie gesagt, ich denke, das ist derzeit etwas zuviel Aufwand, 3 oder 4 (MMX, 3DNow!, SSE und eine normale x86-Implementation vorzuhalten).

    Ich hab jetzt keine Erfahrung wie schnell die Variante mit rep ist die ihr da verwendet, aber wenn es nicht wirklich optimiert sein soll sondern nur ein wenig würd ich vielleicht erstmal sowas wie Duff's Device versuchen und schauen dass ich nicht byteweise sondern in möglichst großen Blöcken kopiere (long long?) und möglichst viel davon ideal aligned ist (die ersten x Byte einzeln kopieren bis wir bei einer Adresse sind die ein Vielfaches von 8 ist und von da weg alles in 8er Blöcken und nur den Rest am Ende wieder einzeln), also mal probieren was man auf Ebene von C noch rausholen kann...

    Kopieren in großen Blöcken ist ja der Ansatz, den wir mit der rep movsd-Version auch versucht haben. Duffs Device klingt interessant. Analog zu Wikipedia habe ich es so implementiert:

    void* memcpy4(void* dest, const void* src, size_t count)
    {
    	register uint8_t *to = (void*)dest, *from = (void*)src;
    	{
    		register size_t n=(count+7)/8;
    		switch(count%8)
    		{
    			case 0: 
    				do
    				{
    					*to++ = *from++;
    					case 7: *to++ = *from++;
    					case 6: *to++ = *from++;
    					case 5: *to++ = *from++;
    					case 4: *to++ = *from++;
    					case 3: *to++ = *from++;
    					case 2: *to++ = *from++;
    					case 1: *to++ = *from++;
    				} while(--n>0);
            }
    	}
    	return(dest);
    }
    

    Abgesehen davon bietet der GCC offenbar den Intrinsic __builtin_memcpy()...

    Danke für den Hinweis. Ich habe das Intrinsic grade mal ausprobiert. Die Performance ist allerdings eher schlecht (PC: AMD Duron 800 Mhz, Angaben in Taktzyklen, gezählt mit rdtsc, Durchschnitt von jeweils 200 Messungen, Interrupts/Task-switches deaktiviert):

    Anzahl Bytes    Intrinsic    Altes C-memcpy    rep-movsd-Varainte    Duffs Device
    11              63           76                72                    53
    231             365          743               153                   442
    23105           31500        69812             9183                  36079
    

    Bei sehr kleinen Datenmengen gewinnt Duffs Device, ansonsten rep-movsd. Interessanterweise verliert Duffs-Device haushoch in allen Tests, wenn man es statt auf dem Duron unter Qemu ausführt...



  • Mit welchen Compileroptionen hast du denn kompiliert? Hast du den C-Code aggressiv auf den Zielprozessor optimieren lassen?

    Dass rep movsd in qemu einen Vorteil hat, ist klar. Für TCG werden einzelne x86-Instruktionen erstmal in mehrere TCG-Ops auseinandergenommen, und er optimiert nicht so gut, dass am Ende wieder ähnlich kurze Befehlsfolgen rauskommen. Insofern ist es günstig, in einem Befehl zu beschreiben, was man will, so dass die optimale Variante in TCG-Ops draus gebastelt wird. Für Benchmarks ist qemu deswegen nicht besonders aussagekräftig.



  • Dass das Problem ziemlich kompliziert ist, zeigt schon was AMD zur Optimierung von Kopierroutinen empfiehlt:

    Software Optimization Guide for AMD64 Processors schrieb:

    5.13 Memory Copy
    Optimization
    ❖ For a very fast general purpose memory copy routine, call the libc memcpy() function included
    with the Microsoft or gcc tools. This function features optimizations for all block sizes and
    alignments.

    Von daher wiederhol ich noch malen Vorschlag, Agner Fogs lib zu verwenden: das ist ein hoch optimierte, Quelloffene All-In-One Lösung – besser werdet ihr es nie hinbekommen.



  • hoch optimierte, Quelloffene All-In-One Lösung

    Klingt gut! Wie aus der Werbung. Werde ich mir merken diesen maximalen Spruch. 😃



  • This is my memcpy, I also have clear and set if you want them.

    memfunc.asm

    global _memcpy
    
    _memcpy:
    	push edi
    	push esi
    	mov ecx, [esp+20]
    	mov edi, [esp+12]
    	mov esi, [esp+16]
    	;Move (E)CX bytes from [(E)SI] to ES:[(E)DI]
    	cld
    	rep movsb
    	pop esi
    	pop edi
    	ret
    

    memory.h

    void memcpy(void *dest, void *src, uint32_t len);
    


  • Jarvix schrieb:

    This is my memcpy, I also have clear and set if you want them.

    Unfortunately a bad solution



  • ... was würde gegen eine einfache Implementierung der memcpy() Funktion sprechen:

    void* memcpy(void* dst, const void* src, size_t total_bytes)
    {
        uint32_t i = 0u;
        uint8_t* a = dst;
        const uint8_t* b = src;
    
        for (i = 0u; i < total_bytes; ++i)
        {
            a[i] = b[i];
        }
    
        return dst;
    }
    

    - das war's. Ich stelle mir vor, das ist die schnellste Variante, weil einfach und simpel. Inline-Assembler - zu kompliziert, Zeiger-Arithmetik - zu kompliziert, SSE, MMX & Co. - auch zu kompliziert 🙂



  • abc.w schrieb:

    das war's. Ich stelle mir vor, das ist die schnellste Variante, weil einfach und simpel.

    so einfach ist es aber leider nicht ...



  • Zum memset

    Ihr werdet ja wahrscheinlich größtenteils Seiten benötigen, welche mit 0 beschrieben sind. Dann könntet ihr euch die Mühe ersparen zu optimieren, wenn ihr einen Task mit sehr niedriger Priorität erstellt, der zum Beispiel immer 10 genullte Pages bereitstellt, und auch nur arbeitet, sollte eine dieser 10 Seiten fehlen. (weiteres steht im Tanenbaum)



  • Die memcpy funktion benutzt in der Implementierung bei Visual C++ den rep move befehl und prüft ausserdem, ob die Länge eine ganzahlige vielfache von 4 ist, dann können in einen Takt bis zu 4 Bytes kopiert werden. Für den Rest wird dann rep movesb benutzt.

    Wenn ich dann also z.B. 256 Bytes kopiere, dann brauche ich dafür nur 64 Takte statt 256, wenn ich nur Byteweise kopieren würde, also mind. 4x schneller als die Lösung von abc.w und Jarvix.

    Ebenso analog arbeitet auch memmove.


Anmelden zum Antworten