L'applicazione con thread C++ viene eseguita più lentamente rispetto a quella senza threading

Question

Attualmente sto scrivendo un generatore di numeri primi in C++. Ho creato prima una versione a thread singolo e successivamente una versione a più thread.

Ho scoperto che se il mio programma genera valori inferiori a 100'000, la versione a thread singolo è più veloce di quella multi-thread. Ovviamente sto facendo qualcosa di sbagliato.

mio codice qui sotto:

#include <iostream> 
#include <fstream> 
#include <set> 
#include <string> 
#include <thread> 
#include <mutex> 
#include <shared_mutex> 

using namespace std; 

set<unsigned long long> primeContainer; 
shared_mutex m; 

void checkPrime(const unsigned long long p) 
{ 
    if (p % 3 == 0) 
     return; 

    bool isPrime = true; 
    for (set<unsigned long long>::const_iterator it = primeContainer.cbegin(); it != primeContainer.cend(); ++it) 
    { 
     if (p % *it == 0) 
     { 
      isPrime = false; 
      break; 
     } 
     if (*it * *it > p) // check only up to square root 
      break; 
    } 

    if (isPrime) 
     primeContainer.insert(p); 
} 

void checkPrimeLock(const unsigned long long p) 
{ 
    if (p % 3 == 0) 
     return; 

    bool isPrime = true; 
    try 
    { 
     shared_lock<shared_mutex> l(m); 
     for (set<unsigned long long>::const_iterator it = primeContainer.cbegin(); it != primeContainer.cend(); ++it) 
     { 
      if (p % *it == 0) 
      { 
       isPrime = false; 
       break; 
      } 
      if (*it * *it > p) 
       break; 
     } 
    } 
    catch (exception& e) 
    { 
     cout << e.what() << endl; 
     system("pause"); 
    } 

    if (isPrime) 
    { 
     try 
     { 
      unique_lock<shared_mutex> l(m); 
      primeContainer.insert(p); 
     } 
     catch (exception& e) 
     { 
      cout << e.what() << endl; 
      system("pause"); 
     } 
    } 
} 

void runLoopThread(const unsigned long long& l) 
{ 
    for (unsigned long long i = 10; i < l; i += 10) 
    { 
     thread t1(checkPrimeLock, i + 1); 
     thread t2(checkPrimeLock, i + 3); 
     thread t3(checkPrimeLock, i + 7); 
     thread t4(checkPrimeLock, i + 9); 
     t1.join(); 
     t2.join(); 
     t3.join(); 
     t4.join(); 
    } 
} 

void runLoop(const unsigned long long& l) 
{ 
    for (unsigned long long i = 10; i < l; i += 10) 
    { 
     checkPrime(i + 1); 
     checkPrime(i + 3); 
     checkPrime(i + 7); 
     checkPrime(i + 9); 
    } 
} 

void printPrimes(const unsigned long long& l) 
{ 
    if (1U <= l) 
     cout << "1 "; 
    if (2U <= l) 
     cout << "2 "; 
    if (3U <= l) 
     cout << "3 "; 
    if (5U <= l) 
     cout << "5 "; 

    for (auto it = primeContainer.cbegin(); it != primeContainer.cend(); ++it) 
    { 
     if (*it <= l) 
      cout << *it << " "; 
    } 
    cout << endl; 
} 

void writeToFile(const unsigned long long& l) 
{ 
    string name = "primes_" + to_string(l) + ".txt"; 
    ofstream f(name); 

    if (f.is_open()) 
    { 
     if (1U <= l) 
      f << "1 "; 
     if (2U <= l) 
      f << "2 "; 
     if (3U <= l) 
      f << "3 "; 
     if (5U <= l) 
      f << "5 "; 

     for (auto it = primeContainer.cbegin(); it != primeContainer.cend(); ++it) 
     { 
      if (*it <= l) 
       f << *it << " "; 
     } 
    } 
    else 
    { 
     cout << "Error opening file." << endl; 
     system("pause"); 
    } 
} 

int main() 
{ 
    unsigned int n = thread::hardware_concurrency(); 
    std::cout << n << " concurrent threads are supported." << endl; 

    unsigned long long limit; 
    cout << "Please enter the limit of prime generation: "; 
    cin >> limit; 

    primeContainer.insert(7); 

    if (10 < limit) 
    { 
     //runLoop(limit); //single-threaded 
     runLoopThread(limit); //multi-threaded 
    } 

    printPrimes(limit); 
    //writeToFile(limit); 
    system("pause"); 
    return 0; 
} 

Nella funzione main troverete commenti su quale funzione è filettato singolo e multi.

La differenza principale tra questi è l'uso di blocchi, condivisi per l'iterazione del contenitore e univoci per l'inserimento. Se è importante, la mia CPU ha 4 core.

Perché la versione a thread singolo è più veloce?

Answer 1

Per me sembra che si stia iniziando una nuova discussione per ogni singolo numero di controllo principale. Questo non è un buon IMHO, perché l'avvio/spegnimento del thread più la sincronizzazione si aggiunge al calcolo di ciascun primo. L'avvio di una discussione può essere piuttosto lento.

Si consiglia di avviare questi 4 thread all'esterno del ciclo for principale ed elaborare 1/4 dell'intervallo in ciascun thread. Ma questo potrebbe richiedere un po 'di sincronizzazione aggiuntiva, perché per verificare un numero primo, il codice sopra apparentemente ha bisogno di avere prima i primi fino a sqrt N disponibili.

Dal mio punto di vista, potrebbe essere più facile da usare il Sieve of Erastothenes algoritmo, che potrebbe essere molto più facile da parallelizzare senza alcun blocco (però potrebbe ancora subire il problema noto come "false sharing").

EDIT

Qui ho subito creato una versione con il crivello di Eratostene:

void processSieve(const unsigned long long& l, 
    const unsigned long long& start, 
    const unsigned long long& end, 
    const unsigned long long& step, 
    vector<char> &is_prime) 
{ 
    for (unsigned long long i = start; i <= end; i += step) 
     if (is_prime[i]) 
      for (unsigned long long j = i + i; j <= l; j += i) 
       is_prime[j] = 0; 
} 

void runSieve(const unsigned long long& l) 
{ 
    vector<char> is_prime(l + 1, 1); 
    unsigned long long end = sqrt(l); 
    processSieve(l, 2, end, 1, is_prime); 
    primeContainer.clear(); 
    for (unsigned long long i = 1; i <= l; ++i) 
     if (is_prime[i]) 
      primeContainer.insert(i); 
} 

void runSieveThreads(const unsigned long long& l) 
{ 
    vector<char> is_prime(l + 1, 1); 
    unsigned long long end = sqrt(l); 
    vector<thread> threads; 
    threads.reserve(cpuCount); 
    for (unsigned long long i = 0; i < cpuCount; ++i) 
     threads.emplace_back(processSieve, l, 2 + i, end, cpuCount, ref(is_prime)); 
    for (unsigned long long i = 0; i < cpuCount; ++i) 
     threads[i].join(); 
    primeContainer.clear(); 
    for (unsigned long long i = 1; i <= l; ++i) 
     if (is_prime[i]) 
      primeContainer.insert(i); 
} 

I risultati della misurazione, i numeri primi fino a 1 000 000 (MSVC 2013, Release):

runLoop: 204.02 ms 
runLoopThread: 43947.4 ms 
runSieve: 30.003 ms 
runSieveThreads (8 cores): 24.0024 ms 

Fino a 10 0000 000:

runLoop: 4387.44 ms 
// runLoopThread disabled, taking too long 
runSieve: 350.035 ms 
runSieveThreads (8 cores): 285.029 ms 

I tempi comprendono l'elaborazione finale del vettore e il trasferimento dei risultati sul set principale.

Come si può vedere, la versione di Sieve è molto più veloce della tua versione anche in versione a thread singolo (per la tua versione mutex ho dovuto cambiare il lock in lock mutex regolari perché MSVC 2013 non ha shared_lock, quindi i risultati sono probabilmente molto peggio dei tuoi).

Ma si può vedere che la versione multithread del setaccio non è ancora veloce come previsto (8 core, cioè 8 thread, l'accelerazione lineare sarebbe 8 volte più veloce del singolo thread), anche se non c'è il blocco (trading off che alcuni numeri potrebbero essere eseguiti inutilmente se non sono stati contrassegnati come "nessun prim" dagli altri thread ancora, ma in generale i risultati dovrebbero essere stabili, perché solo impostare su 0 ogni volta, non importa se impostato simultaneamente da più thread). La causa per cui l'accelerazione non è lineare è molto probabilmente a causa del problema "false sharing" come accennato prima - i thread che scrivono gli zeri invalidano l'un l'altro le linee della cache.

Answer 2

Hai diversi problemi.

In primo luogo, continuate a creare e distruggere le discussioni inutilmente. Fare in modo che ogni ciclo di thread funzioni finché non c'è più lavoro da fare.

In secondo luogo, le serrature sono modo troppo fine e, di conseguenza, si stanno acquisendo li modo troppo spesso. Ciascun thread preleva un blocco di 100 numeri da testare anziché uno alla volta e fa in modo che inseriscano i primi trovati da ciascun blocco in un colpo solo.

Answer 3

Dal momento che la sezione di commento stava diventando un po 'affollato e OP espresso interesse per una soluzione lockless, sto fornendo un esempio di tale approccio di seguito (in semi-pseudocodice):

vector<uint64_t> primes_thread1; 
vector<uint64_t> primes_thread2; 
... 

// check all numbers in [start, end) 
void check_primes(uint64_t start, uint64_t end, vector<uint64_t> & out) { 
    for (auto i = start; i < end; ++i) { 
     if (is_prime(i)) { // simply loop through all odds from 3 to sqrt(i) 
      out.push_back(i); 
     } 
    } 
} 

auto f1 = async(check_primes, 1, 1000'000, ref(primes_thread1)); 
auto f2 = async(check_primes, 1000'000, 2000'000, ref(primes_thread2)); 
... 

f1.wait(); 
f2.wait(); 
... 

primes_thread1.insert(
    primes_thread1.begin(), 
    primes_thread2.cbegin(), primes_thread2.cend() 
); 
primes_thread1.insert(
    primes_thread1.begin(), 
    primes_thread3.cbegin(), primes_thread3.cend() 
); 
... 
// primes_thread1 contains all primes found in all threads 

Ovviamente questo può essere refactored graziosamente parametrizzando il numero di thread e la dimensione di ogni intervallo. Mi stavo rendendo verosimile (si spera) più chiaramente illustrando il concetto di evitare il blocco non condividendo alcuno stato in primo luogo.

Answer 4

Potrebbe esserci un altro problema nel test principale. Non stai mai testando contro 7 come divisore.

Inoltre, il test presuppone che primeContainer contenga già tutti i numeri primi compresi tra 10 e la radice sqare del numero testato. Potrebbe non essere il caso se usi i thread per riempire il contenitore.

Se si riempie il contenitore con numeri sempre crescenti (e l'algoritmo conta su quello), è possibile utilizzare std :: vector invece di std :: set per prestazioni migliori.