Многопоточный random_r медленнее однопоточной версии - PullRequest
Новая
       7

Многопоточный random_r медленнее однопоточной версии

10 голосов
/ 08 июня 2010

Следующая программа по сути такая же, как описанная здесь .Когда я запускаю и компилирую программу, используя два потока (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 предназначен для использования в многопоточных приложениях.

Ответы [ 2 ]

13 голосов
/ 08 июня 2010

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

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]);
}

значительно ускоряет работу моего двухъядерного компьютера.

Это подтвердит подозрение, которое он должен был проверить - что вы изменяете значения в одной и той же строке кэша в двух отдельных потоках и, следовательно, имеете конфликт в кэше. 'Машинная архитектура Херба Саттера - то, что ваш язык программирования никогда не говорил вам' говорите , стоит посмотреть, если у вас есть время, если вы еще не знаете об этом, он демонстрирует ложное совместное использование, начиная примерно с 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 байта.

(я уменьшил ITERATIONS в десять раз вместо того, чтобы иметь тупо быструю машину)

1 голос
/ 15 апреля 2012

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

  srand(seed);
  foo = rand();

до 

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

и это "исправило" это (2 потока теперь надежно почти в два раза быстрее - например, 19 с вместо 35 с).

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

...