Come eseguire correttamente il benchmark di un programma C ++ [modello]

Question

lt &; backgound gt &;

Sono in un punto in cui ho davvero bisogno di ottimizzare il codice C ++. Sto scrivendo una libreria per simulazioni molecolari e devo aggiungere una nuova funzionalità. Ho già provato ad aggiungere questa funzione in passato, ma poi ho usato funzioni virtuali chiamate in loop nidificati. Ne ho avuto cattive sensazioni e la prima implementazione ha dimostrato che questa era una cattiva idea. Tuttavia, questo andava bene per testare il concetto.

lt &; / Sfondo gt &;

Ora ho bisogno che questa funzione sia il più veloce possibile (anche senza il codice assembly o il calcolo GPU, questo deve essere ancora C ++ e più leggibile che meno). Ora so qualcosa di più sui modelli e le politiche di classe (dall'eccellente libro di Alexandrescu) e penso che una generazione di codice in fase di compilazione possa essere la soluzione.

Tuttavia, devo testare il progetto prima di fare il enorme lavoro di implementazione nella libreria. La domanda riguarda il modo migliore per testare l'efficienza di questa nuova funzionalità.

Ovviamente ho bisogno di attivare le ottimizzazioni perché senza questo g ++ (e probabilmente anche altri compilatori) manterrebbero alcune operazioni non necessarie nel codice oggetto. Ho anche bisogno di fare un uso pesante della nuova funzionalità nel benchmark perché un delta di 1e-3 secondi può fare la differenza tra un design buono e uno cattivo (questa funzione verrà chiamata milioni di volte nel programma reale).

Il problema è che a volte g ++ è " troppo intelligente " ottimizzando e rimuovendo un intero ciclo se si considera che il risultato di un calcolo non viene mai utilizzato. L'ho già visto una volta guardando il codice assembly di output.

Se aggiungo un po 'di stampa a stdout, il compilatore sarà quindi costretto a fare il calcolo nel ciclo, ma probabilmente farò un benchmark per lo più dell'implementazione di iostream.

Quindi, come posso fare un benchmark corretto di una piccola funzionalità estratta da una libreria? Domanda correlata: è un approccio corretto eseguire questo tipo di test in vitro su una piccola unità o ho bisogno dell'intero contesto?

Grazie per i consigli!

---

Sembra che ci siano diverse strategie, dalle opzioni specifiche del compilatore che consentono la messa a punto di soluzioni più generali che dovrebbero funzionare con ogni compilatore come volatile o extern.

Penso che proverò tutti questi. Grazie mille per tutte le tue risposte!

Answer 1

Se vuoi forzare qualsiasi compilatore per non scartare un risultato, fallo scrivere su un oggetto volatile. Tale operazione non può essere ottimizzata, per definizione.

template<typename T> void sink(T const& t) {
   volatile T sinkhole = t;
}

Nessun overhead di iostream, solo una copia che deve rimanere nel codice generato. Ora, se stai raccogliendo risultati da molte operazioni, è meglio non scartarli uno per uno. Queste copie possono ancora aggiungere un certo sovraccarico. Invece, in qualche modo raccogli tutti i risultati in un singolo oggetto non volatile (quindi sono necessari tutti i singoli risultati) e quindi assegna quell'oggetto risultato a un volatile. Per esempio. se le singole operazioni producono stringhe, è possibile forzare la valutazione sommando tutti i valori dei caratteri modulo 1 < < 32. Questo aggiunge quasi nessun sovraccarico; le stringhe saranno probabilmente nella cache. Il risultato dell'addizione verrà successivamente assegnato alla volatile, pertanto in realtà ogni carattere di ogni puntura deve essere calcolato, senza scorciatoie consentite.

Answer 2

A meno che tu non abbia un compilatore davvero aggressivo (può succedere), suggerirei di calcolare un checksum (aggiungi semplicemente tutti i risultati insieme) e di generare il checksum.

A parte questo, potresti voler esaminare il codice assembly generato prima di eseguire qualsiasi benchmark in modo da poter verificare visivamente che tutti i loop siano effettivamente in esecuzione.

Answer 3

I compilatori possono eliminare solo rami di codice che non possono accadere. Finché non può escludere che un ramo debba essere eseguito, non lo eliminerà. Finché c'è qualche dipendenza dai dati da qualche parte, il codice sarà lì e verrà eseguito. I compilatori non sono troppo intelligenti nel stimare quali aspetti di un programma non verranno eseguiti e non ci provano, perché si tratta di un problema NP e difficilmente calcolabile. Hanno alcuni semplici controlli come if (0), ma questo è tutto.

La mia modesta opinione è che potresti essere stato colpito da qualche altro problema in precedenza, come il modo in cui C / C ++ valuta le espressioni booleane.

Ma comunque, dato che si tratta di un test di velocità, puoi verificare che le cose vengano chiamate per te stesso: eseguilo una volta senza, poi un'altra volta con un test di valori di ritorno. O una variabile statica viene incrementata. Alla fine del test, stampare il numero generato. I risultati saranno uguali.

Per rispondere alla tua domanda sui test in vitro: Sì, fallo. Se la tua app è così critica in termini di tempo, fallo. D'altra parte, la tua descrizione suggerisce un problema diverso: se i tuoi delta sono in un intervallo di tempo di 1e-3 secondi, allora sembra un problema di complessità computazionale, poiché il metodo in questione deve essere chiamato molto, molto spesso (per poche corse, 1e-3 secondi è trascurabile).

Il dominio problematico che stai modellando sembra MOLTO complesso e i set di dati sono probabilmente enormi. Queste cose sono sempre uno sforzo interessante. Assicurati di avere prima le strutture e gli algoritmi di dati giusti per primi, e poi micro-ottimizza tutto ciò che desideri. Quindi, direi prima di tutto l'intero contesto. ;-)

Per curiosità, qual è il problema che stai calcolando?

Answer 4

Hai molto controllo sulle ottimizzazioni per la tua compilation. -O1, -O2 e così via sono solo alias per un gruppo di switch.

Dalle pagine man

       -O2 turns on all optimization flags specified by -O.  It also turns
       on the following optimization flags: -fthread-jumps -falign-func‐
       tions  -falign-jumps -falign-loops  -falign-labels -fcaller-saves
       -fcrossjumping -fcse-follow-jumps  -fcse-skip-blocks
       -fdelete-null-pointer-checks -fexpensive-optimizations -fgcse
       -fgcse-lm -foptimize-sibling-calls -fpeephole2 -fregmove -fre‐
       order-blocks  -freorder-functions -frerun-cse-after-loop
       -fsched-interblock  -fsched-spec -fschedule-insns  -fsched‐
       ule-insns2 -fstrict-aliasing -fstrict-overflow -ftree-pre
       -ftree-vrp

Puoi modificare e usare questo comando per aiutarti a restringere le opzioni su cui indagare.

       ...
       Alternatively you can discover which binary optimizations are
       enabled by -O3 by using:

               gcc -c -Q -O3 --help=optimizers > /tmp/O3-opts
               gcc -c -Q -O2 --help=optimizers > /tmp/O2-opts
               diff /tmp/O2-opts /tmp/O3-opts Φ grep enabled

Una volta trovata l'ottimizzazione dei cattivi, non dovresti aver bisogno dei cout.

Answer 5

Se questo è possibile per te, potresti provare a dividere il codice in:

• la libreria che si desidera testare compilata con tutte le ottimizzazioni attivate
• un programma di test, che collega dinamicamente la libreria, con le ottimizzazioni disattivate

Altrimenti, potresti specificare un diverso livello di ottimizzazione (sembra che tu stia usando gcc ...) per la funzione di test con l'attributo optimize (vedi http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#Function-Attributes ) .

Answer 6

È possibile creare una funzione fittizia in un file cpp separato che non fa nulla, ma prende come argomento qualunque sia il tipo del risultato del calcolo. Quindi puoi chiamare quella funzione con i risultati del tuo calcolo, costringendo gcc a generare il codice intermedio, e l'unica penalità è il costo di invocare una funzione (che non dovrebbe distorcere i tuoi risultati a meno che tu non lo chiami un lotto ! ).

Answer 7

#include <iostream>

// Mark coords as extern.
// Compiler is now NOT allowed to optimise away coords
// This it can not remove the loop where you initialise it.
// This is because the code could be used by another compilation unit
extern double coords[500][3];
double coords[500][3];

int main()
{

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


std::cout << "hello world !"<< std::endl;
return 0;
}

Answer 8

modifica : la cosa più semplice che puoi fare è semplicemente usare i dati in modo spurio dopo che la funzione è stata eseguita e al di fuori dei tuoi benchmark. Come,

StartBenchmarking(); // ie, read a performance counter
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }
StopBenchmarking(); // what comes after this won't go into the timer

// this is just to force the compiler to use coords
double foo;
for (int j = 0 ; j < 500 ; ++j )
{
  foo += coords[j][0] + coords[j][1] + coords[j][2]; 
}
cout << foo;

---

Ciò che a volte funziona per me in questi casi è nascondere il test in vitro all'interno di una funzione e passare i set di dati di riferimento attraverso i puntatori volatili . Questo dice al compilatore che non deve comprimere le successive scritture su quei puntatori (perché potrebbero essere es. I / O mappati in memoria). Quindi,

void test1( volatile double *coords )
{
  //perform a simple initialization of all coordinates:
  for (int i=0; i<1500; i+=3)
  {
    coords[i+0] = 3.23;
    coords[i+1] = 1.345;
    coords[i+2] = 123.998;
  }
}

Per qualche motivo non ho ancora capito che non funziona sempre in MSVC, ma spesso lo fa - guarda l'output dell'assembly per essere sicuro. Ricorda inoltre che volatile ostacolerà alcune ottimizzazioni del compilatore (impedisce al compilatore di mantenere il contenuto del puntatore nel registro e impone che le scritture avvengano nell'ordine del programma), quindi questo è affidabile solo se lo stai usando per scrittura finale dei dati.

In generale, i test in vitro come questo sono molto utili se ricordi che non è l'intera storia. Di solito collaudo le mie nuove routine matematiche in modo isolato in modo da poter scorrere rapidamente solo le caratteristiche della cache e della pipeline del mio algoritmo su dati coerenti.

La differenza tra la profilatura della provetta in questo modo e l'esecuzione in " il mondo reale " significa che otterrai set di dati di input estremamente variabili (a volte nel migliore dei casi, a volte nel peggiore dei casi, a volte patologici), la cache si troverà in uno stato sconosciuto entrando nella funzione e potresti avere altri thread che sbattono sul bus; quindi, quando hai finito, dovresti eseguire alcuni benchmark su questa funzione in vivo .

Answer 9

Non so se GCC abbia una funzione simile, ma con VC ++ puoi usare:

#pragma optimize

per attivare / disattivare selettivamente le ottimizzazioni. Se GCC ha funzionalità simili, puoi creare con l'ottimizzazione completa e disattivarlo dove necessario per assicurarti che il tuo codice venga chiamato.

Answer 10

Solo un piccolo esempio di ottimizzazione indesiderata:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
double coords[500][3];

//perform a simple initialization of all coordinates:
for (int i=0; i<500; ++i)
 {
   coords[i][0] = 3.23;
   coords[i][1] = 1.345;
   coords[i][2] = 123.998;
 }


cout << "hello world !"<< endl;
return 0;
}

Se commentate il codice da " double coords [500] [3] " alla fine del ciclo for genererà esattamente lo stesso codice assembly (appena provato con g ++ 4.3.2). So che questo esempio è fin troppo semplice e non sono stato in grado di mostrare questo comportamento con uno std :: vector di un semplice & Quot; Coordinates & Quot; struttura.

Comunque penso che questo esempio mostri ancora che alcune ottimizzazioni possono introdurre errori nel benchmark e volevo evitare alcune sorprese di questo tipo quando si introduce un nuovo codice in una libreria. È facile immaginare che il nuovo contesto potrebbe impedire alcune ottimizzazioni e portare a una libreria molto inefficiente.

Lo stesso dovrebbe valere anche per le funzioni virtuali (ma non lo provo qui). Utilizzato in un contesto in cui un collegamento statico farebbe il lavoro, sono abbastanza fiducioso che i compilatori decenti dovrebbero eliminare la chiamata indiretta extra per la funzione virtuale. Posso provare questa chiamata in un ciclo e concludere che chiamare una funzione virtuale non è un grosso problema. Quindi lo chiamerò centinaia di migliaia di volte in un contesto in cui il compilatore non può indovinare quale sarà il tipo esatto del puntatore e avrà un aumento del 20% del tempo di esecuzione ...

Answer 11

all'avvio, letto da un file. nel tuo codice, indica se (input == " x ") cout < < result_of_benchmark;

Il compilatore non sarà in grado di eliminare il calcolo e se si assicura che l'input non sia " x " non si eseguirà il benchmark di iostream.