Welches strcpy ist schneller?

[udok (Gast)]

Hallo,

Hier die Ergebnisse der Performance Tests für die strcpy Funktion,
in der Hoffnung, dass sie jemanden nützen besseren Code zu schreiben.

- Bei kurzen String < 30 Zeichen ist der Unterschied nicht allzu gross.
- Bei langen Strings ist die AgnerFog Asmlib und die Intel Lib weit 
vorne.

Wenn Interesse besteht, das ganze auf dem eigenen Rechner auszuprobier,
dann kann ich den Source und die Exe hier reinstellen.

Gruss,
Udo

[Mark B. (markbrandis)]

Ich hab jetzt ehrlich gesagt noch nie von einem Programm gehört, das zu
langsam gelaufen wäre, weil ein strcpy() zu viel Rechenzeit verbraucht
hätte. 🤔

[Le X. (lex_91)]

Mark B. schrieb:
> Ich hab jetzt ehrlich gesagt noch nie von einem Programm gehört,
> das zu
> langsam gelaufen wäre, weil ein strcpy() zu viel Rechenzeit verbraucht
> hätte. 🤔

Weißt du denn von jedem trägen Programm den Grund, warum es träge ist?

[Mark B. (markbrandis)]

Le X. schrieb:
> Weißt du denn von jedem trägen Programm den Grund, warum es träge ist?

Wenn ich das richtig überblicke, dann hat der Themenersteller nie 
gesagt, dass irgendein Teil einer Software zu träge wäre.

[M.K. B. (mkbit)]

Weißt du, warum die eine Variante schneller ist? Der Maschinencode wäre 
interessant.
Ich könnte mir vorstellen, dass irgendwo die Vektorverarbeitung in der 
CPU verwendet wird.

[udok (Gast)]

Der Asm Code wird bei den Testfiles mit ausgegeben.

Hier ein Beispiel für die den Microsoft Compiler mit -O2,
für eine memcpy() Funktion.

(Parameterübergabe findet immer in den Registern rcx, rdx und r8 statt).

    for (n = 0; n < len; n++)
         dest[n] = source[n];

MS CL.EXE 15.00 macht eine übersichtliche Schleife mit 6 Befehlen:

test_memcpy PROC          ; COMDAT

; 19   :     size_t n;
; 20   :     BYTE *p = dst;
; 21   :     const BYTE *r = src;
; 22   : 
; 23   :     for (n = 0; n < len; n++)

  test  r8, r8
  je  SHORT $LN8@test_memcp
  mov  r9, rcx
  sub  rdx, rcx
  npad  5
$LL3@test_memcp:

; 24   :         p[n] = r[n];

  movzx  eax, BYTE PTR [rdx+r9]
  inc  r9
  sub  r8, 1
  mov  BYTE PTR [r9-1], al
  jne  SHORT $LL3@test_memcp
$LN8@test_memcp:

; 25   : 
; 26   :     return dst;

  mov  rax, rcx

; 27   : }

  ret  0
test_memcpy ENDP

64 Bit Register r8 ist die Länge (len), und wird in jedem
Schleifendurchlauf bis auf 0 runtergezählt (sub r8,1).
64 Bit Register r9 ist der Index n, der in jedem Durchlauf
raufgezählt wird (inc r9).
Die Daten werden ins Register 32 Bit Register eax geladen,
und dann gleich als Byte (al = Register eax Low Byte) abgespeichert

Intel ICL.EXE  macht bei -O1 -Oi- daraus 5 Befehle:

;;;     for (n = 0; n < len; n++)

        xor       r10d, r10d                                    ;23.10
        test      r8, r8                                        ;23.21
        jbe       .B1.5         ; Prob 10%                      ;23.21
                                ; LOE rdx rcx rbx rbp rsi rdi r8 r10 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.3::                         ; Preds .B1.1 .B1.3

;;;         p[n] = r[n];

        mov       r9b, BYTE PTR [r10+rdx]                       ;24.16
        mov       BYTE PTR [r10+rcx], r9b                       ;24.9
        inc       r10                                           ;23.26
        cmp       r10, r8                                       ;23.21
        jb        .B1.3         ; Prob 82%                      ;23.21
                                ; LOE rdx rcx rbx rbp rsi rdi r8 r10 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.5::                         ; Preds .B1.3 .B1.1

;;; 
;;;     return dst;

        mov       rax, rcx                                      ;26.12
                                ; LOE
.B1.8::                         ; Preds .B1.5
        ret                                                     ;26.12

Eine 1:1 Umsetzung der for Schleife, mit 64 Bit Register r10
als Index n. Register r8 ist der Länge len.
Geladen werden die Bytes ins 64 Bit Register r9, und
als Byte (r9b) abgespeichert.

Wenn man aber -QxHost -O2 angibt, wird daraus ein Aufruf der
intel_memcpy(), zumindest für wenn der Block grösser als 96 Bytes ist:

test_memcpy  PROC 
; parameter 1: rcx
; parameter 2: rdx
; parameter 3: r8
.B1.1::                         ; Preds .B1.0

;;; {

        push      rdi                                           ;18.1
        sub       rsp, 32                                       ;18.1
        mov       rdi, rcx                                      ;18.1

;;;     size_t n;
;;;     BYTE *p = dst;
;;;     const BYTE *r = src;
;;; 
;;;     for (n = 0; n < len; n++)

        test      r8, r8                                        ;23.21
        jbe       .B1.5         ; Prob 50%                      ;23.21
                                ; LOE rdx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.2::                         ; Preds .B1.1
        cmp       r8, 96                                        ;23.5
        jbe       .B1.6         ; Prob 10%                      ;23.5
                                ; LOE rdx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.3::                         ; Preds .B1.2
        mov       rax, rdi                                      ;23.5
        mov       ecx, 1                                        ;23.5
        sub       rax, rdx                                      ;23.5
        xor       r10d, r10d                                    ;23.5
        cmp       rax, r8                                       ;23.5
        cmovg     r10d, ecx                                     ;23.5
        xor       r9d, r9d                                      ;23.5
        neg       rax                                           ;23.5
        cmp       rax, r8                                       ;23.5
        cmovg     r9d, ecx                                      ;23.5
        or        r10d, r9d                                     ;23.5
        je        .B1.6         ; Prob 10%                      ;23.5
                                ; LOE rdx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.4::                         ; Preds .B1.3

;;;         p[n] = r[n];

        mov       rcx, rdi                                      ;24.9
        call      _intel_fast_memcpy                            ;24.9
                                ; LOE rbx rbp rsi rdi r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.5::                         ; Preds .B1.1 .B1.10 .B1.4 .B1.11

;;; 
;;;     return dst;

        mov       rax, rdi                                      ;26.12
        add       rsp, 32                                       ;26.12
        pop       rdi                                           ;26.12
        ret                                                     ;26.12
                                ; LOE
.B1.6::                         ; Preds .B1.2 .B1.3
        mov       rax, r8                                       ;23.5
        mov       r9d, 1                                        ;23.5
        shr       rax, 1                                        ;23.5
        xor       ecx, ecx                                      ;23.5
        test      rax, rax                                      ;23.5
        jbe       .B1.10        ; Prob 10%                      ;23.5
                                ; LOE rax rdx rcx rbx rbp rsi rdi r8 r9 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.8::                         ; Preds .B1.6 .B1.8
        mov       r9b, BYTE PTR [rdx+rcx*2]                     ;24.16
        mov       BYTE PTR [rdi+rcx*2], r9b                     ;24.9
        mov       r10b, BYTE PTR [1+rdx+rcx*2]                  ;24.16
        mov       BYTE PTR [1+rdi+rcx*2], r10b                  ;24.9
        inc       rcx                                           ;23.5
        cmp       rcx, rax                                      ;23.5
        jb        .B1.8         ; Prob 64%                      ;23.5
                                ; LOE rax rdx rcx rbx rbp rsi rdi r8 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.9::                         ; Preds .B1.8
        lea       r9, QWORD PTR [1+rcx*2]                       ;23.5
                                ; LOE rdx rbx rbp rsi rdi r8 r9 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.10::                        ; Preds .B1.9 .B1.6
        dec       r9                                            ;23.5
        cmp       r9, r8                                        ;23.5
        jae       .B1.5         ; Prob 10%                      ;23.5
                                ; LOE rdx rbx rbp rsi rdi r9 r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.11::                        ; Preds .B1.10
        mov       al, BYTE PTR [rdx+r9]                         ;24.16
        mov       BYTE PTR [r9+rdi], al                         ;24.9
        jmp       .B1.5         ; Prob 100%                     ;24.9
        ALIGN     16
                                ; LOE rbx rbp rsi rdi r12 r13 r14 r15 xmm6 xmm7 xmm8 xmm9 xmm10 xmm11 xmm12 xmm13 xmm14 xmm15
.B1.12::
; mark_end;
test_memcpy ENDP

"-O2" sollte man wegen dem Code-Bloat nur machen, wenn es notwendig ist.
Wobei im Zeitalter, wo ein "Hello World" schon mal 100 MByte hat,
ist das auch schon Wurscht.

Der gcc 9.2 mit -O2 macht daraus auch 5 Befehle:

test_memcpy:
  .seh_endprologue
  mov  rax, rcx
  test  r8, r8
  je  .L2
  xor  r9d, r9d
  .p2align 4,,10
  .p2align 3
.L3:
  movzx  r10d, BYTE PTR [rdx+r9]
  mov  BYTE PTR [rax+r9], r10b
  add  r9, 1
  cmp  r8, r9
  jne  .L3
.L2:
  ret

mit "-O3 -march=native" werden daraus AVX Befehle, die 32 Bytes in
einem Rutsch kopieren (Label L4), zumindest wenn der Block > 64 Bytes 
ist,
und aligned ist, sonst wird ganz konventionell über Register r9 kopiert 
(Label L3):

[/c]
test_memcpy:
    .seh_endprologue
    mov    rax, rcx
    test    r8, r8
    je    .L22
    lea    rcx, 31[rcx]
    sub    rcx, rdx
    cmp    rcx, 62
    jbe    .L8
    lea    rcx, -1[r8]
    cmp    rcx, 30
    jbe    .L8
    mov    rcx, r8
    and    rcx, -32
    xor    r9d, r9d
    .p2align 4,,10
    .p2align 3
.L4:
    vmovdqu    ymm0, YMMWORD PTR [rdx+r9]
    vmovdqu    YMMWORD PTR [rax+r9], ymm0
    add    r9, 32
    cmp    r9, rcx
    jne    .L4
    mov    r9, r8
    and    r9, -32
    test    r8b, 31
    je    .L21
    .p2align 4,,10
    .p2align 3
.L6:
    movzx    ecx, BYTE PTR [rdx+r9]
    mov    BYTE PTR [rax+r9], cl
    inc    r9
    cmp    r8, r9
    ja    .L6
    vzeroupper
.L22:
    ret
    .p2align 4,,10
    .p2align 3
.L8:
    xor    ecx, ecx
    .p2align 4,,10
    .p2align 3
.L3:
    movzx    r9d, BYTE PTR [rdx+rcx]
    mov    BYTE PTR [rax+rcx], r9b
    inc    rcx
    cmp    r8, rcx
    jne    .L3
    ret
.L21:
    vzeroupper
    ret
[/c]

[Cyblord -. (cyblord)]

Ich fände einen Vergleich mit strlen interessanter. Weil da mehr 
Spielraum für Optimierung des Algorithmus besteht. Bei strcpy muss jedes 
Zeichen kopiert werden. Untere Schranke für die Komplexität ist also 
O(n). D.h. die Optimierung beschränkt sich allein auf die Details der 
Rechnerarchitektur.
Bei strlen aber nicht.

[mh (Gast)]

Cyblord -. schrieb:
> Ich fände einen Vergleich mit strlen interessanter. Weil da mehr
> Spielraum für Optimierung des Algorithmus besteht. Bei strcpy muss jedes
> Zeichen kopiert werden. Untere Schranke für die Komplexität ist also
> O(n). D.h. die Optimierung beschränkt sich allein auf die Details der
> Rechnerarchitektur.
> Bei strlen aber nicht.

Was willst du denn bei strlen anders machen? Bei strlen muss man jedes 
Byte angucken, bis man ne 0 gefunden hat und darf nicht dahinter 
weitergucken. Was soll man da anderes machen als ne lineare Suche Byte 
für Byte?

[udok (Gast)]

Ist das so?
Der Compiler kann ja nicht irgendwo nach im Speicher nach '\0' 
rumsuchen,
Die Komplexität muss also auch bei strlen() O(n) sein.
Aber wenn dir ein ganz bestimmter Test vorschwebt, kann ich den gerne
einbauen.

Die Benschmarks drehen sich aber um die Details der Rechnerarchitektur,
und inwieweit der Compiler da optimieren kann.
Hier wird ja immer wieder behauptet, dass Optimierungen auf dieser
Ebene keine Rolle spielen, aber wenn man z.B. grosse Daten kopiert,
dann machen solche "Mikrooptimierungen" schon mal einen sehr spürbaren
Faktor aus.

Hast du einen Ryzen?  Mich würde wirlich interessieren, wie die
da abschneiden.

[Cyblord -. (cyblord)]

udok schrieb:
> Ist das so?
> Der Compiler kann ja nicht irgendwo nach im Speicher nach '\0'
> rumsuchen,
> Die Komplexität muss also auch bei strlen() O(n) sein.

Wäre in der Tat möglich. Mein erster Gedanke war da könnte Algorithmisch 
was gehen, aber vielleicht auch nicht.

[(prx) A. K. (prx)]

udok schrieb:
> dann machen solche "Mikrooptimierungen" schon mal einen sehr spürbaren
> Faktor aus

Nur sind die hochgradig vom konkreten System abhängig. Bei 
Systemwechseln ungünstig.

[Walter T. (nicolas)]

Cyblord -. schrieb:
> Ich fände einen Vergleich mit strlen interessanter. Weil da mehr
> Spielraum für Optimierung des Algorithmus besteht.

Da ist was dran. Bei strlen() gäbe es für sehr lange Ketten jede Menge 
Optimierungspotenzial über die Ausnutzung des Wissens über das Layout 
des virtuellen Adressraums und des Heaps. Andererseits stellt sich 
natürlich auch die Frage, wo so große Zeichenketten überhaupt ohne 
Längeninformation überhaupt vorkommen, dass das eine Rolle spielt.

[Εrnst B. (ernst)]

Walter T. schrieb:
> Bei strlen() gäbe es für sehr lange Ketten jede Menge
> Optimierungspotenzial über die Ausnutzung des Wissens über das Layout
> des virtuellen Adressraums und des Heaps.

Nö.
Die Anforderung: "Darf kein Byte nach \0 lesen" macht dir so ziemlich 
alle Optimierungsmöglichkeiten zunichte.

Der Prozessor wird zwar trotzdem viele Bytes nach dem "\0" lesen und 
auswerten (Speculative execution), aber wieder "ROLLBACKen". Was uns die 
schöne Klasse der Spectre-CPU-Bugs eingehandelt hat.