C++ e strutture dati (Bajo.it)
In genere mi piace il C++ e il modo in cui si sente il C++, ma c’è una stranezza specifica che è causata dalla scelta di strutture dati da parte dei progettisti STL che non possono essere implementate con una semantica copy-on-write (nota anche come COW).
Curioso di sapere quale stranezza? Continua a leggere! COW potrebbe sembrare un dettaglio di implementazione, ma può davvero cambiare il modo in cui progetti le tue API.
Cos’è un COW?
Un oggetto con semantica COW (a volte chiamata anche “condivisione implicita”) ha una proprietà interessante: ogni volta che lo copi, non esegue realmente una “copia profonda” ma semplicemente condivide i dati sottostanti tra l’oggetto originale e la sua copia, e incrementa un contatore di riferimento per tracciarlo. Solo nel momento in cui una qualsiasi delle copie viene ulteriormente modificata (scritta), la copia profonda viene effettivamente eseguita.
Ora, è importante rendersi conto che l’overhead imposto dalla semantica COW è solitamente molto piccolo: l’oggetto deve solo tenere un contatore ad ogni copia, e controllarlo prima di qualsiasi modifica. Quest’ultimo è ancora più leggero di quanto sembri perché il compilatore può eliminare molti controlli grazie alle propagazioni costanti.
Ma quali sono i vantaggi dell’utilizzo di COW? Il primo e più importante vantaggio è la possibilità di avere un’API pulita rispetto ai valori restituiti.
Restituire un COW
Se hai programmato C++ abbastanza a lungo, sai che tutte le funzioni C++ che dovrebbero restituire una struttura dati complessa (qualsiasi cosa che sia più grande di una piccola struttura, come un contenitore, un buffer di memoria e così via) accetteranno invece un riferimento o un puntatore ad un oggetto che il chiamante dovrà fornire e che verrà “compilato” come valore di ritorno. Questo è assolutamente orribile. Se non lo consideri terribile, è giunto il momento di prenderti una pausa dal C++ e passare ad altri linguaggi per un po’. Per esempio:
std::vettore nodi;
cur_node.children(nodi);
printf(“Numero di figli: %u\n”, nodes.size());
La funzione Node::children(), in qualsiasi altro linguaggio, avrebbe restituito un vettore di Nodi. Ma il C++ idiomatico dice che non dovresti imporre il sovraccarico di fare una copia aggiuntiva del vettore al tuo utente, e quindi chiedergli di passarti il contenitore da riempire. Questo è davvero illeggibile perché rompe la sintassi comune delle funzioni mescolando i valori restituiti agli argomenti. Inoltre, impone ulteriori problemi all’API; es: cosa succede se chiami Node::children() con un vettore non vuoto? La funzione aggiungerà semplicemente i suoi dati al vettore? Oppure lo chiarirebbe all’inizio?
Ora, pensa a un mondo in cui std::vettore è una struttura dati COW. Tutti questi problemi scompaiono improvvisamente perché la restituzione del vettore non causerebbe più una copia. Bam, problema risolto! E quando hai un’API chiara, in cui i valori restituiti sono realmente valori restituiti, ne ottieni tutti i vantaggi:
printf(“Numero di figli: %u\n”, cur_node.children().size());
Tre linee fuse in una. Niente più variabili con nome temporaneo. E se Node memorizza internamente i suoi figli come vettore, questo codice è ancora più veloce della versione non COW, perché non viene eseguita alcuna copia: ottieni la stessa velocità come se children() restituisse un riferimento al codice interno vettore, anche se non è così.
COW in soccorso
Altri vantaggi delle strutture dati COW:
- È possibile nidificare le strutture dati COW senza sovraccarico. Pensa a un vettore<vettore>. Senza COW, ogni volta che la struttura dati esterna viene ridimensionata, le strutture dati interne verranno tutte riallocate e copiate. Con COW non esiste alcuna copia: le strutture dati interne vengono sostanzialmente spostate in tempo costante;
- Puoi smettere di abusare dei riferimenti const ovunque. In C++, la maggior parte delle funzioni riceveranno argomenti tramite riferimenti const anziché valori semplici. Ancora una volta, questo serve per risparmiare il sovraccarico di una copia, e ancora una volta questo è quasi inutile con le strutture dati COW. Anche i riferimenti const sono sgradevoli perché rappresentano una prima perdita di correttezza const nel tuo codice (odio anche tutta la correttezza const in C++, ma questo è per un altro giorno; se ti piace, puoi ancora fare in modo che le tue funzioni accettino const valori se lo senti anche tu).
COW norvegesi
Qt di Nokia ha progettato tutti gli oggetti e le strutture dati con COW. Li hanno persino resi rientranti (per scopi multithreading) utilizzando il conteggio dei riferimenti atomici tramite istruzioni native della CPU. Infine, espongono le viscere di COW attraverso un semplice modello QSharedData che puoi utilizzare per reimplementare i tuoi oggetti COW.
Non potrei essere più d’accordo con i designer di Qt.
Questo è un altro esempio di come il COW possa influenzare positivamente la progettazione dell’API:
QByteArray fileHash(QString fn)
{
QFile f(fn);
QCryptographicHash h(QCryptographicHash::Sha1);
mentre (!f.atEnd())
h.addData(f.read(16*1024));
return h.risultato();
}
Scopri come posso semplicemente passare il buffer restituito da QFile::read() a addData() senza dovermi preoccupare della copia della memoria.