Per qualche strlen in più come ottimizzare la strlen in C - pt.2

col. Mortimer: Che succede ragazzo?
Il Monco: Niente vecchio... non mi tornavano i conti. Me ne mancava uno.

Ok, siamo pronti per la seconda parte di Per qualche dollaro in più (oops... ma non era Per qualche strlen in più?). Come giustamente diceva Il Monco, un buon programmatore fa sempre bene i conti, quindi in questo post analizzeremo i risultati di un benchmark che ho scritto ad hoc per questo scopo. (...si lo so, avevo anche promesso una sorpresa. Ci sarà...).

...niente vecchio... la strlen è un po' lenta oggi...

Allora, nel benchmark confronteremo i risultati (di velocità, ovviamente) delle quattro versioni di strlen() viste nello scorso post, e cioè: K&R, FreeBSD, glibc, e musl libc e il nostro punto di riferimento sarà, evidentemente, la strlen() di default del sistema, anche perché uno dei nostri obbiettivi è scoprire cosa usa di default Linux, che è, al solito, il nostro sistema di riferimento. Vediamo il codice del benchmark:

#include <stdint.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

// prototipi locali
size_t strlenKaR(const char *s);
size_t strlenFreeBSD(const char *str);
size_t strlenGlibc(const char *str);
size_t strlenMusl(const char *s);

int main(int argc, char* argv[])
{
    static char s[1000000000];
    clock_t t_start;
    size_t  result;
    clock_t t_end;
    double  t_passed;
    int i;

    // riempio la stringa di test
    for (i = 0; i < sizeof(s); i++) {
        if (i % 2)
            s[i] = 'a';
        else
            s[i] = 'u';
    }
    s[i - 1] = 0; // terminatore

    // esegue con strlen() di default e calcola tempo
    t_start  = clock();
    result   = strlen(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlen(s)        = %zu - Tempo trascorso: %f secondi\n", result, t_passed);

    // esegue con strlenKaR() e calcola tempo
    t_start  = clock();
    result   = strlenKaR(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenKaR(s)     = %zu - Tempo trascorso: %f secondi\n", result, t_passed);

    // esegue con strlenFreeBSD() e calcola tempo
    t_start  = clock();
    result   = strlenFreeBSD(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenFreeBSD(s) = %zu - Tempo trascorso: %f secondi\n", result, t_passed);

    // esegue con strlenGlibc() e calcola tempo
    t_start  = clock();
    result   = strlenGlibc(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenGlibc(s)   = %zu - Tempo trascorso: %f secondi\n", result, t_passed);

    // esegue con strlenMusl() e calcola tempo
    t_start  = clock();
    result   = strlenMusl(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenMusl(s)    = %zu - Tempo trascorso: %f secondi\n", result, t_passed);

    return 0;
}

Come avrete notato, abbiamo creato una stringa enorme (e se no che test era?) e l'abbiamo riempita di una sequenza di "au" (...beh, si poteva riempire di qualsiasi cosa, ma quel giorno mi ero svegliato con un "au" in testa che non vi dico...). Abbiamo aggiunto il dovuto terminatore di stringa e chiamato in sequenza le varie strlen() usando un metodo affidabile (con clock()) per verificare il tempo reale di attività (un metodo che abbiamo già usato in un vecchio post). Le strlen() sono, ovviamente, quelle dello scorso post (i codici li trovate li), ribattezzate come strlenKaR(), strlenFreeBSD(), strlenGlibc() e strlenMusl(), per distinguerle dall'unica funzione non locale, che è la strlen() di libreria. Come si nota per la versione K&R ho modificato il prototipo (e la definizione) per uniformarla alla strlen() standard.

Vediamo ora i risultati del benchmark con compilazione normale (-O0, che è il default e si può anche omettere) e con una notevole ottimizzazione (-O2, che è quella che si usa normalmente nei casi reali):

usando gcc -O0

aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tempo trascorso: 0.054814 secondi
strlenKaR(s)     = 999999999 - Tempo trascorso: 2.173237 secondi
strlenFreeBSD(s) = 999999999 - Tempo trascorso: 0.308145 secondi
strlenGlibc(s)   = 999999999 - Tempo trascorso: 0.252466 secondi
strlenMusl(s)    = 999999999 - Tempo trascorso: 0.304617 secondi

usando gcc -O2

aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tempo trascorso: 0.164509 secondi
strlenKaR(s)     = 999999999 - Tempo trascorso: 0.395466 secondi
strlenFreeBSD(s) = 999999999 - Tempo trascorso: 0.091599 secondi
strlenGlibc(s)   = 999999999 - Tempo trascorso: 0.102967 secondi
strlenMusl(s)    = 999999999 - Tempo trascorso: 0.091931 secondi

I risultati sono veramente interessanti. La strlenKaR() è, come ci aspettavamo, molto più lenta delle versioni che usano l'algoritmo descritto in ZeroInWord e, anche compilando con -O2, è più lenta delle altre compilate con -O0, anche se, comunque, il divario tra le versioni ottimizzate è minore di quello tra le non ottimizzate. Ripeto, siamo in un caso limite: la stringa misurata è veramente enorme, e con stringhe "normali" la differenza di prestazioni sarebbe molto più piccola, comunque è evidente che le versioni con algoritmo speciale vanno meglio e sono, giustamente, da preferire, specialmente ricordando che "le super-ottimizzazioni sono sicuramente raccomandabili per le piccole funzioni di uso frequente" (...e questa è una mia auto-citazione dal mio ultimo post...). Le tre funzioni strlenFreeBSD(), strlenGlibc e strlenMusl() hanno prestazioni ottime ed analoghe, visto che usano lo stesso algoritmo, e la versione glibc prevale leggermente compilando con -O0, mentre che compilando con -O2 la migliore è la musl, con la FreeBSD a ruota.

E veniamo alla parte sorprendente: pare che la strlen() di default è nettamente più veloce di tutte le altre compilando con -O0 mentre perde il vantaggio compilando con -O2. Quindi, almeno senza ottimizzazioni, sul mio sistema Linux la strlen() di default non è quella della glibc (come uno si aspetterebbe) ma è qualcos'altro. E cosa è, allora? Proviamo a commentare la linea "#include <string.h>" e a ricompilare, e vediamo cosa ci dice il compilatore...

aldo@mylinux:~/blogtest$ gcc -c -O0 strlens.c -o strlens.o
strlens.c: In function 'main':
strlens.c:35:16: warning: implicit declaration of function 'strlen'
     result   = strlen(s);
                ^
strlens.c:35:16: warning: incompatible implicit declaration of built-in function 'strlen'
strlens.c:35:16: note: include '<string.h>' or provide a declaration of 'strlen'

Ecco, pare che la strlen() di default sia una funzione implicita del compilatore gcc, quindi non si usa la versione della libreria e, del resto "...in alcuni casi queste funzioni possono essere addirittura inlineate e/o scritte in assembler..." (...e questa è un'altra mia auto-citazione dal mio ultimo post...). Per confermare tutto questo ho cercato una versione in assembler della strlen() e l'ho trovata qui su stackoverflow. Ho modificato leggermente Il codice (la originale non restituiva correttamente il risultato) e ho modificato il benchmark per usarla. Il codice è il seguente:

#include <immintrin.h>

// una possibile implementazione in assembler della strlen() implicita in gcc
size_t strlenAsm(const char* src)
{
    size_t result = 0;
    unsigned int tmp1;
    __m128i zero = _mm_setzero_si128(), vectmp;

    // A pointer-increment may perform better than an indexed addressing mode
    asm(
        "\n.Lloop:\n\t"
            "movdqu   (%[src], %[res]), %[vectmp]\n\t" // result reg is used as the loop counter
            "pcmpeqb  %[zerovec], %[vectmp]\n\t"
            "pmovmskb %[vectmp], %[itmp]\n\t"
            "add      $0x10, %[res]\n\t"
            "test     %[itmp], %[itmp]\n\t"
            "jz  .Lloop\n\t"

        "bsf %[itmp], %[itmp]\n\t"
        "add %q[itmp], %q[res]\n\t"                // q modifier to get quadword register.
        : [res] "+r"(result), [vectmp] "=&x" (vectmp), [itmp] "=&r" (tmp1)
        : [zerovec] "x" (zero)  // There might already be a zeroed vector reg when inlining
            , [src] "r" (src)
            , [dummy] "m" (*(const char (*)[])src) // this reads the whole object, however
                                                   // long gcc thinks it is not needed
                                                   // because of the dummy input
    );

    return result - tmp1 - 1;
}

e i risultati diventano così (con -O0, e con -O2 il risultato della strlenAsm() non cambia visto che, essendo in assembler, viene compilata a parte e senza ottimizzazioni, come si può notare nelle linee successive):

usando gcc -O0

aldo@mylinux:~/blogtest$ gcc -c strlenasm.c -o strlenasm.o
aldo@mylinux:~/blogtest$ gcc -c -O0 strlens.c -o strlens.o
aldo@mylinux:~/blogtest$ gcc strlens.o strlenasm.o -o strlens
aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tempo trascorso: 0.054087 secondi
strlenKaR(s)     = 999999999 - Tempo trascorso: 2.163937 secondi
strlenFreeBSD(s) = 999999999 - Tempo trascorso: 0.306909 secondi
strlenGlibc(s)   = 999999999 - Tempo trascorso: 0.251383 secondi
strlenMusl(s)    = 999999999 - Tempo trascorso: 0.305544 secondi
strlenAsm(s)     = 999999999 - Tempo trascorso: 0.061378 secondi

Ecco, il risultato canta: la versione implicita di gcc è scritta in assembler (e ripeto: non è affatto una scelta stranissima per piccole funzioni di libreria di uso frequente). Resta il mistero del perché compilando con -O2 (riguardare i risultati più sopra) la strlen() di default sembra non essere più la versione implicita, visto che le sue prestazioni peggiorano. Questo è un mistero che mi riprometto di risolvere prima o poi.

(...ma, visto che siamo ad Agosto, sicuramente durante le vacanze me ne dimenticherò, di solito mentre sono in spiaggia penso a ben altro...)

Ciao e al prossimo post!