Un'interfaccia minima:codice sia espressivo che veloce

Un'interfaccia minima:codice sia espressivo che veloce

Hai mai usato std::inserter per inserire gli output di un algoritmo STL in un contenitore ordinato come un std::set ?

E se l'hai fatto, non sei infastidito da come la sua interfaccia ti obbliga a specificare la posizione in cui inserire gli elementi nel set?

Trovo questo molto fastidioso, perché la maggior parte delle volte non abbiamo idea di dove dovrebbero andare all'interno del set nel momento in cui scriviamo il codice. Non conosciamo nemmeno i loro valori in anticipo. Questo è il set È compito di capire dove mettere i nuovi elementi e mantenere un ordine.

Quindi finiamo per attaccare il begin o il end dell'insieme come argomento per std::inserter , e questa informazione inutile si trova come un ospite non invitato nel mezzo dell'elegante festa STL:

std::vector<int> v = {1, 3, -4, 2, 7, 10, 8};
std::set<int> results;
 
std::copy(begin(v), end(v), std::inserter(results, end(results)));

In precedenza ci siamo imbattuti in sorted_inserter , fa la stessa cosa di std::inserter tranne che non devi specificare dove inserire gli elementi. Puoi specificarlo, se ti capita di sapere, e farà risparmiare tempo a set invece di cercare la sua posizione per te in questo caso. Ma per il resto il set se ne prende cura (proprio come quando chiamiamo il suo .insert metodo):

std::vector<int> v = {1, 3, -4, 2, 7, 10, 8};
std::set<int> results;
 
std::copy(begin(v), end(v), sorted_inserter(results));

Rimuovendo la chiamata all'iteratore finale, sorted_inserter rende il codice più diretto. Ma questo ha un impatto sulle prestazioni? Lo scopo di questo post è confrontare le prestazioni di sorted_inserter con lo standard std::inserter .

Per il bene dell'esempio useremo std::copy perché è l'algoritmo STL più semplice, ma sorted_inserter potrebbe essere utilizzato anche con altri algoritmi. E come ha notato l'utente di Reddit FbF_, in particolare questo non significa che dovremmo usare std::copy per aggiungere dati a un contenitore, poiché esistono modi migliori per inserire più elementi in un contenitore STL in modo efficiente.

Misura, misura, misura... bene facciamolo!

Per questo benchmark utilizzerò lo strumento sempre più popolare di Fred Tingaud, Quick-Bench.

Il test case che utilizziamo qui è questo:

  1. costruisci un vector<int> contenente 100 valori generati casualmente tra -100 e +100,
  2. copia il contenuto di questo vettore in un set<int> , utilizzando std::copystd::inserter(results, end(results))
  3. ripetere 2) un numero elevato di volte e misurare il tempo medio
  4. dividilo per il tempo impiegato da un benchmark vuoto, in modo da avere un riferimento no-op

Questi sono i risultati in blu sotto.

Forse passando begin(results) è migliore di end(results) ? Ho inserito un nuovo test case (è molto facile da fare con il banco rapido) per misurarlo. Questi sono i risultati in rosa sotto.

Infine, ho incluso un test case che utilizza sorted_inserter invece di std::inserter , rappresentato dai risultati in giallo sotto.

Ecco i risultati visivi:

Questi risultati ci permettono di interpretare due cose:

  • se non sei sicuro di cosa inserire come posizione in std::inserter , begin e end sembrano equivalenti in termini di prestazioni,
  • sorted_inserter è più veloce di std::inserter . Quanto sopra mostrano un aumento delle prestazioni del 44%. Questo benchmark è stato fatto in O3 (per gli altri livelli di ottimizzazione l'aumento è stato più vicino al 20%).

Ecco la corsa rapida al banco per questo test se vuoi giocarci.

Un'interfaccia minima

Perché sorted_inserter superare l'STL? Non deriva certo da un'implementazione più efficiente, perché quella STL è sicuramente implementata molto meglio.

Penso al problema di std::inserter è la sua interfaccia:sta facendo troppe cose contemporaneamente .

In effetti, ha senso specificare una posizione per un vector , perché non riesce a trovarlo da solo. Quindi std::inserter L'interfaccia di 's ha senso per il vettore. Ma sta anche cercando di funzionare per un set. Sta cercando di adattare tutti i contenitori contemporaneamente.

E std::inserter sta mandando il set sulla strada sbagliata, fornendo costantemente un suggerimento che non è quello giusto. È più un lavoro per il set che non fornire alcun suggerimento, perché il set prova il suggerimento prima di rendersi conto che era sbagliato e quindi deve comunque inserire l'elemento.

sorted_inserter fornisce piuttosto un'interfaccia minima (solo un contenitore, nessuna posizione), ma è specifica per i contenitori ordinati e non ha senso sui vettori. E fornisce anche l'interfaccia più elaborata che consente all'utente di fornire un suggerimento, anche se si tratta di un caso d'uso meno comune.

Penso che una lezione da trarre da questa analisi sia che è utile fornire almeno un'interfaccia minima, che soddisfi perfettamente i bisogni più elementari . Qui questa interfaccia consisterebbe nell'inserimento in un contenitore ordinato senza informazioni preliminari sulla posizione finale dei componenti inseriti. Ciò è particolarmente importante se questa necessità si verifica spesso, come nel caso di std::inserter su std::set .

In questo modo, avremo maggiori possibilità di progettare interfacce che consentano un codice sia espressivo che veloce.