È normale che i buildin atomici di gcc siano così lenti?

Question

Ho un'applicazione in cui devo incrementare alcuni contatori statistici in un metodo multi-thread. L'incremento deve essere sicuro per i thread, quindi ho deciso di utilizzare la funzione integrata gcc atomica __sync_add_and_fetch(). Solo per avere un'idea del loro impatto, ho fatto alcuni semplici test delle prestazioni e ho notato che queste funzioni sono molto più lente del semplice incremento pre/post.

Ecco il programma di test che ho creato:

#include <iostream> 
#include <pthread.h> 
#include <time.h> 

using namespace std; 

uint64_t diffTimes(struct timespec &start, struct timespec &end) 
{ 
    if(start.tv_sec == end.tv_sec) 
    { 
    return end.tv_nsec - start.tv_nsec; 
    } 
    else if(start.tv_sec < end.tv_sec) 
    { 
    uint64_t nsecs = (end.tv_sec - start.tv_sec) * 1000000000; 
    return nsecs + end.tv_nsec - start.tv_nsec; 
    } 
    else 
    { 
    // this is actually an error 
    return 0; 
    } 
} 

void outputResult(const char *msg, struct timespec &start, struct timespec &end, uint32_t numIterations, uint64_t val) 
{ 
    uint64_t diff = diffTimes(start, end); 
    cout << msg << ": " 
     << "\n\t iterations: " << numIterations 
     << ", result: " << val 
     << "\n\t times [start, end] = [" << start.tv_sec << ", " << start.tv_nsec << "]" 
     << "\n\t [" << end.tv_sec << ", " << end.tv_nsec << "]" 
     << "\n\t [total, avg] = [" << diff 
     << ", " << (diff/numIterations) << "] nano seconds" 
     << endl; 
} 

int main(int argc, char **argv) 
{ 
    struct timespec start, end; 
    uint64_t val = 0; 
    uint32_t numIterations = 1000000; 

    // 
    // NON ATOMIC pre increment 
    // 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    ++val; 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("Non-Atomic pre-increment", start, end, numIterations, val); 
    val = 0; 

    // 
    // NON ATOMIC post increment 
    // 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    val++; 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("Non-Atomic post-increment", start, end, numIterations, val); 
    val = 0; 

    // 
    // ATOMIC add and fetch 
    // 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    __sync_add_and_fetch(&val, 1); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("Atomic add and fetch", start, end, numIterations, val); 
    val = 0; 

    // 
    // ATOMIC fetch and add 
    // 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    __sync_fetch_and_add(&val, 1); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("Atomic fetch and add", start, end, numIterations, val); 
    val = 0; 

    // 
    // Mutex protected post-increment 
    // 
    pthread_mutex_t mutex; 
    pthread_mutex_init(&mutex, NULL); 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    pthread_mutex_lock(&mutex); 
    val++; 
    pthread_mutex_unlock(&mutex); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("Mutex post-increment", start, end, numIterations, val); 
    val = 0; 

    // 
    // RWlock protected post-increment 
    // 
    pthread_rwlock_t rwlock; 
    pthread_rwlock_init(&rwlock, NULL); 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint32_t i = 0; i < numIterations; ++i) 
    { 
    pthread_rwlock_wrlock(&rwlock); 
    val++; 
    pthread_rwlock_unlock(&rwlock); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 

    outputResult("RWlock post-increment", start, end, numIterations, val); 
    val = 0; 

    return 0; 
} 

Ed ecco i risultati:

# ./atomicVsNonAtomic 
Non-Atomic pre-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 1585375] 
     [0, 1586185] 
     [total, avg] = [810, 0] nano seconds 
Non-Atomic post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 1667489] 
     [0, 1667920] 
     [total, avg] = [431, 0] nano seconds 
Atomic add and fetch: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 1682037] 
     [0, 16595016] 
     [total, avg] = [14912979, 14] nano seconds 
Atomic fetch and add: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 16617178] 
     [0, 31499571] 
     [total, avg] = [14882393, 14] nano seconds 
Mutex post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 31526810] 
     [0, 68515763] 
     [total, avg] = [36988953, 36] nano seconds 
RWlock post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 68547649] 
     [0, 110877351] 
     [total, avg] = [42329702, 42] nano seconds 

Ecco la compilazione gcc:

g++ -o atomicVsNonAtomic.o -c -march=i686 -O2 -I. atomicVsNonAtomic.cc 
g++ -o atomicVsNonAtomic atomicVsNonAtomic.o -lrt -lpthread 

E informazioni correlate e Versioni:

# gcc --version 
gcc (GCC) 4.3.2 
Copyright (C) 2008 Free Software Foundation, Inc. 
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

# uname -a 
Linux gtcba2v1 2.6.32.12-0.7-default #1 SMP 2010-05-20 11:14:20 +0200 i686 i686 i386 GNU/Linux 

E ora per la domanda effettiva :) È normale che le operazioni atomiche siano molto più lente?

La differenza per un milione di iterazioni è:

• semplice post-incremento: 431 nano secondi
• atomiche prendere e aggiungere il funzionamento: 14882393 nano secondi

Naturalmente capisco che un l'operazione atomica dovrebbe essere più costosa, ma ciò sembra esagerato. Solo per completezza, ho anche controllato un mutex pthread e rwlock. Almeno le operazioni atomiche sono più veloci delle operazioni di pthread, ma mi sto ancora chiedendo se ho fatto qualcosa di sbagliato. Non riuscivo a collegarmi senza specificare l'opzione -march=i686, forse questo ha un impatto?

UPDATE:

ho tirato fuori l'ottimizzazione -O2 compilatore e stato in grado di ottenere risultati più coerenti come segue:

# ./atomicVsNonAtomic 
Non-Atomic pre-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 1647303] 
     [0, 4171164] 
     [total, avg] = [2523861, 2] nano seconds 
Non-Atomic post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 4310230] 
     [0, 7262704] 
     [total, avg] = [2952474, 2] nano seconds 
Atomic add and fetch: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 7285996] 
     [0, 25919067] 
     [total, avg] = [18633071, 18] nano seconds 
Atomic fetch and add: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 25941677] 
     [0, 44544234] 
     [total, avg] = [18602557, 18] nano seconds 
Mutex post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 44573933] 
     [0, 82318615] 
     [total, avg] = [37744682, 37] nano seconds 
RWlock post-increment: 
     iterations: 1000000, result: 1000000 
     times [start, end] = [0, 82344866] 
     [0, 125124498] 
     [total, avg] = [42779632, 42] nano seconds 

Answer 1

La risposta è che GCC ottimizza le incrementi non-atomiche lontano. Quando si vede un ciclo simile:

for (int i=0; i<N; i++) x++; 

si sostituisce con:

x += N; 

Questo può essere visto in assembly generato, che contiene:

call clock_gettime 
leal -32(%ebp), %edx 
addl $1000000, -40(%ebp)  <- increment by 1000000 
adcl $0, -36(%ebp) 
movl %edx, 4(%esp) 
movl $2, (%esp) 
call clock_gettime 

Quindi non sta misurando cosa pensi di essere.

È possibile rendere la variabile volatile per impedire questa ottimizzazione. Sul mio computer, dopo averlo fatto, l'accesso non atomico è circa 8 volte più veloce dell'accesso atomico. Quando si utilizza una variabile a 32 bit anziché 64 bit (sto compilando come 32 bit), la differenza scende a circa un fattore di 3.

Answer 2

Sto indovinando che gcc sta ottimizzando l'operazione di incremento non-atomica a qualcosa come

val += numIterations; 

Lei dice che 10^6 incrementi stanno prendendo 431 nanosecondi, che funziona a 0.000431 ns per loop di iterazione. Su un processore da 4 GHz, un ciclo di clock è di 0,25 ns, quindi è abbastanza ovvio che il ciclo venga ottimizzato. Questo spiega la grande differenza di prestazioni che stai vedendo.

Edit: è misurato un'operazione atomica come prendere 14 ns - assumendo ancora una volta un processore a 4 GHz, che funziona a 56 cicli, che è abbastanza decente!

Answer 3

La lentezza di ogni meccanismo di sincronizzazione non può essere misurata da un unico filo. Gli oggetti di sincronizzazione a processo singolo come i mutex POSIX/le sezioni critiche di Windows costano davvero molto tempo quando vengono contestati.

Si dovrebbe introdurre diversi threads- fare altro lavoro che rispecchia il tempo della tua vera applicazione- per i metodi sincronizzati per ottenere una vera e propria idea di quanto tempo ci vuole.