Suche strcpy, strcmp, memcpy, memcmp Implementation
-
Hi, wo finde ich denn die Implementationen von den Funktionen strcpy, strcmp, memcpy und memcmp? Kann mir da jemand weiterhelfen?
-
http://en.wikipedia.org/wiki/Strcmp
http://en.wikipedia.org/wiki/Strcpy
http://clc-wiki.net/wiki/memcpy
http://clc-wiki.net/wiki/memcmpIm Übrigen sind gerade die copy Funktionen bei den meisten Compilern direkt in Assembler geschrieben. Willst du dafür auch Beispiele? (Und das hier ist das C++-Forum, in dem du nach C Funktionen fragst. Kannst also gleich schon mal schreiben, ob du lieber in das C oder in das Assembler Forum geschoben werden willst.)
Edit:
die Implementationen
"Die Implementierungen" gibt es nicht, das kann jeder Compiler so machen, wie er will. (Solange es funktioniert. Der Standard gibt nur vor, was die Funktionen machen müssen; nicht wie.)
-
cooky451 schrieb:
Der Standard gibt nur vor, was die Funktionen machen müssen; nicht wie.)
und bei manchen dingen auch mit welcher geschwindigkeit/komplexität...
-
Skym0sh0 schrieb:
und bei manchen dingen auch mit welcher geschwindigkeit/komplexität...
Z.B.?
-
also der standard sagt bei den containern was über die komplexität aus
ich meine map und set dürften maximal logarithmische komplexität besitzen. da müsste man mal nachgucken, hab das mal gelesen irgendwoedit: STD § 23.2.4
-
Bei vielen Algorithmen und den Containerklassen werden Laufzeit-Klassen vorgegeben (z.B. O(n log n) für std::sort() oder O(log n) für map/set-Operationen).
-
CStoll schrieb:
Bei vielen Algorithmen und den Containerklassen werden Laufzeit-Klassen vorgegeben (z.B. O(n log n) für std::sort() oder O(log n) für map/set-Operationen).
Im N1905 habe ich die Komplexität für die assoziativen Container gefunden, nicht aber für
std::sort
.
-
Ich hab' leider keinen aktuellen Standard verfügbar, aber im Josuttis sind die Komplexitätsanforderungen für diverse Algorithmen aufgelistet, z.B.:
sort/stable_sort schrieb:
Complexity:
- forsort()
: n-log-n on average (approximately numberOfElements**log(numberOfElements) comparisions on average)
- forstable_sort()
: n-log-n if there is enough extra memory (...), or n-log-nlog-n otherwise
-
EOutOfResources schrieb:
Im N1905 habe ich die Komplexität für die assoziativen Container gefunden, nicht aber für
std::sort
.25.3.1.1.3
-
SeppJ schrieb:
25.3.1.1.3
Hab ich übersehen. Danke.
-
Implementator schrieb:
Hi, wo finde ich denn die Implementationen von den Funktionen strcpy, strcmp, memcpy und memcmp?
Bei anderen weiß ich es nicht, aber memcpy ist beim GCC eine vieler "intrinsischer Funktionen". Das heißt, es gibt höchstens eine C-Version als Fallback irgendwo in den Headern oder der libc.
Werfe ich das dem GNU C++ Compiler zum Fraß vor...
// g++ -c -O2 memcpy.cpp #include <cstring> void foo(void* t, void const* s, std::size_t len) { std::memcpy(t,s,len); }
...und disassembliere das Resultat per objdump, dann erhalte ich das hier:
// objdump -Cd memcpy.o memcpy.o: file format pe-i386 Disassembly of section .text: 00000000 <foo(void*, void const*, unsigned int)>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 57 push %edi 4: 56 push %esi 5: 8b 45 08 mov 0x8(%ebp),%eax 8: 8b 75 0c mov 0xc(%ebp),%esi b: 8b 4d 10 mov 0x10(%ebp),%ecx e: 89 c7 mov %eax,%edi 10: f3 a4 rep movsb %ds:(%esi),%es:(%edi) 12: 5e pop %esi 13: 5f pop %edi 14: c9 leave 15: c3 ret 16: 90 nop 17: 90 nop
So. Da hast Du die Implementierung von std::memcpy.
-
Ganz interessant finde ich in dem Zusammenhang auch, dass der Compiler (MSVC) statt in einer Schleife direkt kopiert und dabei die Registerbreite ausnutzen kann (nur bis zu einer bestimmten Größe, und auch nur, wenn die Größe % Registerbreite == 0).
24 Byte kopieren auf einem 32 Bit-System:mov edx, DWORD PTR [eax] mov DWORD PTR [ecx], edx mov edx, DWORD PTR [eax+4] mov DWORD PTR [ecx+4], edx mov edx, DWORD PTR [eax+8] mov DWORD PTR [ecx+8], edx mov edx, DWORD PTR [eax+12] mov DWORD PTR [ecx+12], edx mov edx, DWORD PTR [eax+16] mov DWORD PTR [ecx+16], edx mov eax, DWORD PTR [eax+20] mov DWORD PTR [ecx+20], eax
Mit SSE-Optimierungen werden stattdessen die XMM Register bemüht:
movq xmm0, QWORD PTR [eax] movq QWORD PTR [ecx], xmm0 movq xmm0, QWORD PTR [eax+8] movq QWORD PTR [ecx+8], xmm0 movq xmm0, QWORD PTR [eax+16] movq QWORD PTR [ecx+16], xmm0
Bei anderen (geraden) Längen zieht der Compiler mit den Optimierungen die XMM- und für das letzte Wort das ax-Register heran.
Ähnliche Optimierungen kommen auch bei strcmp und Konsorten zum Zuge*. Nur die naivsten Implementierungen (gibt es soetwas überhaupt noch?) vergleichen byteweise.
Edit: Bzw. diese Funktionen werden gleich so programmiert. seldon hat dies afair einmal im C-Forum demonstriert.