Un giorno di ordinaria STL
considerazioni sull’efficienza della STL del C++
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!
