Czy to normalne, że wbudowane w gcc wbudowane elementy są tak wolne?

Question

Mam aplikację, w której muszę zwiększyć liczbę liczników statystyk w metodzie wielowątkowej. Inkrementacja musi być bezpieczna dla wątków, więc zdecydowałem się użyć funkcji wbudowanej gcc atomowej __sync_add_and_fetch(). Aby dowiedzieć się o ich wpływie, zrobiłem kilka prostych testów wydajności i zauważyłem, że te funkcje są znacznie wolniejsze niż zwykły przyrost pre/post.

Oto program testowy, który stworzyłem:

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

A oto wyniki:

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

Oto gcc kompilacji:

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

i pokrewnych informacji i wersje:

# 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 

A teraz pytanie brzmi: czy to normalne, że operacje atomowe są o wiele wolniejsze?

Różnica na milion iteracji:

• prosty postinkrementacja: 431 nano sekund
• atomowe pobierania i dodać operacji: 14882393 nano sekund

Z oczywiście rozumieć, że Operacja atomowa powinna być droższa, ale wydaje się to przesadne. Dla kompletności sprawdziłem również mutex pthread i rwlock. Przynajmniej operacje atomowe są szybsze niż operacje pthread, ale wciąż zastanawiam się, czy zrobiłem coś złego. Nie mogłem go połączyć bez określenia opcji -march=i686, może to ma wpływ?

UPDATE:

Wyjąłem optymalizacji -O2 kompilatora i był w stanie uzyskać bardziej spójne wyniki w następujący sposób:

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

Odpowiedź brzmi, że GCC optymalizuje przyrosty non-atomowych z dala. Kiedy widzi pętlę jak:

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

zastępuje go:

x += N; 

To może być postrzegane w wygenerowanym zespołu, który zawiera:

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 

Więc nie mierzysz co myślisz, że jesteś.

Możesz ustawić zmienną volatile, aby zapobiec tej optymalizacji. Na moim komputerze, dostęp nieatomowy jest około 8 razy szybszy niż dostęp atomowy. Gdy używasz 32-bitowej zmiennej zamiast 64-bitowej (kompiluję jako 32-bitową), różnica spada do około 3.

Answer 2

Zgaduję, że gcc jest zoptymalizowanie non-atomową operację przyrost coś jak

val += numIterations; 

Mówisz, że przyrosty 10^6 biorą 431 nanosekund, co przekłada się na 0.000431 ns na pętli iteracji. W procesorze 4 GHz cykl zegara wynosi 0,25 ns, więc oczywiste jest, że pętla jest optymalizowana z dala. To wyjaśnia dużą różnicę w wydajności, którą widzisz.

Edytuj: Zmierzyłeś operację atomową jako przyjmującą 14 ns - zakładając ponownie procesor 4 GHz, który działa na 56 cykli, co jest całkiem przyzwoite!

Answer 3

Powolność dowolnego mechanizmu synchronizacji nie może być mierzona przez pojedynczy wątek. Obiekty z pojedynczym procesem synchronizacji, takie jak POSEX mutexes/sekcje krytyczne Windows, naprawdę kosztują tylko czas, kiedy są kwestionowane.

Będziesz musiał wprowadzić kilka wątków - wykonując inne prace, które odzwierciedlają czas rzeczywistej aplikacji - aby zsynchronizowane metody pozwoliły zorientować się, ile czasu potrzeba.