¿Es normal que los builtins atómicos gcc sean tan lentos?

Question

Tengo una aplicación en la que tengo que incrementar algunos contadores de estadísticas en un método de subprocesos múltiples. El incremento tiene que ser seguro para subprocesos, así que decidí usar la función __sync_add_and_fetch() de gcc atomic builtins. Solo para tener una idea de su impacto, realicé algunas pruebas simples de rendimiento y noté que estas funciones son mucho más lentas que el simple incremento pre/post.

Aquí es el programa de prueba que he creado:

#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; 
} 

Y aquí están los resultados:

# ./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 

Aquí es la compilación gcc:

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

y la información relacionada y versiones:

# 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 

Y ahora para la pregunta real :) ¿Es normal que las operaciones atómicas sean mucho más lentas?

La diferencia de un millón de iteraciones es:

• sencilla después de la subasta: 431 nano segundos
• atómicas traer y añadir operación: 14882393 nano segundos

Por supuesto que entiendo que una la operación atómica debería ser más costosa, pero esto parece exagerado. Solo para completar, también verifiqué un pthread mutex y rwlock. Al menos las operaciones atómicas son más rápidas que las operaciones pthread, pero aún me pregunto si he hecho algo mal. No pude conseguir que se vincule sin especificar la opción -march=i686, ¿quizás esto tiene un impacto?

ACTUALIZACIÓN:

Saqué la optimización -O2 compilador y la oportunidad de obtener resultados más coherentes de la siguiente manera:

# ./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 respuesta es que GCC optimiza sus incrementos no atómicas lejos. Cuando se ve un bucle como:

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

se reemplaza con:

x += N; 

Esto se puede ver en el conjunto generado, el cual 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 

Por lo que no se está midiendo lo que piensas que eres

Puede hacer que su variable volatile evite esta optimización. En mi computadora, después de hacer esto, el acceso no atómico es aproximadamente 8 veces más rápido que el acceso atómico. Cuando utilizo una variable de 32 bits en lugar de 64 bits (estoy compilando como de 32 bits), la diferencia se reduce a un factor de 3.

Answer 2

que supongo que gcc es la optimización de su operación de incremento no atómica a algo así como

val += numIterations; 

Usted dice que 10^6 incrementos están tomando 431 nanosegundos, lo que equivale a 0.000431 ns por iteración del bucle. En un procesador de 4 GHz, un ciclo de reloj es de 0,25 ns, por lo que es bastante obvio que el bucle se está optimizando. Esto explica la gran diferencia de rendimiento que estás viendo.

Editar: Usted midió una operación atómica como tomar 14 ns - asumiendo un procesador de 4 GHz nuevamente, eso da un total de 56 ciclos, ¡lo cual es bastante decente!

Answer 3

La lentitud de cualquier mecanismo de sincronización no puede medirse con un solo hilo. Los objetos de sincronización de proceso único, como los mutexes POSIX/secciones críticas de Windows, solo realmente cuestan tiempo cuando se impugnan.

Tendría que introducir varios hilos, haciendo otro trabajo que refleje el tiempo de su aplicación real, para los métodos sincronizados para obtener una idea real de cuánto tiempo lleva.