memcpy in assembly



  • Erhard Henkes schrieb:

    Gibt es denn überhaupt eine sinnvolle Assembler-Variante als Ersatz für obigen C-Code oder sollte man das lassen? Wenn ja, warum genau?

    ja gibt es. Schau dir Agner Fog's lib an - Quellcode mit Beschreibung liegt bei.
    Auch ein Blick in die Optimization manuls ist empfehlenswert.



  • Es gab dazu mal nen Thema mit einer memcpy Implementierung die SSE nutzt: http://www.c-plusplus.net/forum/257842



  • Also ich hab ua memcpy als Prüfungsprojekt in SSE Umgesetzt, die Variante konnte auch mit nicht aligned Speicher umgehen. Das ganze lief dann über diverse OS und CPUs mit nem Geschwindigkeits Test. Das Problem daran war das sich das ganze auf älteren CPUS (AMD ATHLON 64 x2 oder Intel Core2Duo) durchaus gelohnt hat. Auf neueren wie den Quads Phenoms usw hat sich das garnichtmehr gelohnt. Es hat sich wegen dem Overhead auch generell erst ab größen jenseits 1KB gelohnt.



  • so sieht memcpy im objcode mit -O3 aus:

    00000098 <memcpy>:
          98:	55                   	push   %ebp
          99:	89 e5                	mov    %esp,%ebp
          9b:	57                   	push   %edi
          9c:	56                   	push   %esi
          9d:	53                   	push   %ebx
          9e:	83 ec 08             	sub    $0x8,%esp
          a1:	8b 45 08             	mov    0x8(%ebp),%eax
          a4:	8b 75 0c             	mov    0xc(%ebp),%esi
          a7:	8b 5d 10             	mov    0x10(%ebp),%ebx
          aa:	85 db                	test   %ebx,%ebx
          ac:	74 19                	je     c7 <memcpy+0x2f>
          ae:	89 f1                	mov    %esi,%ecx
          b0:	89 c2                	mov    %eax,%edx
          b2:	83 fb 09             	cmp    $0x9,%ebx
          b5:	77 19                	ja     d0 <memcpy+0x38>
          b7:	31 d2                	xor    %edx,%edx
          b9:	8d 76 00             	lea    0x0(%esi),%esi
          bc:	8a 0c 16             	mov    (%esi,%edx,1),%cl
          bf:	88 0c 10             	mov    %cl,(%eax,%edx,1)
          c2:	42                   	inc    %edx
          c3:	39 d3                	cmp    %edx,%ebx
          c5:	75 f5                	jne    bc <memcpy+0x24>
          c7:	83 c4 08             	add    $0x8,%esp
          ca:	5b                   	pop    %ebx
          cb:	5e                   	pop    %esi
          cc:	5f                   	pop    %edi
          cd:	c9                   	leave  
          ce:	c3                   	ret    
          cf:	90                   	nop    
          d0:	89 f7                	mov    %esi,%edi
          d2:	09 c7                	or     %eax,%edi
          d4:	83 e7 03             	and    $0x3,%edi
          d7:	75 de                	jne    b7 <memcpy+0x1f>
          d9:	8d 7e 04             	lea    0x4(%esi),%edi
          dc:	39 f8                	cmp    %edi,%eax
          de:	76 50                	jbe    130 <memcpy+0x98>
          e0:	89 df                	mov    %ebx,%edi
          e2:	c1 ef 02             	shr    $0x2,%edi
          e5:	89 7d ec             	mov    %edi,-0x14(%ebp)
          e8:	c1 e7 02             	shl    $0x2,%edi
          eb:	89 7d f0             	mov    %edi,-0x10(%ebp)
          ee:	74 28                	je     118 <memcpy+0x80>
          f0:	31 d2                	xor    %edx,%edx
          f2:	8b 7d ec             	mov    -0x14(%ebp),%edi
          f5:	8d 76 00             	lea    0x0(%esi),%esi
          f8:	8b 0c 96             	mov    (%esi,%edx,4),%ecx
          fb:	89 0c 90             	mov    %ecx,(%eax,%edx,4)
          fe:	42                   	inc    %edx
          ff:	39 fa                	cmp    %edi,%edx
         101:	72 f5                	jb     f8 <memcpy+0x60>
         103:	8b 55 f0             	mov    -0x10(%ebp),%edx
         106:	8d 0c 16             	lea    (%esi,%edx,1),%ecx
         109:	8d 14 10             	lea    (%eax,%edx,1),%edx
         10c:	89 de                	mov    %ebx,%esi
         10e:	2b 75 f0             	sub    -0x10(%ebp),%esi
         111:	3b 5d f0             	cmp    -0x10(%ebp),%ebx
         114:	74 b1                	je     c7 <memcpy+0x2f>
         116:	89 f3                	mov    %esi,%ebx
         118:	31 f6                	xor    %esi,%esi
         11a:	89 d7                	mov    %edx,%edi
         11c:	8a 14 31             	mov    (%ecx,%esi,1),%dl
         11f:	88 14 37             	mov    %dl,(%edi,%esi,1)
         122:	46                   	inc    %esi
         123:	39 de                	cmp    %ebx,%esi
         125:	75 f5                	jne    11c <memcpy+0x84>
         127:	83 c4 08             	add    $0x8,%esp
         12a:	5b                   	pop    %ebx
         12b:	5e                   	pop    %esi
         12c:	5f                   	pop    %edi
         12d:	c9                   	leave  
         12e:	c3                   	ret    
         12f:	90                   	nop    
         130:	8d 78 04             	lea    0x4(%eax),%edi
         133:	39 fe                	cmp    %edi,%esi
         135:	76 80                	jbe    b7 <memcpy+0x1f>
         137:	eb a7                	jmp    e0 <memcpy+0x48>
         139:	8d 76 00             	lea    0x0(%esi),%esi
    


  • MrX hat nun dieses memcpy vorgeschlagen:

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

    Lässt sich das steigern mit normalen Mitteln, also ohne SSE?



  • 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!?



  • was spricht den gegen die Verwendung Agner Fogs lib?
    Wie auch immer, zur Optimierung könnte man z.B. das alignment von Quelle und Ziel untersuchen und dementsprechend verschieden Routinen benutzen.
    Im allgemeinen sollte man (laut AMD und Intel) auf die String-Funktionen verzichten ([rep] cmpsX,movsX,...) bzw., wenn überhaupt, dann nur die DWORD/QWORD varianten (entsprechendes alignment vorausgesetzt).

    Wenn ich den Code gezeigter Funktion richtig interpretiere, ist diese Falsch - esi und edi sollten nur einmal mir src und dest geladen werden. Einzig ecx muss zwei Mal gefüllt werden. Ein weitere Schwäche ist, das wenn das alignment nicht stimmt, rep movsd permanent unaligned Schreib- und/oder Lesezugriffe durchführt. CLD solle man auch äußerst sparsam einsetzen - hat euer OS kein ABI Vereinbarung?



  • 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);
    

Anmelden zum Antworten