Suche strcpy, strcmp, memcpy, memcmp Implementation



  • 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 irgendwo

    edit: 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:
    - for sort() : n-log-n on average (approximately numberOfElements**log(numberOfElements) comparisions on average)
    - for stable_sort() : n-log-n if there is enough extra memory (...), or n-log-n
    log-n otherwise


  • Mod

    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.


Anmelden zum Antworten