Pourquoi le multithread est-il plus lent?

J’essaie donc d’écrire un programme qui trouve des nombres premiers. Le véritable objective du projet est simplement d’apprendre sur le multithreading. D’abord, j’ai écrit un programme à un seul thread et il trouve jusqu’à 13 633 943 en 1 minute. Ma version multithread n’a que 10.025.627.

Voici mon code pour le programme mono-threadé

#include  using namespace std; bool isprime(long num) { long lim = num/2; if(num == 1) { return 0; } for(long i = 2; i <= lim; i++) { if (num % i == 0) { return 0; } else{ lim = num/i; } } return 1; } int main() { long lim; cout <> lim; for(long i = 1; i <= lim || lim == 0; i++) { if(isprime(i)) { cout << i << endl; } } } 

Voici mon code pour mon programme multithread.

 extern"C" { #include  #include  } #include  using namespace std; bool isprime(long num); void * iter1(void * arg); void * iter2(void * arg); void * iter3(void * arg); void * iter4(void * arg); int main() { //long lim; //cout <> lim; pthread_t t1; char mem1[4096];//To avoid false sharing. Needed anywhere else? pthread_t t2; char mem2[4096];//These helped but did not solve problem. pthread_t t3; pthread_create(&t1, NULL, iter1, NULL); pthread_create(&t2, NULL, iter2, NULL); pthread_create(&t3, NULL, iter3, NULL); iter4(0); } bool isprime(long num) { long lim = num/2; if(num == 1) { return 0; } for(long i = 2; i <= lim; i++) { if (num % i == 0) { return 0; } else{ lim = num/i; } } return 1; } void * iter1(void * arg) { for(long i = 1;; i = i + 4) { if(isprime(i)) { cout << i << endl; } } return 0; } void * iter2(void * arg) { for(long i = 2;; i = i + 4) { if(isprime(i)) { cout << i << endl; } } return 0; } void * iter3(void * arg) { for(long i = 3;; i = i + 4) { if(isprime(i)) { cout << i << endl; } } return 0; } void * iter4(void * arg) { for(long i = 4;; i = i + 4) { if(isprime(i)) { cout << i << endl; } } return 0; } 

Ce qui me perturbe particulièrement, c’est que le moniteur système signale une utilisation de l’UC de 25% pour le thread simple et de 100% pour le multithread. Cela ne devrait-il pas signifier qu’il effectue 4 fois plus de calculs?

Je suis à peu cout sûr que cout agit comme une ressource partagée – et même si elle imprime réellement chaque numéro correctement et dans le bon ordre, cela ralentit TRÈS beaucoup le processus.

J’ai fait quelque chose de similaire (il est plus flexible et utilise une opération atomique pour “choisir le prochain nombre”), et c’est presque exactement 4x plus vite sur ma machine quad core. Mais ce n’est que si je n’imprime rien. Si vous imprimez sur la console, le processus est beaucoup plus lent, car il est très souvent utilisé pour mélanger les pixels plutôt que pour calculer.

Commenter le cout << i << endl; ligne, et cela ira beaucoup plus vite.

Edit: en utilisant mon programme de test, avec impression:

 Single thread: 15.04s. Four threads: 11.25s 

Sans impression:

 Single threads: 12.63s. Four threads: 3.69s. 

3,69 * 4 = 14,76s, mais la commande time de ma machine Linux indique une exécution totale de 12,792s. Il est donc évident qu’il rest un peu de temps quand tous les threads ne fonctionnent pas - ou des erreurs de comptabilité ...

Je pense que votre problème actuel réside en grande partie dans le fait que vous prenez la partie qui peut vraiment fonctionner en multi-thread (recherche des nombres premiers) et que vous l’enfouissez dans le bruit (le temps d’écrire la sortie sur la console).

Pour avoir une idée de l’effet que cela a, j’écris un peu votre écriture principale pour séparer l’impression des nombres premiers de la recherche des nombres premiers. Pour faciliter le chronométrage, je l’ai également demandé de prendre la limite de la ligne de commande au lieu d’interactivement, donnant ceci:

 int main(int argc, char **argv) { if (argc != 2) { std::cerr << "Usage: bad_prime \n"; return 1; } std::vector primes; unsigned long lim = atol(argv[1]); clock_t start = clock(); for(unsigned long i = 1; i <= lim; i++) if(isprime(i)) primes.push_back(i); clock_t stop = clock(); for (auto a : primes) std::cout << a << "\t"; std::err << "\nTime to find primes: " << double(stop-start)/CLOCKS_PER_SEC << "\n"; } 

En sautant les milliers de lignes des nombres premiers eux-mêmes, j'obtiens un résultat comme celui-ci:

 Time to find primes: 0.588 Real 48.206 User 1.68481 Sys 3.40082 

Donc, environ une demi-seconde pour trouver les nombres premiers et plus de 47 secondes pour les imprimer. En supposant que l’intention est vraiment d’écrire la sortie sur la console, nous pourrions aussi bien nous arrêter ici. Même si le multithreading pouvait éliminer complètement le temps nécessaire à la recherche des nombres premiers, nous ne modifierions néanmoins que le temps ultime de ~ 48,2 secondes à ~ 47,6 secondes - il est peu probable que cela en vaille la peine.

Pour le moment, je suppose donc que l'intention réelle est d'écrire la sortie dans un fichier. Puisqu'il semble assez inutile de créer du code multi-thread, mais d'exécuter un code horriblement inefficace dans chaque thread, j'ai pensé optimiser le code mono-thread (ou au moins le dés-pessimiser). point.

Tout d'abord, j'ai supprimé le endl et l'ai remplacé par "\n" . Avec la sortie dirigée vers un fichier, le temps d'exécution a été ramené de 0,968 seconde à 0,678 seconde. Endl vide le tampon en plus d'écrire une nouvelle ligne, et ce vidage de la mémoire tampon représente environ un tiers du temps pris par le programme.

Sur la même base, j'ai pris la liberté de réécrire votre isprime en quelque chose de moins inefficace:

 bool isprime(unsigned long num) { if (num == 2) return true; if(num == 1 || num % 2 == 0) return false; unsigned long lim = sqrt(num); for(unsigned long i = 3; i <= lim; i+=2) if (num % i == 0) return false; return true; } 

Ceci est certainement ouvert à plus d'amélioration (par exemple, tamis d'Eratosthenes), mais c'est simple, direct, et environ deux à trois fois plus rapide (les temps ci-dessus sont basés sur l'utilisation de cet isprime , pas le vôtre).

À ce stade, le multithreading du résultat principal a au moins une chance de sens: avec le résultat principal prenant environ 0,5 seconde sur 0,6 seconde, même si nous ne pouvons que doubler la vitesse, nous devrions voir une différence significative dans le temps total .

La séparation de la sortie du résultat principal nous donne également une base bien meilleure pour écrire une version multithread du code. Avec chaque thread écrivant ses résultats dans un vecteur séparé, nous pouvons obtenir une sortie significative (sans entrelacement) sans avoir à verrouiller cout et ainsi de suite. Nous calculons chaque bloc séparément, puis imprimons chaque vecteur dans l'ordre.

Le code pour cela pourrait ressembler à quelque chose comme ça:

 #include  #include  #include  #include  #include  using namespace std; bool isprime(unsigned long num) { // same as above } typedef unsigned long UL; struct params { unsigned long lower_lim; unsigned long upper_lim; std::vector results; params(UL l, UL u) : lower_lim(l), upper_lim(u) {} }; long thread_func(params *p) { for (unsigned long i=p->lower_lim; iupper_lim; i++) if (isprime(i)) p->results.push_back(i); return 0; } int main(int argc, char **argv) { if (argc != 2) { std::cerr << "Usage: bad_prime \n"; return 1; } unsigned long lim = atol(argv[1]); params p[] = { params(1, lim/4), params(lim/4, lim/2), params(lim/2, 3*lim/4), params(3*lim/4, lim) }; std::thread threads[] = { std::thread(thread_func, p), std::thread(thread_func, p+1), std::thread(thread_func, p+2), std::thread(thread_func, p+3) }; for (int i=0; i<4; i++) { threads[i].join(); for (UL p : p[i].results) std::cout << p << "\n"; } } 

En exécutant ceci sur la même machine qu'avant (un processeur dual-core assez ancien), je reçois:

 Real 0.35 User 0.639604 Sys 0 

Cela semble extrêmement bien évoluer . Si tout ce que nous gagnons est un calcul multi-cœur, nous nous attendons à voir le temps de trouver la division des nombres premiers par 2 (je l’utilise sur un processeur dual-core) et le temps d’écriture des données sur le disque rest constant. (le multithreading ne va pas accélérer mon disque dur). Sur cette base, une mise à l'échelle parfaite devrait nous donner 0,59 / 2 + 0,1 = 0,40 seconde.

L’amélioration (certes) mineure que nous constatons au-delà de cela tient probablement au fait que nous pouvons commencer à écrire les données du thread 1 sur le disque pendant que les threads 2, 3 et 4 trouvent toujours des nombres premiers (et les données du thread 2 alors que 3 et 4 sont encore en cours d’informatique, et l’écriture des données du thread 3 alors que le thread 4 est toujours en cours d’informatique).

Je suppose que je devrais append que l'amélioration que nous constatons est suffisamment petite pour qu'il puisse également s'agir d'un simple bruit dans le timing. Cependant, j’ai exécuté à la fois les versions à un et à plusieurs threads, et bien qu’il y ait une certaine variation dans les deux, la version à plusieurs threads est toujours plus rapide que la simple amélioration de la vitesse de calcul.

J'avais presque oublié: pour avoir une idée de la différence de vitesse totale, j'ai fait un test pour voir le temps qu'il faudrait pour trouver les nombres premiers allant jusqu'à 13 633 943, ce que votre version d'origine a trouvée en une minute. Même si j'utilise sans doute un processeur plus lent (un Athlon 64 X2 âgé de 7 ans environ), cette version du code le fait en 12,7 secondes.

Une dernière remarque: au moins pour le moment, j'ai omis le remplissage que vous aviez inséré pour empêcher les faux partages. Basé sur les temps que je reçois, ils ne semblent pas être nécessaires (ou utiles).

Cela dépend plutôt du nombre de processeurs que votre code doit exécuter sur le système d’exploitation. Chacun de ces threads est lié au CPU, donc si vous en avez un, il exécutera un thread un instant, coupez-le plusieurs fois, exécutez le thread suivant, etc., ce qui ne sera pas plus rapide et pourrait être plus lent, en fonction de les frais généraux d’un échange de fil. Et sur Solaris, au moins, cela vaut la peine de dire que vous voulez que tous les fils soient exécutés en même temps.

Je n’ai pas rencontré d’implémentation dont la sortie est sérialisée, comme le suggère l’autre affiche. Normalement, vous obtenez une sortie comme

 235 iisi s ppprririimmme ee 

Votre sortie peut donc indiquer que le système d’exploitation ne vous alloue pas plusieurs threads.

Un autre problème que vous pouvez rencontrer est que la sortie sur une console est incroyablement lente comparée à la sortie sur un fichier. Il peut être intéressant d’envoyer la sortie de votre programme dans un fichier et de voir à quelle vitesse cela se passe ainsi.

Je crois qu’Oli Charlesworth a eu raison du problème de l’hyperthreading. Je pensais que l’hyperthreading était comme avoir deux cœurs. Ce n’est pas. Je l’ai changé pour n’utiliser que deux threads et je suis passé à 22 227 421, ce qui est presque deux fois plus rapide.

Bien que @MatsPetersson soit correct (au moins pour un système basé sur POSIX, stdout est une ressource partagée), il ne fournit pas un moyen de résoudre ce problème, alors voici comment vous pouvez éliminer ces verrous embêtants.

POSIX C définit une fonction, putc_unlocked , qui fera exactement la même chose que putc , mais sans locking (surprise). En utilisant cela, nous pouvons alors définir notre propre fonction qui imprimera un entier sans locking et sera plus rapide que cout ou printf dans des scénarios multithread:

 void printint_unlocked(FILE *fptr, int i) { static int digits[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; if (i < 0) { putc_unlocked('-', fptr); i = -i; } int ndigits = (int) log10(i); while (ndigits >= 0) { int digit = (i / (digits[ndigits])) % 10; putc_unlocked('0' + digit, fptr); --ndigits; } } 

Notez qu’il est tout à fait possible qu’il y ait des conditions de concurrence avec cette méthode, entraînant une collision de nombres dans votre sortie. Si votre algorithme n’aboutit pas à des collisions, vous devriez tout de même bénéficier de l’amélioration des performances du code multithread.

La troisième et dernière option (et probablement trop complexe pour votre cas d’utilisation) consiste à créer une queue d’événements sur un autre thread et à effectuer toutes les impressions à partir de ce thread, ce qui ne génère aucune condition de concurrence ni aucun problème de locking entre les threads.