benchmarking, codice di riordino, volatile

Question

decido che voglio punto di riferimento una particolare funzione, così ho ingenuamente scrivere codice come questo:

#include <ctime> 
#include <iostream> 

int SlowCalculation(int input) { ... } 

int main() { 
    std::cout << "Benchmark running..." << std::endl; 
    std::clock_t start = std::clock(); 
    int answer = SlowCalculation(42); 
    std::clock_t stop = std::clock(); 
    double delta = (stop - start) * 1.0/CLOCKS_PER_SEC; 
    std::cout << "Benchmark took " << delta << " seconds, and the answer was " 
       << answer << '.' << std::endl; 
    return 0; 
} 

Un collega ha sottolineato che avrei dovuto dichiarare le variabili start e stop come volatile a evitare il riordino del codice. Egli ha suggerito che l'ottimizzatore potrebbe, per esempio, in modo efficace riordinare il codice come questo:

std::clock_t start = std::clock(); 
    std::clock_t stop = std::clock(); 
    int answer = SlowCalculation(42); 

All'inizio ero scettico che tale riordino estremo è stato permesso, ma dopo un po 'di ricerca e sperimentazione, ho imparato che era.

Ma volatile non si sentiva la soluzione giusta; non è volatile davvero solo per l'I/O mappato in memoria?

Tuttavia, ho aggiunto volatile e ho scoperto che non solo il benchmark impiegava molto più tempo, ma era anche selvaggiamente incoerente dall'inizio alla fine. Senza volatilità (e avendo la fortuna di garantire che il codice non fosse riordinato), il benchmark richiedeva costantemente 600-700 ms. Con la volatilità, spesso ci sono voluti 1200 ms e talvolta più di 5000 ms. Gli elenchi di disassemblaggio delle due versioni non mostravano praticamente alcuna differenza se non una diversa selezione di registri. Questo mi fa chiedere se c'è un altro modo per evitare il riordino del codice che non ha effetti collaterali così travolgenti.

La mia domanda è:

Qual è il modo migliore per prevenire il codice di riordino nel codice di benchmarking come questo?

La mia domanda è simile a this one (che era sull'utilizzo di volatili per evitare di elisione invece di riordino), this one (che non ha risposto come prevenire riordino), e this one (che dibattuto se il problema è stato codice di riordino o eliminazione del codice morto). Mentre tutti e tre sono su questo argomento esatto, nessuno in realtà risponde alla mia domanda.

Aggiornamento: La risposta sembra essere che il mio collega si è sbagliato e che il riordino in questo modo non è coerente con lo standard. Ho svalutato tutti quelli che l'hanno detto e ho assegnato la generosità a Maxim.

Ho visto un caso (basato sul codice in this question) in cui Visual Studio 2010 ha riordinato le chiamate di clock come illustrato (solo in versioni a 64 bit). Sto cercando di creare un caso minimale per illustrarlo in modo da poter segnalare un errore su Microsoft Connect.

Per chi ha detto che volatili dovrebbero essere molto più lento, perché costringe legge e scrive a memoria, questo non è del tutto coerente con il codice viene emesso. Nella mia risposta su this question, mostro lo smontaggio per il codice con e senza volatile. All'interno del ciclo, tutto è tenuto in registri. Le uniche differenze significative sembrano essere la selezione del registro. Non capisco x86 assemblaggio abbastanza bene per sapere il motivo per cui le prestazioni della versione non-volatile è costantemente veloce mentre la versione volatile è incoerente (e a volte drammaticamente) più lento.

Answer 1

Un collega ha sottolineato che avrei dovuto dichiarare l'inizio e fine variabili come volatili per evitare il codice riordino.

Scusate, ma il vostro collega ha torto.

Il compilatore non riordina le chiamate a funzioni le cui definizioni non sono disponibili in fase di compilazione. Immagina semplicemente l'ilarità che si avrebbe se il compilatore avesse riordinato le chiamate come fork e exec o spostato il codice attorno a queste.

In altre parole, qualsiasi funzione senza definizione è una barriera di memoria del tempo di compilazione, ovvero il compilatore non sposta le istruzioni successive prima della chiamata o delle istruzioni precedenti dopo la chiamata.

Nel vostro codice chiamate a std::clock terminare chiamando una funzione la cui definizione non è disponibile.

Non posso raccomandare abbastanza guardando atomic Weapons: The C++ Memory Model and Modern Hardware perché discute idee sbagliate sulle barriere di memoria (tempo di compilazione) e volatile tra molte altre cose utili.

Tuttavia, ho aggiunto volatile e ho scoperto che non solo il benchmark impiegava molto più tempo, ma era anche selvaggiamente incoerente dall'inizio alla fine. Senza volatilità (e avendo la fortuna di garantire che il codice non fosse riordinato), il benchmark richiedeva costantemente 600-700 ms. Con volatile, spesso ci sono voluti 1200 ms e qualche volta più di 5000 ms

Non sono sicuro che la causa sia la volatile.

Il tempo di esecuzione segnalato dipende da come viene eseguito il benchmark. Assicurati di disabilitare il ridimensionamento della frequenza della CPU in modo che non accenda la modalità turbo o cambi la frequenza nel mezzo della corsa. Inoltre, i micro-benchmark devono essere eseguiti come processi prioritari in tempo reale per evitare la pianificazione del rumore. Potrebbe accadere che durante un'altra esecuzione un indicizzatore di file in background inizi a competere con il benchmark per il tempo della CPU. Vedi this per maggiori dettagli.

Una buona pratica è misurare i tempi necessari per eseguire la funzione un numero di volte e riportare i numeri min/avg/mediano/max/stdev/totale. Una deviazione standard elevata potrebbe indicare che i preparativi di cui sopra non vengono eseguiti. La prima esecuzione è spesso la più lunga perché la cache della CPU potrebbe essere fredda e potrebbe richiedere molti errori di cache e errori di pagina e anche risolvere i simboli dinamici dalle librerie condivise durante la prima chiamata (la risoluzione dei simboli lazy è la modalità di collegamento predefinita in fase di esecuzione su Linux , ad esempio), mentre le chiamate successive verranno eseguite con un sovraccarico molto minore.

Answer 2

si potrebbe fare due file C, SlowCalculation compilati con g++ -O3 (alto livello di ottimizzazione), e il punto di riferimento quello compilato con g++ -O1 (livello inferiore, ancora ottimizzati - che potrebbero essere sufficienti per quella parte di benchmarking).

Secondo la pagina man, riordino di codice avviene durante -O2 e -O3 livelli ottimizzazioni.

Poiché l'ottimizzazione si verifica durante la compilazione, non il collegamento, il lato del benchmark non deve essere influenzato dal riordino del codice.

Supponendo che si utilizzi g++ - ma ci dovrebbe essere qualcosa di equivalente in un altro compilatore.

Answer 3

Il metodo usuale per evitare il riordino è una barriera compilata, ovvero asm volatile ("":::"memory"); (con gcc). Questa è un'istruzione asm che non fa nulla, ma diciamo al compilatore che cloberà la memoria, quindi non è permesso riordinare il codice attraverso di essa.Il costo di questo è solo il costo effettivo della rimozione del riordino, che ovviamente non è il caso di cambiare il livello di ottimizzazione ecc. Come suggerito altrove.

Credo che _ReadWriteBarrier è equivalente per roba di Microsoft.

Per Maxim, la risposta di Yegorushkin, tuttavia, è improbabile che il riordino sia la causa dei vostri problemi.

Answer 4

Riordino descritto dal collega rompe solo 1,9/13

sequenziato prima è una, transitivo, a coppie relazione asimmetrica tra le valutazioni eseguite da un singolo filo (1,10), che induce un ordine parziale tra quelle valutazioni. Date due valutazioni A e B, se A è sequenziato prima di B, allora l'esecuzione di A precede l'esecuzione di B. Se A non è sequenziato prima di B e B non è sequenziato prima di A, quindi A e B non sono sequenziati . [Nota: l'esecuzione delle valutazioni non eseguite può sovrapporsi. -end note] Le valutazioni A e B sono sequenzialmente indeterminate quando A viene sequenziato prima che B o B sia sequenziato prima di A, ma non è specificato quale. [Nota: non è possibile sovrapporre indeterminatamente le valutazioni sequenziali , ma è possibile eseguirle prima. -end note]

Quindi in pratica non si deve pensare al riordino mentre non si usano i thread.

Answer 5

Il modo corretto per eseguire questa operazione in C++ consiste nell'utilizzare una classe , ad es. qualcosa come

class Timer 
{ 
    std::clock_t startTime; 
    std::clock_t* targetTime; 

public: 
    Timer(std::clock_t* target) : targetTime(target) { startTime = std::clock(); } 
    ~Timer() { *target = std::clock() - startTime; } 
}; 

e usarlo in questo modo:

std::clock_t slowTime; 
{ 
    Timer timer(&slowTime); 
    int answer = SlowCalculation(42); 
} 

Intendiamoci, io in realtà non crede il compilatore potrà mai riordinare come questo.

Answer 6

Il volatile garantisce una cosa e una sola cosa: le letture di una variabile volatile verranno lette ogni volta dalla memoria - il compilatore non assumerà che il valore possa essere memorizzato nella cache di un registro. Allo stesso modo, le scritture verranno scritte nella memoria. Il compilatore non lo terrà in un registro "per un po ', prima di scriverlo in memoria".

Per evitare il riordino del compilatore, è possibile utilizzare le cosiddette recinzioni del compilatore. MSVC comprende 3 recinti del compilatore:

_ReadWriteBarrier() - completa recinzione

_ReadBarrier() - recinzione su due lati per carichi

_WriteBarrier() - recinzione su due lati per i negozi

ICC include __memory_barrier() recinto completo.

I recinti pieni di solito sono la scelta migliore perché non c'è bisogno di una granularità più fine a questo livello (le recinzioni del compilatore sono praticamente non costose in fase di esecuzione).

Riordino dei parametri (che la maggior parte del compilatore esegue quando l'ottimizzazione è abilitata), questo è anche il motivo principale per cui alcuni programmi non riescono a funzionare quando vengono compilati con l'ottimizzazione del compilatore.

suggerirà di leggere http://preshing.com/20120625/memory-ordering-at-compile-time per vedere i potenziali problemi che possiamo affrontare con il compilatore reoredering ecc

Answer 7

Ci sono un paio di modi che mi viene in mente. L'idea è di creare barriere del tempo di compilazione in modo che il compilatore non riordini una serie di istruzioni.

Un possibile modo per evitare il riordino sarebbe quello di imporre la dipendenza tra istruzioni che non possono essere risolte dal compilatore (ad esempio passando un puntatore alla funzione e usando quel puntatore nell'istruzione successiva). Non sono sicuro di come ciò possa influire sulle prestazioni del codice effettivo che ti interessa nel benchmarking.

Un'altra possibilità è quella di rendere la funzione SlowCalculation(42); una funzione extern (definire questa funzione in un file separato .c/cpp e collegare il file al vostro programma principale) e dichiarare start e stop come variabili globali. Non so quali sono le ottimizzazioni offerte dall'ottimizzatore link-time/inter-procedural del tuo compilatore.

Inoltre, se si compila in O1 o O0, molto probabilmente il compilatore non si preoccuperebbe di riordinare le istruzioni. La tua domanda è in qualche modo correlata a (Compile time barriers - compiler code reordering - gcc and pthreads)