memcpy in assembly
-
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);
-
Jarvix schrieb:
This is my memcpy, I also have clear and set if you want them.
Unfortunately a bad solution