Multi-threaded random_r es más lento que la versión de una sola rosca

Question

El siguiente programa es esencialmente el mismo que el descrito here. Cuando funciono y compilar el programa utilizando dos hilos (NTHREADS == 2), consigo los siguientes tiempos de funcionamiento:

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

Cuando es ejecutado con un solo hilo (NTHREADS == 1) veces, consigo corro significativamente mejor a pesar de que solo usa un núcleo.

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

Mi sistema es de doble núcleo, y sé random_r es seguro para subprocesos y estoy bastante seguro de que es no bloqueante. Cuando se ejecuta el mismo programa sin random_r y se utiliza un cálculo de cosenos y senos como reemplazo, la versión de doble subproceso se ejecuta en aproximadamente la mitad del tiempo como se esperaba.

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

estoy confundido por eso que cuando la generación de números aleatorios los dos ejecución roscada realiza mucho peor que la versión de un solo subproceso, teniendo en cuenta random_r está destinado a ser utilizado en aplicaciones de subprocesos múltiples.

Answer 1

Un cambio muy sencillo de espacio de los datos fuera de la memoria:

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

resultados en un tiempo mucho más rápido que se ejecuta en mi máquina de doble núcleo.

Esto confirmaría la sospecha que se suponía que debía probar: que está mutando valores en la misma línea de caché en dos subprocesos separados, y también tiene conflicto de caché. Vale la pena ver el 'machine architecture - what your programming language never told you' talk de Herb Sutter si todavía tienes tiempo, si no sabes nada de eso, demuestra que se comparte de forma falsa a partir de la 1:20.

Resuelva el tamaño de la línea de caché y cree los datos de cada subproceso para que estén alineados.

Es un poco más limpio de vino peleón todos los datos del hilo en una estructura, y alinee que:

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

con 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 

O puede utilizar el doble del tamaño de línea de caché, y use malloc: el relleno extra asegura que la memoria mutada se encuentre en líneas separadas, ya que malloc tiene 16 (IIRC) en lugar de 64 bytes alineados.

(reduje ITERACIONES por un factor de diez en lugar de tener una máquina estúpida rápido)

Answer 2

No sé si esto es relevante o no - pero acabo de ver un comportamiento muy similar (orden de magnitud más lento con 2 hilos que con uno) ... yo, básicamente cambiado a:

srand(seed); 
    foo = rand(); 

a un

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

y que "fija" que (2 hilos es ahora de forma fiable casi dos veces más rápido - por ejemplo 1 9s en lugar de 35s).

No sé lo que podría haber sido el problema - ¿Coherencia o coherencia del caché en las partes internas de rand() tal vez? De todos modos, también hay un random_r(), así que tal vez te sirva (hace un año) u otra persona.