Nei titoli e nei testi troverete qualche rimando cinematografico (ebbene si, sono un cinefilo). Se non vi interessano fate finta di non vederli, già che non sono fondamentali per la comprensione dei post...

Di questo blog ho mandato avanti, fino a Settembre 2018, anche una versione in Spagnolo. Potete trovarla su El arte de la programación en C. Buona lettura.

giovedì 8 agosto 2019

Lo chiamavano Jeeg OpenSSL
come scrivere TCP Server e Client con OpenSSL in C - pt.3

Enzo/Jeeg: T'è annata male, Zingaro! Si vòi diventà famoso te conviene torna' a fa' l'imitazione der Grande Fratello! 
Fabio/Zingaro: Era Buona Domenica, cojone!
E ci risiamo un'altra volta: anche per questa terza puntata di Lo chiamavano Jeeg Robot (oops: Lo chiamavano Jeeg OpenSSL) abbiamo due notizie, una buona e una cattiva. La buona è che questo post completa (finalmente) il discorso della libreria MySSL. La cattiva notizia è che ho, finalmente, scoperto che diventare ricchi e famosi col Software è veramente molto complicato... Un consiglio: iscrivetevi, invece, al casting del Grande Fratello, quello è il futuro! (no, è mejo Buona Domenica, cojone!).
...e usa sta' MySSL cojone!...
(...si lo so, lo so: nell'ultimo articolo avevo promesso che avremmo proseguito e approfondito il discorso errno/strerror disquisendo di reentrant/thread-safe: ma siamo ad agosto, e l'articolo promesso potrebbe risultare troppo pesante per chi ha già la testa (e anche il corpo, spero) in vacanza... Vi/mi faccio un favore: ne riparleremo a Settembre, così oltre alla depressione post-vacanze vi beccherete anche un articolo pesantone in grado di schiantarvi del tutto...

Allora: perché una terza puntata di Lo chiamavano Jeeg OpenSSL? Se ben ricordate (e se non vi ricordate questa è una occasione imperdibile per rileggere la parte 1 e la parte 2 della serie) abbiamo lasciato la saga con la proposta di una semplice libreria per scrivere in maniera user-friendly applicazioni che usano OpenSSL (che è in effetti un po' ostica da usare così com'è). Era una piccola libreria di smart-wrapper per alcune delle funzioni OpenSSL e l'avevo scritta ad-hoc per il blog, usando una struttura ultra-semplificata: era composta solo da due file, myssl.c e myssl.h, e doveva essere compilata e linkata direttamente con la applicazione che la usava (ad esempio un SSL Server).

Per questa terza parte del post ho deciso di rendere la libreria un po' più professionale, come struttura e come distribuzione, quindi l'ho rivoluzionata (abbastanza) e l'ho trasformata in un repository GitHub. La potete trovare qui (...in realtà già ai tempi della seconda parte del post il mio ottimo collega Andrea Simone Costa mi aveva suggerito di farlo, ma avevo rimandato la cosa a tempi più propizi, tipo ora...). Vi riporto subito il file README.md del repository GitHub così non ci perdiamo in chiacchiere (per l'occasione tradotto in Italiano, ma su GitHub lo trovate in Inglese): 
MySSL 
Un'interfaccia user-friendly per la libreria OpenSSL

Panoramica
----------
La libreria MySSL è una semplice interfaccia per la libreria OpenSSL che 
consente una scrittura user-friendly (in C o C++) di SSL Server e SSL Client.

Note
----
- Licenza GNU MySSL (omissis)
- Licenza OpenSSL (omissis)
- La libreria "OpenSSL" di riferimento è la ver.1.0.2g
- Attualmente la libreria MySSL supporta solo sistemi Linux

Installazione
-------------
Questa è attualmente una versione beta e utilizza un Makefile molto semplice: 
quindi per generare e testare la libreria MySSL è necessario eseguire alcuni 
passaggi manuali:

1. Posizionarsi nella directory src e generare la libreria con 
   "make clean && make". Questo genera una libreria condivisa (libmyssl.so) e 
   la copia nella directory tests/lib. Il header-file myssl.h viene copiato 
   nella directory tests/include.
2. Posizionarsi nella directory tests e generare i due programmi di test
   (sslserver e sslclient) con "make clean && make".
3. Leggere il paragrafo "Testing" di questo file per vedere come eseguire un 
   semplice test della libreria MySSL utilizzando due terminali.
4. Notare che in questa versione beta la libreria non viene installata 
   automaticamente, quindi per eseguire il test è necessario installare 
   libmyssl.so nel sistema oppure è possibile eseguire un'installazione 
   temporanea in entrambi i due terminali in questo modo:

   export LD_LIBRARY_PATH = "~/path-di-myssl-package/tests/lib"

La prossima versione della libreria MySSL utilizzerà Autotools per generare e 
installare automaticamente e per rendere il pacchetto portatile su molti sistemi
Unix-like.

Testing
-------
Due test sono forniti nelle directory tests/server e tests/client e si può 
modificare liberamente il codice sorgente in base alle proprie esigenze (è Free
Software :).

I due programmi di test sono un SSL Server e un SSL Client che utilizzano la 
libreria MySSL e, oltre a testare la libreria, possono servire da esempio su 
come scrivere codice usando la libreria MySSL.

Le due directory di test forniscono esempi di base (e funzionanti) dei 
certificati SSL utilizzati dalla libreria MySSL per funzionare.

Per un rapido test della libreria MySSL, è possibile eseguire i seguenti 
programmi in due shell aperte nelle directory tests/server e tests/client:

1. ./sslserver 8888
2. ./sslclient 127.0.0.1 8888

TODO list
---------
- Generazione e installazione della libreria con Autotools
- Documentazione
- Supporto Windows
Ecco, penso che il README.md sia più che sufficiente a descrivere la nuova MySSL (l'ho scritto apposta!), quindi approfitto dell'occasione per descrivere, invece, i passi che ho eseguito per trasformare una libreria con struttura semplice in una più complessa per GitHub: questa guida è generica ed è, ovviamente, molto soggettiva, ma secondo me potrebbe essere un buon spunto per tutti quelli che si accingono a fare una operazione del genere. Vediamo i passi che ho eseguito:
  1. Ho diviso il "sorgentone" originale myssl.c in più sorgenti, uno per ogni funzione della libreria (sslread.c, sslwrite.c, ecc.).
  2. Ho diviso il "headerone" originale myssl.h in due header, myssl.h (pubblico) e myssl-private.h (privato): i sorgenti della libreria MySSL includono entrambi i file, mentre gli applicativi che usano MySSL includeranno solo l'header pubblico.
  3. Ho aggiunto opportuni header in testa a tutti i file con varie informazioni descrittive (seguendo un po' lo stile dei manuali Unix/Linux e lo standard POSIX).
  4. Ho aggiunto opportuni header in testa a tutte le funzioni della libreria (seguendo un po' lo stile dei manuali Unix/Linux e lo standard POSIX).
  5. Ho tradotto tutto (header e commenti nei sorgenti) in inglese: sono tutt'altro che un esterofilo però, visto che GitHub è un sito di uso globale, bisogna dare una opportunità di lettura diretta a tutto il pubblico potenziale.
  6. Ho creato una struttura di directory semplice e funzionale: src (sorgenti della libreria) e tests (applicazioni di test): per entrambe ho scritto un Makefile. Il Makefile in src genera la libreria, mentre quello in tests genera le due applicazioni di test (un SSL Server e un SSL Client).
  7. Ho scritto i "canonici" file GitHub (README.md, LICENSE e .gitignore) e li ho copiati nella root-directory della libreria.
  8. E, finalmente, ho copiato tutto nel repository GitHub. Missione compiuta!
That's all folks! E buone vacanze!

Ciao e al prossimo post!

lunedì 8 luglio 2019

Errno miei
come funziona errno e come usarlo in C

(...una premessa: questo post è un remake di un mio vecchio post (anzi, di due). L'ho riadattato e "modernizzato" per pubblicarlo su quell'altro bel blog collettivo dove scrivo. Visto che le modifiche sono molte e (forse) interessanti, lo ripubblico anche qui. Questo potrebbe ripetersi in futuro...)
Mascetti: Tarapìa tapiòco! Prematurata la supercazzola, o scherziamo?
Vigile: Prego?
Mascetti: No, mi permetta. No, io... scusi, noi siamo in quattro. Come se fosse antani anche per lei soltanto in due, oppure in quattro anche scribàcchi confaldina? Come antifurto, per esempio.
Vigile: Ma che antifurto, mi faccia il piacere! Questi signori qui stavano sonando loro. 'Un s'intrometta!
Mascetti: No, aspetti, mi porga l'indice; ecco lo alzi così... guardi, guardi, guardi. Lo vede il dito? Lo vede che stuzzica? Che prematura anche? Ma allora io le potrei dire, anche con il rispetto per l'autorità, che anche soltanto le due cose come vicesindaco, capisce?
Vigile: Vicesindaco? Basta 'osì, mi seguano al commissariato, prego!
Perozzi: No, no, no, attenzione! Noo! Pàstene soppaltate secondo l'articolo 12, abbia pazienza, sennò posterdati, per due, anche un pochino antani in prefettura...
Mascetti: ...senza contare che la supercazzola prematurata ha perso i contatti col tarapìa tapiòco.
A volte penso che per spiegare come funziona e come usare errno sarebbe sufficiente usare una Supercazzola come quella dello specialista Mascetti nel capolavoro Amici Miei. Tanto nessuno ti ascolta, errno funziona e tanto basta, quindi perché approfondire? Beh, non sono d'accordo, ho visto (ahimè) molti usi impropri di errno, quindi un po' di sana teoria di base può far bene (anzi, fa sempre bene). Ovviamente gli eventuali "Masters of Errno" qui presenti potranno saltare a piè pari la lettura dell'articolo (che potrebbe risultare noioso, lo ammetto...).
...errno come se fosse antani...
Allora: cos'è errno? Molte funzioni di libreria e system calls in caso di errore aggiornano il valore di una variabile globale (errno, giust'appunto) che quindi contiene, in ogni momento, il valore dell'ultimo errore di esecuzione. Anticamente errno era definito così nel header (della libc) errno.h:
    extern int errno;
e si riferiva a una semplice variabile globale della libc, per l'appunto un int chiamato errno. Poi sono arrivati i thread, con lo standard POSIX 1003.1c (detto anche POSIX.1c, ma fa lo stesso) e quindi errno ha dovuto adeguarsi al modo thread-safe. Come si può ben leggere nel manuale di errno (dopo POSIX.1c) ora la definizione è:
    errno is defined by the ISO C standard to be a modifiable lvalue of
    type int, and must not be explicitly declared; errno may be a macro.
    errno is thread-local; setting it in one thread does not affect its
    value in any other thread.
Quindi la nuova definizione di errno è ora in bits/errno.h (che viene incluso dal errno.h classico). Semplificando un po' (ho omesso alcuni dettagli per facilitare la lettura) il nuovo giro del fumo è:
nel header-file errno.h
#include <bits/errno.h>
/* Declare the `errno' variable, unless it's defined as a macro by
   bits/errno.h.  This is the case in GNU, where it is a per-thread
   variable.  This redeclaration using the macro still works, but it
   will be a function declaration without a prototype and may trigger
   a -Wstrict-prototypes warning.  */
#ifndef errno
extern int errno;
#endif

nel header-file bits/errno.h
/* Function to get address of global `errno' variable. */
extern int *__errno_location (void);

/* When using threads, errno is a per-thread value. */
#define errno (*__errno_location ())
Quindi, in parole povere, ora errno non è più un int globale ma è "il contenuto di un indirizzo ritornato da una funzione globale". Ovviamente la variabile int a cui punta la funzione in oggetto è il nuovo errno locale di un thread (ossia: ogni thread ha il suo errno). Un esempio (mooolto semplificato) di come si potrebbe implementare la __errno_location() è il seguente:
// errno locale di un thread: è una variabile di tipo thread-local storage (TLS)
__thread int th_errno;

int *__errno_location(void)
{
    // ritorna l'indirizzo della variabile th_errno
    return &th_errno;
}
E, alla fine della fiera, nonostante i cambi descritti, sarà ancora possibile fare operazioni di questo tipo:
int my_errno = errno; // Ok, equivale a: int my_errno = (* __errno_location());
errno = EADDRINUSE;   // Ok, equivale a: (* __errno_location()) = EADDRINUSE;
perché, ovviamente, tutto è stato pensato per essere retro-compatibile, e quindi errno, nonostante ora sia una macro, deve ancora comportarsi come quando era un semplice int.

E, a questo punto, non possiamo farci mancare un piccolo estratto dello standard POSIX.1c, che puntualizza tutto quello detto fin'ora:
Redefinition of errno
In POSIX.1, errno is defined as an external global variable. But this definition
is unacceptable in a multithreaded environment, because its use can result in 
nondeterministic results. The problem is that two or more threads can encounter 
errors, all causing the same errno to be set. Under these circumstances, a thread 
might end up checking errno after it has already been updated by another thread. 

To circumvent the resulting nondeterminism, POSIX.1c redefines errno as a service 
that can access the per-thread error number as follows (ISO/IEC 9945:1-1996, n2.4): 

Some functions may provide the error number in a variable accessed through the 
symbol errno. The symbol errno is defined by including the header <errno.h>, as 
specified by the C Standard ... For each thread of a process, the value of errno 
shall not be affected by function calls or assignments to errno by other threads... 
E ora facciamo un passo avanti: come possiamo sfruttare l'esistenza di errno? A parte usarlo direttamente come numero e agire opportunamente nel codice in base all'errore indicato, è prassi abituale cercare la descrizione  dell'errore (come stringa di testo) con un meccanismo che ci viene gentilmente offerta dalla nostra amata libc: infatti, parallelamente a errno, viene mantenuta un'altra variabile globale, _sys_errlist, che contiene le stringhe corrispondenti a ogni error number, per cui (dettaglio importantissimo di cui molti si dimenticano) prima che qualche altra parte del programma in esecuzione alteri il valore di errno, si può localizzare in _sys_errlist la stringa di errore che vogliamo trattare. Questa ultima operazione si può fare usando la funzione strerror(), in una delle sue (tante) varianti.

Ebbene si: la strerror() ha molte personalità, quindi quale scelgo? la strerror() o la strerror_r()? E se uso quest'ultima quale scelgo, la versione XSI-compliant o la versione GNU-specific? (per non parlare, poi, delle altre varianti, la strerror_l(), la strerror_s(), ecc., ma queste sono varianti secondarie).

Cominciamo con la prima domanda: strerror() o strerror_r()? Anticamente esisteva solo la prima, ma poi, come detto sopra, sono apparsi i thread e anche qui sono cominciati i problemi, perché nel codice multithread ci sono alcune parti critiche dove bisognerebbe usare solo funzioni thread-safe. La strerror() non è dichiarata thread-safe nello standard, e per capire il perché basta analizzare una implementazione semplificata (però molto simile alle implementazioni reali che possiamo trovare nelle varie libc disponibili). Vai col codice!
#include <stdio.h> // stdio.h include sys_errlist.h che dichiara le variabili
                   // globali _sys_errlist (array errori) e _sys_nerr (num.errori)
static char buf[256]; // buffer globale statico per la stringa da ritornare

char *strerror(int errnum)
{
    // test se errnum è un valore valido
    if (errnum < 0 || errnum >= _sys_nerr || _sys_errlist[errnum] == NULL) {
        // errore sconosciuto: copio in buf un messaggio di errore generico
        snprintf(buf, sizeof(buf), "Unknown error %d", errnum);
    }
    else {
        // errore conosciuto: copio in buf il messaggio corrispondente
        snprintf(buf, sizeof(buf), "%s", _sys_errlist[errnum]);
    }

    // ritorno buf che ora contiene il messaggio di errore
    return buf;
}
risulta evidente dal codice (ben commentato, come sempre, così non devo spiegarlo riga per riga) che la strerror() non ritorna direttamente _sys_errlist[errnum] (e se fosse così sarebbe intrinsecamente thread-safe) ma compone un messaggio di errore (per trattare anche gli error number non validi) usando un buffer globale statico buf: quindi, se due thread di una applicazione usano (quasi) contemporaneamente la strerror() il contenuto di buf non sarà attendibile (prevale il thread che ha scritto per ultimo). 

(...apro una parentesi: non è vietato scrivere una strerror() che sia thread-safe, e in alcuni sistemi lo è: ma visto che secondo lo standard non lo è, non possiamo essere sicuri che sul sistema che stiamo usando (o sul sistema su cui, un giorno, girerà la applicazione che stiamo scrivendo) non ci sia una implementazione come quella appena descritta, quindi...)

Allora, per il Software multithread è nata la strerror_r() che è thread-safe. Come funziona? vai col codice!
#include <stdio.h> // stdio.h include sys_errlist.h che dichiara le variabili
                   // globali _sys_errlist (array errori) e _sys_nerr (num.errori)

char *strerror_r(int errnum, char *buf, size_t buflen);
{
    // test se errnum è un valore valido
    if (errnum < 0 || errnum >= _sys_nerr || _sys_errlist[errnum] == NULL) {
        // errore sconosciuto: copio in buf un messaggio di errore generico
        snprintf(buf, buflen, "Unknown error %d", errnum);
    }
    else {
        // errore conosciuto: copio in buf il messaggio corrispondente
        snprintf(buf, buflen, "%s", _sys_errlist[errnum]);
    }

    // ritorno buf che ora contiene il messaggio di errore
    return buf;
}
anche in questo caso si tratta di codice semplificato, ma molto vicino alla realtà: il trucco è semplice, invece di usare un buffer globale statico (che è la fonte dei problemi della strerror()) il chiamante della funzione si deve preoccupare di allocare e passare un buffer (e la sua lunghezza) alla strerror_r(). In questo modo il buffer che usa la strerror_r() è locale al thread che la chiama, e non può essere sovrascritto da un altro thread concorrente. Abbiamo sacrificato un po' di semplicità d'uso ma abbiamo ottenuto l'agognato comportamento thread-safe!

Ed ora aggiungiamo un po' di complicazione: la versione di strerror_r() appena mostrata è la GNU-specific. Ma, sfortunatamente, esiste anche la XSI-compliant, che è la seguente:
int strerror_r(int errnum, char *buf, size_t buflen);
Come si nota questa seconda versione non ritorna il buffer con la error-string, ma ritorna, invece, un codice di errore, e la stringa trovata bisogna ripescarla direttamente nel buffer che abbiamo passato. Per quanto riguarda il codice di ritorno è 0 in caso di successo e, in base alla versione di libc in uso, potrebbe ritornare -1 in caso di errore (settando errno al valore specifico di errore) oppure un valore positivo corrispondente a errno (bah, questo doppio comportamento non è proprio il massimo della semplicità d'uso...). Per usare questa versione o la GNU-specific bisogna giocare opportunamente con i flag _GNU_SOURCE, _POSIX_C_SOURCE e _XOPEN_SOURCE del preprocessore (come descritto nel manuale della strerror()).

Il motivo per cui esiste la versione XSI-compliant è descritto nello stesso  estratto dello standard POSIX.1c citato precedentemente, al posto dei puntini di sospensione finali c'è questa parte:
...In addition, all POSIX.1c functions avoid using errno and, instead, return the 
error number directly as the function return value, with a return value of zero 
indicating that no error was detected. This strategy is, in fact, being followed 
on a POSIX-wide basis for all new functions.
E ora siamo pronti per la seconda domanda: quale usiamo, la GNU-specific o la XSI-compliant? Beh, io direi che quando scriviamo del codice per trattare dei codici di errore probabilmente non ci interessa trattare anche gli errori generati in questa fase (e nella fase successiva, ecc., ecc., un loop infinito di ricerca degli errori!); ci interessa, invece, scrivere codice lineare e semplice... per toglierci il dubbio possiamo analizzare due piccoli esempi d'uso:
GNU-specific
if ((my_socket = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
    // errore socket()
    char errbuf[MAX_ERROR_LEN];    // buffer per strerror_r()
    printf("socket() error (%s)\n", strerror_r(errno, errbuf, sizeof(errbuf)));
    return EXIT_FAILURE;
}
XSI-compliant
if ((my_socket = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
    // errore socket()
    char errbuf[MAX_ERROR_LEN];    // buffer per strerror_r()
    int my_error = strerror_r(errno, errbuf, sizeof(errbuf)));
    if (! my_error)
        printf("socket() error (%s)\n", errbuf);
    else {
        // tratto l'errore (magari usando di nuovo strerror_r()?)
        ...
    }

    return EXIT_FAILURE;
}
Non so voi cosa ne pensate, ma io uso sempre la versione GNU-specific! A voi la scelta...

In conclusione: abbiamo analizzato, nel dettaglio, come funziona errno. Poi abbiamo visto come usarlo. E, ancora, abbiamo esaminato le varianti principali della strerror(), notando che, molto spesso, conviene usare la strerror_r() che è la versione thread-safe... Cosa ci manca da approfondire? Ah si, ecco: perchè la strerror_r() si chiama così? E perchè c'è una intera famiglia di funzioni che finiscono in "_r"? Uhm... la "_r" sta per reentrant che, al contrario delle credenze comuni, non è esattamente la stessa cosa di thread-safe... Si, forse dobbiamo approfondire ulteriormente... (SPOILER ALERT: sarà nel prossimo articolo!).

Ciao, e al prossimo post!

giovedì 13 giugno 2019

Un giorno di ordinaria STL
considerazioni sull'efficienza della STL del C++

(...una doverosa premessa: questo articolo è, apparentemente, sul C++. Quindi cosa ci fa in questo blog? Se vi fidate, leggetelo ugualmente, perché gli agganci col C ci sono, (eccome!). Se poi siete completamente refrattari al C++ o, più semplicemente, non è un linguaggio che usate abitualmente, saltatelo pure: non mi offendo...)
William Foster: [prende l'hamburger che ha appena ordinato e lo confronta con la foto dietro il bancone] Quello che mi ha fatto sempre rabbia è... voltatevi, guardate li. Quello è bello gonfio, pieno di salsa, alto 8 cm. Ora... guardate questa insignificante, squallida cosa... qualcuno sa dirmi in che assomiglia alla foto?
Nell'ottimo Un Giorno di Ordinaria Follia un Michael Douglas un po' stressato (eufemismo) scatena la sua rabbia su tutto ciò che incontra, evidenziando più volte la sua frustrazione di consumatore deluso. Ecco, visto che sono un po' stufo che ci vengano vendute le cose "per quel che dovrebbero essere" e non "per quello che sono" ho pensato di fare un po' di luce su un argomento usato e abusato da troppo tempo, quello della straordinaria efficienza della  C++ Standard Library (…STL per gli amici, e preciso: la diatriba sulla correttezza dell’uso e abuso del termine STL (Ok, lo so: è la Standard Template Library) non è oggetto di questo articolo…).
...questo hamburger ha una bassissima efficienza...
Cominciamo, allora, con un colloquio immaginario tra un William Foster arrabbiato (come al solito) e un programmatore entusiasta della STL:
programmatore: Ti raccomando la STL. È bella, completa, comodissima, facile da usare ed è anche molto efficiente.
William Foster: Si, hai ragione, la uso anch'io, funziona (quasi sempre) bene ed è comodissima, ma l'efficienza di cui parli... hai consultato qualche fonte affidabile? Hai scritto qualche benchmark? Insomma chi te l'ha detto?
programmatore: Mah, lo dicono in molti...
William Foster: Molti? Ma chi sono questi molti? Anzi chi è questo Signor Molti che te l'ha detto?
programmatore: Uhm... me l'ha detto mio cuggino...
Ecco, il problema è questo: molti (tra cui gli imparzialissimi creatori della STL) hanno sparso la voce della grande efficienza della STL, e bisogna credergli sulla fiducia, pena essere tacciati di essere dei miscredenti indegni di usare il C++. Ok, e allora sono sono un miscredente, e al cuggino del programmatore qui sopra non credo sulla parola, per cui, emulando San Tommaso, ho deciso di scrivere un bel benchmark...

Ovviamente il benchmark non può coprire tutta la STL (sarebbe un lavoro improbo, e non ho abbastanza tempo per farlo) ma ho pensato che, prendendo un classico problema che mette a prova l'efficienza (vedi un mio recentissimo articolo) e cioè il riempimento di una grande mole di dati, si potrebbe estrarre qualche risultato interessante. Quindi ho scelto alcuni STL Container adatti a questo scopo, e cioè: std::vector (il classico prezzemolino della STL) confrontato con un normale array C, e poi std::list e std::forward_list confrontate con una linked list C che ho scritto ad-hoc. Ok, bando alle ciance, vediamo un estratto semplificato del codice del benchmark per il vector:
// Test Array 1
int* array = (int*)malloc(arrsize * sizeof(int));
for (int i = 0; i < arrsize; i++)
    array[i] = i;

// Test Array 2
vector<int> array(arrsize);
for (int i = 0; i < arrsize; i++)
    array[i] = i;

// Test Array 3
vector<int> array;
array.resize(arrsize);     // alloca+crea istanze per il vector
for (int i = 0; i < arrsize; i++)
    array[i] = i;

// Test Array 4
vector<int> array(arrsize);
for (int i = 0; i < arrsize; i++)
    array.at(i) = i;

// Test Array 5
vector<int> array;
for (int i = 0; i < arrsize; i++)
    array.push_back(i);

// Test Array 6
vector<int> array;
array.reserve(arrsize);     // alloca spazio per il vector
for (int i = 0; i < arrsize; i++)
    array.push_back(i);
e, visto che non vedete l'ora di vedere i risultati, eccoli!

(...ma prima di mostrare e analizzare i risultati, una premessa: questo articolo può sembrare, apparentemente, come un redde rationem con i sostenitori della STL: nulla di più falso: sono anni che sorveglio l'evoluzione della STL e ho già scritto vari benchmark (per uso personale) per verificare eventuali progressi (e per decidere di volta in volta se, come e cosa usare). Fino a qualche anno fa i risultati della STL rispetto agli equivalenti in C puro erano abbastanza deludenti, e visto che di solito scrivo articoli sul C ho deciso di non parlare (quasi) mai dell'argomento, per evitare inutili polemiche e guerre fratricide tra i sostenitori dell'uno e dell'altro bando. Ma, come ho già scritto recentemente, i compilatori crescono e si fanno adulti e, in contemporanea, pare che anche il codice della STL sia stato migliorato. Quindi i risultati che sto per presentare sono decisamente buoni (alla faccia di chi mi accusa di essere parziale). Ciò non toglie che l'efficienza della STL era, fino a un po' di tempo fa, una vera e propria leggenda urbana...)
TEST con arrsize = 0xfffffff

TEST con compilazione g++ senza ottimizzazioni
Test Array 1: tempo trascorso: 0.931270 secondi
Test Array 2: tempo trascorso: 0.880625 secondi
Test Array 3: tempo trascorso: 0.868680 secondi
Test Array 4: tempo trascorso: 2.794937 secondi
Test Array 5: tempo trascorso: 4.442567 secondi
Test Array 6: tempo trascorso: 3.854844 secondi

TEST con compilazione g++ con ottimizzazione -O1
Test Array 1: tempo trascorso: 0.376887 secondi
Test Array 2: tempo trascorso: 0.107783 secondi
Test Array 3: tempo trascorso: 0.107272 secondi
Test Array 4: tempo trascorso: 0.164109 secondi
Test Array 5: tempo trascorso: 1.380443 secondi
Test Array 6: tempo trascorso: 0.863229 secondi

TEST con compilazione g++ con ottimizzazione -O2
Test Array 1: tempo trascorso: 0.375978 secondi
Test Array 2: tempo trascorso: 0.106973 secondi
Test Array 3: tempo trascorso: 0.106659 secondi
Test Array 4: tempo trascorso: 0.162633 secondi
Test Array 5: tempo trascorso: 1.358833 secondi
Test Array 6: tempo trascorso: 0.835997 secondi

TEST con compilazione g++ con ottimizzazione -O3
Test Array 1: tempo trascorso: 0.334696 secondi
Test Array 2: tempo trascorso: 0.109222 secondi
Test Array 3: tempo trascorso: 0.108441 secondi
Test Array 4: tempo trascorso: 0.163007 secondi
Test Array 5: tempo trascorso: 1.052935 secondi
Test Array 6: tempo trascorso: 0.528534 secondi
Ecco: finalmente possiamo dire che vector, senza ottimizzazioni, è efficiente almeno quanto la controparte in C puro, e con le ottimizzazioni (già con la -O1 di g++) si avvantaggia ulteriormente. Era ora! Soprattutto è importante il fattore dell'efficienza senza ottimizzazioni, perché dimostra che il codice è già efficiente di base, e ovvia al problema che, a volte, le ottimizzazioni non si possono usare (comunque, la -O1 di g++ è, normalmente, molto sicura). Evidentemente il benchmark testa solo il riempimento dell'array/vettore, che è, però, la parte più dispendiosa, quindi i risultati sono abbastanza significativi.

E, come avrete notato, per rendere il test più completo ho provato vari metodi di riempimento, ben cinque. E i risultati ci dicono che la maniera  migliore di usare vector è di allocare memoria e oggetti già in costruzione (passando la dimensione al costruttore o usando subito resize()) e poi accedere agli elementi usando l'operatore indice []. Il metodo at() non va altrettanto bene in versione base, ma si giova molto delle ottimizzazioni. Un capitolo a parte va scritto per il metodo push_back(): usandolo con un vector vuoto comporta la crescita progressiva (e dispendiosa) dello stesso, man mano che si riempiono gli elementi, ed i risultati non sono buoni, neanche con le ottimizzazioni. Si può ovviare parzialmente al problema usando il metodo reserve(), ma il miglioramento delle prestazioni non è epocale. 

Conclusione 1: usate pure vector senza remore, è il container raccomandato (a ragione) da Bjarne Stroustrup in persona, e ha raggiunto un notevole livello di maturità. Usatelo, però, in stile C (non so perché, ma mi viene da ridere scrivendo questo) attraverso l'operatore indice [].

E adesso possiamo passare alla seconda parte del test, quella delle liste: vediamo un estratto semplificato del codice:
// Test Lista 1
node_t* array = NULL;
for (int i = 0; i < arrsize; i++)
    addNode(&array, i);

// Test Lista 2
list<int> array;
for (int i = 0; i < arrsize; i++)
    array.push_front(i);

// Test Lista 3
list<int> array;
for (int i = 0; i < arrsize; i++)
    array.push_back(i);

// Test Lista 4
forward_list<int> array;
for (int i = 0; i < arrsize; i++)
    array.push_front(i);

// nodo di una linked list singola con campo dati
typedef struct snode {
    int data;
    struct snode* next;
} node_t;

// alloca in testa a una lista un node con i dati e un puntatore al prossimo elemento
void addNode(node_t** head, int data)
{
    // alloca un nuovo node
 node_t *node = (node_t*)malloc(sizeof(node_t));
 node->data = data;
 node->next = *head;

    // assegna head lista al nuovo node
    *head = node;
}
In questo caso la versione C di riferimento non è immediata come quella usata per vector (che sfruttava direttamente malloc()), ma è comunque elementare: si definisce un tipo nodo a link singolo, e si usa una semplicissima funzione addNode() per aggiungere nodi alla lista. Per comodità e coerenza ho chiamato ugualmente array la lista, anche se, evidentemente, non lo è (permettetemi questa frivolezza, grazie). E adesso passiamo ai risultati, eccoli!
TEST con arrsize = 0xffffff

TEST con compilazione g++ senza ottimizzazioni
Test Lista 1: tempo trascorso: 0.554599 secondi
Test Lista 2: tempo trascorso: 1.643846 secondi
Test Lista 3: tempo trascorso: 1.642775 secondi
Test Lista 4: tempo trascorso: 1.515138 secondi

TEST con compilazione g++ con ottimizzazione -O1
Test Lista 1: tempo trascorso: 0.536368 secondi
Test Lista 2: tempo trascorso: 0.580142 secondi
Test Lista 3: tempo trascorso: 0.580442 secondi
Test Lista 4: tempo trascorso: 0.546508 secondi

TEST con compilazione g++ con ottimizzazione -O2
Test Lista 1: tempo trascorso: 0.516421 secondi
Test Lista 2: tempo trascorso: 0.579874 secondi
Test Lista 3: tempo trascorso: 0.579059 secondi
Test Lista 4: tempo trascorso: 0.539288 secondi

TEST con compilazione g++ con ottimizzazione -O3
Test Lista 1: tempo trascorso: 0.528822 secondi
Test Lista 2: tempo trascorso: 0.579284 secondi
Test Lista 3: tempo trascorso: 0.579571 secondi
Test Lista 4: tempo trascorso: 0.540146 secondi
Ahimè, pare che list sia ancora un po' indietro rispetto alla controparte in C puro. Recupera un po' con le ottimizzazioni, ma non abbastanza. E a nulla è servito usare anche il nuovo container forward_list (che è una novità del C++11) che usa una singly linked list ed è, quindi, direttamente confrontabile col riferimento C (list, invece, è una doubly linked list). Anzi, considerando che forward_list è meno completa di list, alla fin fine tra le due conviene usare quest'ultima. Del resto si può ragionevolmente affermare che, al massimo, un STL Container può avere la stessa efficienza della controparte in C puro con l'aggiunta, però, di un notevole numero di utilità (metodi di accesso multipli, iteratori, allocatori, e chi più ne ha più ne metta): questo obbiettivo alcuni container (come vector) lo raggiungono, mentre altri (come list) non ci riescono. Ce ne faremo una ragione...

Conclusione 2: se non siete proprio dei pigroni usate con parsimonia list e forward_list, che funzionano bene ma non sono il massimo dell'efficienza. Tra l'altro (come diceva anche Bjarne Stroustrup nel link citato sopra), è quasi sempre possibile risolvere la stessa necessità usando vector (e se non è possibile scrivetevi voi una linked-list ad-hoc!).

(...ed ora la conclusione delle conclusioni: immagino che tra i lettori ci siano molti che, come me, alternano l'uso del C con l'uso del C++, oppure li usano in contemporanea. Ecco, in questo caso non fate come me: visto che mi viene abbastanza naturale e facile scrivere codice C di basso livello, quando uso a lungo il C e poi passo al C++ mi riduco a non usare quasi per nulla la STL (al massimo uso la std::string...) e questo non lo raccomando: se perdi l'abitudine a usarla poi ti dimentichi i trucchi del mestiere e, prima o poi, ti toccherà riprenderla da zero. Ricordate, però, che c'è anche un rovescio della medaglia: anche quelli che non alternano C e C++ e usano sempre, o quasi sempre, quest'ultimo, dovrebbero auto-imporsi di non diventare STL-dependent, perché un giorno potrebbero fare magre figure, anche solo per trattare una stringa senza usare std::string (giuro: ho visto fior di programmatori cadere su queste cose, gente terrorizzata da un doppio puntatore...). Quindi, usate la STL: è bella, completa, comodissima, facile da usare ed è (a volte) molto efficiente (e non è perfetta, se no come vi spiegate questo?),  ma, per favore, non scordatevi la programmazione di base!...)

Beh, per oggi può bastare. Ho tentato di fare un po' di luce su un argomento spinoso e (ahimè) sono sicuro di non avere accontentato tutti. E se qualcuno mi obbietta "Ma hai provato solo due STL Container dei 1000 disponibili, e solo in modo riempimento, senza testare i metodi di accesso, gli iteratori, ecc., ecc." che posso rispondere? È vero, ma come ho già detto sopra, sono ragionevolmente convinto che il test del principe dei container (vector) in modo riempimento è una prova molto effettiva e rappresentativa dello stato dell'arte della STL in generale (e il confronto con le liste aggiunge un tocco di completezza che non guasta mai).

Comunque in rete ci sono vari test molto esaustivi che confrontano tra di loro gli STL Container in tutti i loro aspetti, ma... mancano sempre i test di paragone con il codice C base della funzionalità in oggetto, e qui arrivo io a colmare la mancanza. E la mia grande speranza è che, dopo la lettura di questo articolo, nessuna debba più affermare che la STL è efficiente solo perché glielo ha detto suo cuggino...

Ciao e al prossimo post!

lunedì 6 maggio 2019

2001: Odissea nell'ottimizzazione
considerazioni sull'ottimizzazione del codice in C

HAL9000: Nessun calcolatore 9000 ha mai commesso un errore o alterato un'informazione. Noi siamo, senza possibili eccezioni di sorta, a prova di errore, e incapaci di sbagliare.
In 2001: Odissea nello spazio il computer HAL9000 era così sicuro di essere infallibile che sabotò la missione (oops: spoiler!... va beh, ma è un film del 1968, se non l'avete ancora visto sarà mica colpa mia...). Ecco, in questo articolo tratteremo un argomento spinoso, l'ottimizzazione del codice, che andrà a toccare miti e leggende (urbane) su cui molti colleghi programmatori hanno certezze magari un po' datate. Sarò costretto a dire delle eresie, delle cose poco ortodosse, ma cercherò, come sempre, di usare un linguaggio il più possibile soft, perché non mi sento ancora preparato per finire sul rogo dell'Inquisizione Informatica.
...ottimizzare il codice noonnnn serxyzh!!11wu?ve aaa nizxrn!!11mm-x?ente....
Come ho appena detto: un tema spinoso, su cui ho già scritto in passato. Ma i tempi cambiano, l'informatica avanza, i compilatori crescono e si fanno adulti... e il mio vecchio articolo è diventato obsoleto (anzi, peggio: deprecated), e non ho nessuna difficoltà ad ammetterlo (non sono mica HAL9000!): i risultati dei test di allora (era il 2012) ora non sono più validi. E quindi non sono più valide neanche le conclusioni. Comunque, prima di andare avanti vi spoilero il piano dell'articolo, così nessuno potrà dire che non vi avevo avvertito prima (potete saltare la lettura del piano se vi piacciono le sorprese: attenzione SPOILER):

Piano dell'articolo
  1. Le basi: la descrizione sommaria di cosa è e cosa non è una ottimizzazione.
  2. L'illusione: la descrizione di alcune promettenti forme di ottimizzazione (solo alcune tra le mille disponibili, eh!).
  3. La delusione: il test sperimentale che dimostra l'inutilità del punto 2.
  4. Il Gran Finale: le ultime considerazioni e le parole di un profeta che aveva già previsto tutto questo.
1. Le basi
Chiariamo subito una cosa: le ottimizzazioni di cui parleremo sono quelle strettamente legate al codice, alle istruzioni di base. Non si parla di algoritmi, perché è evidente che quelli si che devono essere ottimizzati: se voglio fare un sort dei valori in un grande array è meglio scrivere un quick-sort che un insertion-sort! E, tornando alle istruzioni di base, anche qui bisogna fare dei distinguo: ad esempio, se devo aggiungere cinque volte lo stesso un valore ad una variabile e lo faccio con un loop non è una ottimizzazione, è semplice senso comune! Quindi vediamo un po' di codice per spiegare meglio l'argomento:
#include <stdio.h>
#include <time.h>

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // VERSIONE STUPIDA (senza senso comune)
    int i = 0;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;

    printf("Test 1: array[4] = %d\n", array[4]);

    // VERSIONE BASE (con senso comune)
    int n;
    for (n = 0; n < 5; n++)
        array[n] = n * 2;

    printf("Test 2: array[4] = %d\n", array[4]);

    // VERSIONE OTTIMIZZATA: è la base con shift logico invece di moltiplicazione
    int k;
    for (k = 0; k < 5; k++)
        array[k] = k << 1;

    printf("Test 3: array[4] = %d\n", array[4]);

    return 0;
}
Come si nota nel semplicissimo esempio, abbiamo un problema e lo possiamo risolvere in maniera "stupida", "normale" o "ottimizzata": sulla maniera "stupida" preferisco non commentare, mentre su quella ottimizzata faccio notare che ho usato uno Shift Logico al posto della (dispendiosa) moltiplicazione per due.

E per chiudere questa sezione non posso non citare una tra le tante Leggende Urbane che girano nella comunità C: quella secondo cui è meglio mettere la definizione di una variabile fuori da un loop "se no ogni volta che si entra nel loop viene allocata nuovamente e il programma rallenta"... Quindi, secondo alcuni, quando è stato introdotto nel C il concetto di scope grazie al quale possiamo (tra le altre cose) dichiarare e usare una variabile solo dove serve, si sono dimenticati di dirci di non usare questa caratteristica perché "rallenta il codice"... ma si, continuiamo così, facciamoci del male. Vabbè, vi propongo un piccolo esempio di codice da compilare per estrarre l'assembly (ad esempio con gcc -S): vedrete che le due funzioni (una con variabile dentro il loop e l'altra con la variabile fuori) generano lo stesso codice: Leggenda Urbana, confermato.
#include <stdio.h>

// prototipi locali
int test1(int array[], int nelems);
int test2(int array[], int nelems);

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // Test 1
    test1(array, 5);
    printf("Test 1: array[4] = %d\n", array[4]);

    // Test 2
    test2(array, 5);
    printf("Test 2: array[4] = %d\n", array[4]);

    return 0;
}

// funzione test1()
int test1(
    int array[],
    int nelems)
{
    // riempio array
    int n;  // n dichiarato fuori dal loop
    int i;
    for (i = 0; i < nelems; i++) {
        n = i * 2;
        array[i] = n;
    }
}

// funzione test2()
int test2(
    int array[],
    int nelems)
{
    // riempio array
    int i;
    for (i = 0; i < nelems; i++) {
        int n;  // n dichiarato dentro il loop
        n = i * 2;
        array[i] = n;
    }
}
2. L'illusione
Allora, stiamo parlando di ottimizzazione del codice, quindi di un argomento vastissimo (ci sono moltissime tecniche e moltissimi casi), ma visto che il tempo e la dimensione dell'articolo hanno dei limiti cercheremo di ottimizzare (!?) focalizzandoci solo su un tipo classico, anche perché il risultato finale (come vedremo nel punto 3) dovrebbe essere sempre (più o meno) lo stesso. E quale è la principale fonte di lentezza in una applicazione? ma è lui, è il (grande) loop! Quindi ho scritto sei piccoli esempi che riprendono i casi "base" e "ottimizzato" dell'esempio nel punto 1, vediamoli:

// TEST 1 - versione con moltiplicazione, array e indice
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i * 2;

// TEST 2 - versione con calcolo incrementale invece di moltiplicazione
int array[1000];
int i, incr;
for (i = 0, incr = 0; i < 1000; i++) {
    array[i] = incr;
    incr += 2;
}

// TEST 3 - versione con calcolo incrementale e pointer invece di array
int array[1000];
int *ptr = array;
int i, incr;
for (i = 0, incr = 0; i < 1000; i++, ptr++) {
    *ptr = incr;
    incr += 2;
}

// TEST 4 - versione con calcolo incrementale, pointer e senza indice
int array[1000];
int *ptr = array;
int limit = 1000 * 2;
int incr;
for (incr = 0; incr < limit; incr += 2, ptr++)
    *ptr = incr;

// TEST 5 - versione con shift logico invece di moltiplicazione
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i << 1;

// TEST 6 - versione con shift logico e pointer invece di array
int array[1000];
int *ptr = array;
int i;
for (i = 0; i < 1000; i++, ptr++)
    *ptr = i << 1;
Evidentemente la funzione Test 1 (già vista all'inizio dell'articolo) è semplicissima, però contiene un loop, e se la dimensione dell'array è molto grande potrebbe diventare dispendiosa. Ho provato a ottimizzarla usando due tecniche, la Strength Reduction e la Induction Variable, e attraverso vari passaggi (Test 2 e Test 3) si arriva alla versione super-ottimizzata in Test 4. Dato che c'ero ho riproposto in Test 5 la versione semplice ma con shift logico al posto della moltiplicazione e, infine, in Test 6 troviamo un ibrido con pointer al posto dell'array e shift logico al posto della moltiplicazione.

E a questo punto è doveroso uscire dalla teoria ed entrare nella pratica, quindi ho scritto un piccolo benchmark per analizzare i risultati delle varie versioni. Ho usato un grandissimo loop (se no i risultati sarebbero stati impossibili da valutare) e... vediamo i risultati (con GCC 7.4.0/Linux 4.15.0/Intel I7):

TEST con array di dimensione 0xfffffff

TEST con compilazione gcc senza ottimizzazioni
Test 1: Tempo trascorso: 0.903985 secondi
Test 2: Tempo trascorso: 0.881661 secondi
Test 3: Tempo trascorso: 0.863433 secondi
Test 4: Tempo trascorso: 0.844027 secondi
Test 5: Tempo trascorso: 0.899836 secondi
Test 6: Tempo trascorso: 0.896226 secondi

TEST con compilazione gcc con ottimizzazione -O1
Test 1: Tempo trascorso: 0.366814 secondi
Test 2: Tempo trascorso: 0.365151 secondi
Test 3: Tempo trascorso: 0.352550 secondi
Test 4: Tempo trascorso: 0.351188 secondi
Test 5: Tempo trascorso: 0.366156 secondi
Test 6: Tempo trascorso: 0.356479 secondi

TEST con compilazione gcc con ottimizzazione -O2
Test 1: Tempo trascorso: 0.359824 secondi
Test 2: Tempo trascorso: 0.363385 secondi
Test 3: Tempo trascorso: 0.362589 secondi
Test 4: Tempo trascorso: 0.356611 secondi
Test 5: Tempo trascorso: 0.361608 secondi
Test 6: Tempo trascorso: 0.362675 secondi

TEST con compilazione gcc con ottimizzazione -O3
Test 1: Tempo trascorso: 0.299029 secondi
Test 2: Tempo trascorso: 0.286266 secondi
Test 3: Tempo trascorso: 0.290292 secondi
Test 4: Tempo trascorso: 0.287927 secondi
Test 5: Tempo trascorso: 0.305653 secondi
Test 6: Tempo trascorso: 0.316873 secondi
Allora: effettivamente la versione Test 4 va meglio delle altre, ma il miglioramento è irrisorio, e i risultati con le ottimizzazioni del compilatore... beh, forse è meglio passare al punto 3.

3. La delusione
Ebbene si: dai risultati dei test si evince che:
  • le "ottimizzazioni manuali" sono poco effettive.
  • il compilatore ottimizza molto meglio di noi (ma che strano!), perfino usando la blanda opzione -O1.
  • il compilatore ottimizza un po' anche senza dirglielo, vedi il risultato (senza ottimizzazioni) di Test 1 rispetto a quello di Test 5, ad esempio.
Il fatto è (e bisogna farsene una ragione) che le ottimizzazioni descritte (Strength Reduction, Induction Variable, e mille altre) le usa già il compilatore, nei punti e nelle maniere che ritiene più opportune, e quindi, se noi cerchiamo di ottimizzare già a livello di scrittura delle istruzioni base, stiamo perdendo tempo e energie per un lavoro che non è compito nostro (questo magari non era vero in passato ma ora lo è). Ed è altamente probabile che il compilatore farà questo lavoro meglio di noi. Ovviamente qui abbiamo visto solo una minima parte delle possibili "ottimizzazioni manuali" ma, in generale, il discorso fatto vale per tutte.

Solo mi preme precisare che le ottimizzazioni forzate (con GCC sono indicate con -O1, -O2 e -O3) bisogna usarle con cautela crescente in base al numero: -O1 si può usare quasi sempre, mentre -O2 in alcuni casi particolari può provocare comportamenti strani e -O3 è ancora più critico: infatti bisogna ricordarsi che un compilatore, anche se buono, è stato scritto da persone (non da HAL9000!) quindi può anche contenere bugs, e poi il processo di ottimizzazione interno è abbastanza complicato, anche perché contiene delle "decisioni" interne del compilatore che con un codice possono funzionare perfettamente mentre con un altro codice non funzionano altrettanto bene. Detto questo credo che ora siamo pronti per il punto 4.

4. Il Gran Finale
Nel mio vecchio articolo chiedevo: "Quando scrivo codice devo farlo in maniera naturale, o meglio, istintiva (beh, sempre se si possiede l'istinto del Programmatore...) o devo seguire linee un po' astruse ed ermetiche per rendere il programma più efficiente?". E chiedevo anche: "Vale la pena di trasformare un codice leggibile e chiaro come quello di Test 1 in uno molto più criptico, come ad esempio quello di Test 4, solo perché non ci fidiamo del compilatore?". La risposta è evidente: lasciamo questo lavoro al compilatore e concentriamoci sullo scrivere del buon codice, chiaro, leggibile, manutenibile, ben strutturato, con una architettura coerente e solida, ecc., ecc.: vivremo più tranquilli e faremo anche un bel favore a chi dovrà, un giorno, mettere le mani sul nostro lavoro. 

E, come promesso, concludo con le parole di un profeta, uno di quelli che hanno scritto la storia dell'informatica e da cui c'è sempre qualcosa da imparare, anche a distanza di molti anni:
"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming" [Donald Ervin Knuth, "Computer Programming as an Art", 1974]
Ciao e al prossimo post!