Perché questo codice C++ 11 contenente rand() è più lento con più thread che con uno?

Question

Sto provando in giro sui nuovi thread di C++ 11, ma il mio semplice test ha prestazioni multicore abissali. Come semplice esempio, questo programma somma alcuni numeri casuali quadrati.

#include <iostream> 
#include <thread> 
#include <vector> 
#include <cstdlib> 
#include <chrono> 
#include <cmath> 

double add_single(int N) { 
    double sum=0; 
    for (int i = 0; i < N; ++i){ 
     sum+= sqrt(1.0*rand()/RAND_MAX); 
    } 
    return sum/N; 
} 

void add_multi(int N, double& result) { 
    double sum=0; 
    for (int i = 0; i < N; ++i){ 
     sum+= sqrt(1.0*rand()/RAND_MAX); 
    } 
    result = sum/N; 
} 

int main() { 
    srand (time(NULL)); 
    int N = 1000000; 

    // single-threaded 
    auto t1 = std::chrono::high_resolution_clock::now(); 
    double result1 = add_single(N); 
    auto t2 = std::chrono::high_resolution_clock::now(); 
    auto time_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count(); 
    std::cout << "time single: " << time_elapsed << std::endl; 

    // multi-threaded 
    std::vector<std::thread> th; 
    int nr_threads = 3; 
    double partual_results[] = {0,0,0}; 
    t1 = std::chrono::high_resolution_clock::now(); 
    for (int i = 0; i < nr_threads; ++i) 
     th.push_back(std::thread(add_multi, N/nr_threads, std::ref(partual_results[i]))); 
    for(auto &a : th) 
     a.join(); 
    double result_multicore = 0; 
    for(double result:partual_results) 
     result_multicore += result; 
    result_multicore /= nr_threads; 
    t2 = std::chrono::high_resolution_clock::now(); 
    time_elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count(); 
    std::cout << "time multi: " << time_elapsed << std::endl; 

    return 0; 
} 

compilato con 'g ++ -std = C++ 11 -pthread test.cpp' su Linux e una macchina 3core, un risultato tipico è

time single: 33 
time multi: 565 

Così multi esecuzione filettata è più un ordine di grandezza più lento. Ho usato numeri casuali e un sqrt per rendere l'esempio meno banale e incline alle ottimizzazioni del compilatore, quindi sono fuori dalle idee.

modifica:

1. Questo problema scale per ingrandire la N, quindi il problema non è il breve tempo di esecuzione
2. Il tempo per creare i fili non è il problema. Escludendolo non cambia significativamente il risultato

Wow ho trovato il problema. Era davvero rand(). L'ho sostituito con un equivalente in C++ 11 e ora il runtime si adatta perfettamente. Grazie a tutti!

Answer 1

Il tempo necessario per eseguire il programma è molto piccolo (33 msec). Ciò significa che l'overhead per creare e gestire diversi thread potrebbe essere più che il vero vantaggio. Prova a utilizzare programmi che richiedono tempi più lunghi per l'esecuzione (ad es. 10 secondi).

Answer 2

Per rendere più veloce, utilizzare un modello di pool di thread.

Ciò consentirà di accodare le attività in altri thread senza l'overhead di creare un std::thread ogni volta che si desidera utilizzare più di un thread.

Non contare l'overhead di impostare la coda nelle metriche di rendimento, solo il tempo di accodare ed estrarre i risultati.

Creare un set di thread e una coda di attività (una struttura contenente un std::function<void()>) per alimentarli. I thread attendono la coda per le nuove attività da svolgere, le eseguono, quindi attendono nuove attività.

Le attività sono responsabili della comunicazione del loro "done-ness" al contesto di chiamata, ad esempio tramite std::future<>. Il codice che consente le funzioni di accodamento nella coda di attività potrebbe fare questo involucro per te, vale a dire questa firma:

template<typename R=void> 
std::future<R> enqueue(std::function<R()> f) { 
    std::packaged_task<R()> task(f); 
    std::future<R> retval = task.get_future(); 
    this->add_to_queue(std::move(task)); // if we had move semantics, could be easier 
    return retval; 
} 

che trasforma una nuda std::function ritorno R in un nullaria packaged_task, poi aggiunge che alla coda di compiti. Si noti che la coda delle attività deve essere sensibile al movimento, poiché packaged_task è solo di spostamento.

Nota 1: Non sono così familiare con std::future, quindi quanto sopra potrebbe essere in errore.

Nota 2: Se le attività inserite nella coda sopra descritta sono dipendenti l'una dall'altra per risultati intermedi, la coda potrebbe deadlock, poiché non viene descritta alcuna disposizione per "recuperare" i thread bloccati ed eseguire il nuovo codice. Tuttavia, le attività non bloccanti di "calcolo nudo" dovrebbero funzionare correttamente con il modello precedente.

Answer 3

Sul mio sistema il comportamento è lo stesso, ma come indicato da Maxim, rand non è thread-safe. Quando cambio rand su rand_r, il codice multi-thread è più veloce come previsto.

void add_multi(int N, double& result) { 
double sum=0; 
unsigned int seed = time(NULL); 
for (int i = 0; i < N; ++i){ 
    sum+= sqrt(1.0*rand_r(&seed)/RAND_MAX); 
} 
result = sum/N; 
} 

Answer 4

Come hai scoperto, rand è il colpevole qui.

Per coloro che sono curiosi, è possibile che questo comportamento provenga dall'implementazione di rand utilizzando un mutex per la sicurezza dei thread.

Ad esempio, eglibc definisce rand in termini di __random, che is defined as:

long int 
__random() 
{ 
    int32_t retval; 

    __libc_lock_lock (lock); 

    (void) __random_r (&unsafe_state, &retval); 

    __libc_lock_unlock (lock); 

    return retval; 
} 

Questo tipo di bloccaggio costringerebbe più thread per eseguire in serie, con conseguente prestazioni inferiori.