Ist es normal, dass die gcc-Atombauten so langsam sind?

Question

Ich habe eine Anwendung, in der ich einige Statistikzähler in einer Multithread-Methode inkrementieren muss. Das Inkrementieren muss Thread-sicher sein, so entschied ich mich, die gcc atomic builtins __sync_add_and_fetch() Funktion zu verwenden. Um eine Vorstellung von deren Auswirkungen zu bekommen, habe ich ein paar einfache Leistungstests durchgeführt und festgestellt, dass diese Funktionen viel langsamer sind als einfache Pre-/Post-Inkrementierungen.

Hier haben wir das Testprogramm, das ich erstellt:

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

Und hier sind die Ergebnisse:

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

Hier ist der gcc Compilation ist:

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

und damit verbundene Informationen und Versionen:

# 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 

Und jetzt für die eigentliche Frage :) Ist es normal, dass die atomaren Operationen so viel langsamer sind?

Der Unterschied für eine Million Iterationen ist:

• einfache Nachinkrement: 431 Nanosekunden
• Atom holen und den Betrieb hinzuzufügen: 14882393 Nanosekunden

Natürlich verstehe ich, dass ein Atomoperation sollte teurer sein, aber das scheint übertrieben. Nur der Vollständigkeit halber habe ich auch einen Pthread-Mutex und -Rwlock überprüft. Zumindest sind die atomaren Operationen schneller als die Pthread-Operationen, aber ich frage mich immer noch, ob ich etwas falsch gemacht habe. Ich konnte es nicht verbinden, ohne die Option -march=i686 zu spezifizieren, vielleicht hat das eine Auswirkung?

UPDATE:

ich die -O2 Compiler-Optimierung nahm und konnte kohärentere Ergebnisse erhalten wie folgt:

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

Die Antwort ist, dass GCC Ihre Nicht-Atom Schritten optimiert Weg. Wenn es eine Schleife wie sieht:

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

es ersetzt sie durch:

x += N; 

Diese in der erzeugten Baugruppe zu sehen ist, die enthält:

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 

So sind Sie nicht messen was du denkst du bist.

Sie können Ihre Variable volatile machen, um diese Optimierung zu verhindern. Auf meinem Computer ist der nicht-atomare Zugriff ungefähr achtmal so schnell wie der atomare Zugriff. Bei Verwendung einer 32-Bit-Variablen anstelle von 64-Bit (ich kompiliere als 32-Bit), fällt die Differenz auf etwa einen Faktor von 3.

Answer 2

Ich vermute, dass gcc Ihre Nicht-Atom Inkrementbetrieb um so etwas wie

Optimierung

val += numIterations; 

Sie sagen, dass 10^6 Schritten 431 ns einnehmen, die pro Schleifeniterationslatenzzeit auf 0,000431 ns ausarbeitet. Bei einem 4-GHz-Prozessor beträgt der Taktzyklus 0,25 ns, also ist es ziemlich offensichtlich, dass die Schleife weg optimiert wird. Dies erklärt den großen Leistungsunterschied, den Sie sehen.

Edit: Sie haben eine atomare Operation als 14 ns gemessen - unter der Annahme eines 4 GHz-Prozessors wieder, das funktioniert bis 56 Zyklen, die ziemlich anständig ist!

Answer 3

Die Langsamkeit eines Synchronisationsmechanismus kann nicht mit einem einzigen Thread gemessen werden. Single-Prozess-Sync-Objekte wie POSIX-Mutexe/Windows-kritische Abschnitte kosten nur dann wirklich Zeit, wenn sie umkämpft sind.

Sie müssten mehrere Threads einführen - andere Arbeiten, die die Zeit Ihrer realen Anwendung widerspiegeln - für die synchronisierten Methoden, um eine realistische Vorstellung davon zu bekommen, wie lange es dauert.