Многопоточность random_r медленнее, чем однопоточная версия

Question

Следующая программа по существу такая же, как описанная here. Когда я бегу и компилировать программу с помощью двух потоков (NTHREADS == 2), я получаю следующий раз запустите:

real  0m14.120s 
user  0m25.570s 
sys   0m0.050s 

Когда он запускается только один поток (NTHREADS == 1), я задавят раз значительно лучше, хотя он использует только одно ядро.

real  0m4.705s 
user  0m4.660s 
sys   0m0.010s 

Моя система двухъядерный, и я знаю, что random_r является поточно, и я уверен, что это не является блокирующим. Когда одна и та же программа запускается без random_r, и вычисление косинусов и синусов используется в качестве замены, двухпоточная версия работает примерно в 1/2 раза, как ожидалось.

#include <pthread.h> 
#include <stdlib.h> 
#include <stdio.h> 

#define NTHREADS 2 
#define PRNG_BUFSZ 8 
#define ITERATIONS 1000000000 

void* thread_run(void* arg) { 
    int r1, i, totalIterations = ITERATIONS/NTHREADS; 
    for (i = 0; i < totalIterations; i++){ 
     random_r((struct random_data*)arg, &r1); 
    } 
    printf("%i\n", r1); 
} 

int main(int argc, char** argv) { 
    struct random_data* rand_states = (struct random_data*)calloc(NTHREADS, sizeof(struct random_data)); 
    char* rand_statebufs = (char*)calloc(NTHREADS, PRNG_BUFSZ); 
    pthread_t* thread_ids; 
    int t = 0; 
    thread_ids = (pthread_t*)calloc(NTHREADS, sizeof(pthread_t)); 
    /* create threads */ 
    for (t = 0; t < NTHREADS; t++) { 
     initstate_r(random(), &rand_statebufs[t], PRNG_BUFSZ, &rand_states[t]); 
     pthread_create(&thread_ids[t], NULL, &thread_run, &rand_states[t]); 
    } 
    for (t = 0; t < NTHREADS; t++) { 
     pthread_join(thread_ids[t], NULL); 
    } 
    free(thread_ids); 
    free(rand_states); 
    free(rand_statebufs); 
} 

Я смущен, почему при генерации случайных чисел два резьбовых версия работает намного хуже, чем однотридовая версия, с учетом random_r предназначен для использования в многопоточных приложениях.

Answer 1

Очень простое изменение пространства данных из памяти:

struct random_data* rand_states = (struct random_data*)calloc(NTHREADS * 64, sizeof(struct random_data)); 
char* rand_statebufs = (char*)calloc(NTHREADS*64, PRNG_BUFSZ); 
pthread_t* thread_ids; 
int t = 0; 
thread_ids = (pthread_t*)calloc(NTHREADS, sizeof(pthread_t)); 
/* create threads */ 
for (t = 0; t < NTHREADS; t++) { 
    initstate_r(random(), &rand_statebufs[t*64], PRNG_BUFSZ, &rand_states[t*64]); 
    pthread_create(&thread_ids[t], NULL, &thread_run, &rand_states[t*64]); 
} 

приводит к гораздо быстрее, времени работы на моей двухъядерной машине.

Это подтвердит подозрение, которое оно предназначалось для тестирования, - что вы мутируете значения в одной строке кэша в двух отдельных потоках, и поэтому у вас есть проблема с кешем. Herb Sutter's 'machine architecture - what your programming language never told you' talk стоит посмотреть, есть ли у вас время, если вы еще не знаете об этом, он демонстрирует ложное разделение, начиная примерно с 1:20.

Разработайте свой размер строки кеша и создайте данные каждого потока, чтобы он был привязан к нему.

Это немного чище, чтобы Плонк все данные в нити в структуры, и выравнивать, что:

#define CACHE_LINE_SIZE 64 

struct thread_data { 
    struct random_data random_data; 
    char statebuf[PRNG_BUFSZ]; 
    char padding[CACHE_LINE_SIZE - sizeof (struct random_data)-PRNG_BUFSZ]; 
}; 

int main (int argc, char** argv) 
{ 
    printf ("%zd\n", sizeof (struct thread_data)); 

    void* apointer; 

    if (posix_memalign (&apointer, sizeof (struct thread_data), NTHREADS * sizeof (struct thread_data))) 
     exit (1); 

    struct thread_data* thread_states = apointer; 

    memset (apointer, 0, NTHREADS * sizeof (struct thread_data)); 

    pthread_t* thread_ids; 

    int t = 0; 

    thread_ids = (pthread_t*) calloc (NTHREADS, sizeof (pthread_t)); 

    /* create threads */ 
    for (t = 0; t < NTHREADS; t++) { 
     initstate_r (random(), thread_states[t].statebuf, PRNG_BUFSZ, &thread_states[t].random_data); 
     pthread_create (&thread_ids[t], NULL, &thread_run, &thread_states[t].random_data); 
    } 

    for (t = 0; t < NTHREADS; t++) { 
     pthread_join (thread_ids[t], NULL); 
    } 

    free (thread_ids); 
    free (thread_states); 
} 

с CACHE_LINE_SIZE 64:

refugio:$ gcc -O3 -o bin/nixuz_random_r src/nixuz_random_r.c -lpthread 
refugio:$ time bin/nixuz_random_r 
64 
63499495 
944240966 

real 0m1.278s 
user 0m2.540s 
sys 0m0.000s 

Или вы можете использовать двойной размер строки кэша, и используйте malloc - дополнительное заполнение гарантирует, что мутированная память находится на отдельных строках, так как malloc равен 16 (IIRC), а не 64 байта.

(я уменьшил Итерации по десять раз, а не имеющий тупо быстрая машина)

Answer 2

Я не знаю, если это уместно, или нет - но я только что видел очень сходное поведение (порядок медленнее с 2-мя нитями, чем с одним) ... Я в принципе изменилась:

srand(seed); 
    foo = rand(); 

к

myseed = seed; 
    foo = rand_r(&myseed); 

и что «фиксированный» его (2 потоков теперь надежно почти в два раза быстрее - например, 1 9s вместо 35s).

Я не знаю, в чем проблема: блокировка или кеширование на внутренних элементах rand() возможно? В любом случае, есть также random_r(), так что, возможно, это будет полезно для вас (год назад) или кого-то еще.