col. Mortimer: Che succede ragazzo?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à...).
Il Monco: Niente vecchio... non mi tornavano i conti. Me ne mancava uno.
 |
| ...niente vecchio... la strlen è un po' lenta oggi... |
#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 secondiI 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 secondiEcco, 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!
