Domanda Assegnazione vs operazione

[zouth]

Qual'e' piu' veloce?

int strlen(char *s) {
    char *p = s;

    while(*p != '\0')
        p++;
   
    return p - s;
}

o

int strlen(char *s) {
    int x = 0;
   
    while(s != '\0')
        x++;
        s++;
   
    return x - 1;
}

 

[driverfury]

Vediamo... controlliamo il codice compilato (https://godbolt.org/ utilizzo il compilatore gcc e come target platform scelgo x86_64):

La prima funzione viene compilata nel seguente codice Assembly:

strlen(char*):
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     rax, QWORD PTR [rbp-24]
        mov     QWORD PTR [rbp-8], rax
        jmp     .L2
.L3:
        add     QWORD PTR [rbp-8], 1
.L2:
        mov     rax, QWORD PTR [rbp-8]
        movzx   eax, BYTE PTR [rax]
        test    al, al
        jne     .L3
        mov     rax, QWORD PTR [rbp-8]
        sub     rax, QWORD PTR [rbp-24]
        pop     rbp
        ret

Nella seconda funzione ho dovuto correggere prima due errori:

1. La condizione del while (linea 4) deve essere

*s != 0

ovvero avevi mancato l'asterisco.

2. Dopo il while ci vogliono le parentesi graffe perché occorre un blocco di 2 istruzioni e non una singola istruzione, ovvero deve essere così:

while(*s != '\0') {
        x++;
        s++;
}

Dopo aver corretto questi due errori, procediamo a dare il codice in pasto al nostro compilatore di fiducia:

strlen(char*):
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-4], 0
        jmp     .L2
.L3:
        add     DWORD PTR [rbp-4], 1
        add     QWORD PTR [rbp-24], 1
.L2:
        mov     rax, QWORD PTR [rbp-24]
        movzx   eax, BYTE PTR [rax]
        test    al, al
        jne     .L3
        mov     eax, DWORD PTR [rbp-4]
        sub     eax, 1
        pop     rbp
        ret

Le prime tre righe e le ultime due di ambedue le routine sono standard per le funzioni C.

Il nucleo delle funzioni è ciò che vi è in mezzo.

Ora considera questo: in generale, la CPU fa i calcoli in maniera estremamente veloce mentre legge dalla memoria in maniera estremamente lenta.

Ora io vedo che la prima routine accede alla memoria (in scrittura o lettura) tramite le istruzioni mov e add 6 volte (3 volte nel loop e 3 volte fuori dal loop).

La seconda routine, invece, accede alla memoria 4 volte nel loop e 2 volte fuori dal loop. Ovvero potenzialmente è più lenta.

Occorre anche considerare che per 1 istruzione mov in più non è che cambi molto. Anche perché le CPU di oggi hanno anche le cache che ottimizzano i tempi di accesso in memoria.

Secondo me, più che concentrarsi sul fatto che una funzione impeghi 1 clock di CPU in più occorre concentrarsi dapprima sull'efficacia del software: ovvero scrivere codice che fa ciò che vogliamo che faccia. Ad esempio, prima ho individuato subito due bug nella seconda funzione che non l'avrebbero fatta funzionare come ci si aspettava.

Una volta che il codice funziona come vogliamo, possiamo pensare di ottimizzare rendendolo più efficiente/rapido.

My 2 cents

 

[St3ve]

Nel primo fai un assegnamento, n confronti, n incrementi e una sottrazione. Nel secondo (corretto) fai un assegnamento, n confronti, n incrementi su x, n incrementi su s e una sottrazione. Sulla carta il primo dovrebbe essere più veloce, poi puoi fare qualche microbenchmark per misurare di quanto.

Entrambi sono sicuramente più lenti del vero strlen o di qualsiasi strlen ottimizzato. FYI, glibc si fa questa roba qui e per diverse architetture (tra cui x86_64) hanno scritto direttamente il codice assembly che sfrutta le features avanzate dell'architettura.

 

[DispatchCode]

Un esempio semplice di quanto dice St3ve potrebbe essere questo (serve MSVC per compilare):

int my_strlen(const char* string) {
    
    int len = 0;
    __asm {
        xor   al, al
        mov   edi, string
        xor   ecx, ecx
        not   ecx
        cld
        repne scasb
        not   ecx
        dec   ecx
        mov   len, ecx
    };
    
    return len;
}

cld azzera il flag DF così che scasb incrementi EDI/ESI.
repne scasb ripete scansionando un byte alla volta ciò che trova in EDI, sino a atrovare il carattere terminatore (o in generale il valore contenuto in AL).
Ad ogni passo (repne scasb) ECX viene decrementato.

 

[Utente cancellato 277320]

Quale e' piu performante ?

Tutto un discorso legato a che compilatore usi (msvc, o gcc, clang, e molti altri etc etc), che opzioni di compilazione usi, e che ottimizzazioni usi.

Con moderni compilatori come gcc e -O3 (se cerchi la performance) il compilatore ottimizza comunque a sua scelta con molte sue decisioni.

0000000000001130 <astrlen>:
    1130:    80 3f 00                 cmpb   $0x0,(%rdi)
    1133:    74 1b                    je     1150 <astrlen+0x20>
    1135:    48 89 f8                 mov    %rdi,%rax
    1138:    0f 1f 84 00 00 00 00     nopl   0x0(%rax,%rax,1)
    113f:    00
    1140:    48 83 c0 01              add    $0x1,%rax
    1144:    80 38 00                 cmpb   $0x0,(%rax)
    1147:    75 f7                    jne    1140 <astrlen+0x10>
    1149:    29 f8                    sub    %edi,%eax
    114b:    c3                       ret
    114c:    0f 1f 40 00              nopl   0x0(%rax)
    1150:    31 c0                    xor    %eax,%eax
    1152:    c3                       ret
    1153:    66 2e 0f 1f 84 00 00     cs nopw 0x0(%rax,%rax,1)
    115a:    00 00 00
    115d:    0f 1f 00                 nopl   (%rax)

0000000000001130 <astrlen> (con 2 errori corretti):
1130: 80 3f 00 cmpb $0x0,(%rdi)
    1133:    74 23                    je     1158 <astrlen+0x28>
    1135:    31 c0                    xor    %eax,%eax
    1137:    66 0f 1f 84 00 00 00     nopw   0x0(%rax,%rax,1)
    113e:    00 00
    1140:    41 89 c0                 mov    %eax,%r8d
    1143:    48 83 c0 01              add    $0x1,%rax
    1147:    80 3c 07 00              cmpb   $0x0,(%rdi,%rax,1)
    114b:    75 f3                    jne    1140 <astrlen+0x10>
    114d:    44 89 c0                 mov    %r8d,%eax
    1150:    c3                       ret
    1151:    0f 1f 80 00 00 00 00     nopl   0x0(%rax)
    1158:    41 b8 ff ff ff ff        mov    $0xffffffff,%r8d
    115e:    44 89 c0                 mov    %r8d,%eax
    1161:    c3                       ret
    1162:    66 2e 0f 1f 84 00 00     cs nopw 0x0(%rax,%rax,1)
    1169:    00 00 00
    116c:    0f 1f 40 00              nopl   0x0(%rax)

Per altro piu codice non vuol dire meno performance. E in un moderno pc "cisc" difficile che guardando il codice assembly tu capisca la piu performante, tutto un discorso complesso di pipelines/cache/predictions etc. Piu chiaro invece su un micro 8bit con singola pipeline come un atmega o pic, dove la tua strlen si tradurrebbe in un codice che viene eseguito cosi come lo vedi.

Dunque, in un moderno pc per la "performace" devi eseguire un loop di milioni di cicli e misurare il tempo.