Performances et limite des threads

Version imprimable

Bonjour à tous,

Continuant mon apprentissage en développement, je souhaite savoir si il existe une "limite" de performances concernant les threads, ou, de manière plus générale, comment fonctionnent ces derniers ?
Je comprends le principe : paralléliser des processus (si tant est qu'ils soient parallélisables), mais finalement, comment ces threads sont traités par l' OS ? Car j'ai cru comprendre que c'est ce dernier qui gère les priorités des tâches concurrentes...

Dans le cas d'une fonction du style std::transform, y gagne t'on à paralléliser les opérations lorsque la fonction est "importante".
Par exemple, est-il intéressant de remplacer le code suivant :
Code:

1 2 3 4 5 6 7 8 9 template<typename IT, typename OP> void operate(IT first, IT last, IT outp, OP op) { while(first != last) { *outp = op(*first); ++first; ++outp; } }
par
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 template<typename IT, typename OP> void operate(IT first, IT last, IT outp, OP op) { std::vector<std::thread> thd; while(first != last) { thd.push_back(std::tread{op, outp, first}); } for(auto & v:thd) { v.join(); } }
(En espérant que la syntaxe soit correcte)

En bref : comment se justifie l'utilisation des threads et quelles sont les limites de la parallélisation ?

Merci !

11/03/2020, 12h03
koala01

Salut,

De manière générale, le gros problème d'un thread, c'est que cela demande énormément de temps à créer, et qu'il faut parfois s'assurer de les synchroniser.

Dans le code que tu présente, il y a, en outre, le problème de la capacité de ton vecteur lors du push_back à prendre en compte: n'oublie pas que, si la capacité de ton vecteur est insuffisante pour accepter l'élément supplémentaire, il y aura réallocation de la mémoire, et déplacement des données contenues dans le vector. Cela nécessitera également "beaucoup de temps".

(au fait, sauf erreur de ma part, tu as oublié d'incrémenter ton itérateur après la création de ton thread :P :$ )

Il n'est donc "pas si rare que cela" que l'on se rende compte que la préparation et à l'exécution des différents threads demande plus de temps que l'exécution purement séquentielle de la même opération :P

En gros, tout va dépendre, en priorité, de la complexité de OP et, dans une moindre mesure, de la manière dont tu vas traiter et manipuler thd.

Il est impossible de dresser une règle générale sur le sujet. Le meilleur conseil que l'on puisse te donner étant de ... faire un benchmark comparant l'exécution séquentielle et l'exécution parallélisée.

Dans certains cas, si OP représente un ensemble d'opérations qui prendront du temps, il se peut que la parallélisation permette de gagner du temps. Mais, si OP représente des opérations simples ne demandant que peu de temps d'exécution, il se peut tout aussi bien que tu observe une réelle chute des performances en tentant de paralléliser l'exécution :P
12/03/2020, 04h36
BioKore

Bonjour, et merci pour ce retour.

Citation:

(au fait, sauf erreur de ma part, tu as oublié d'incrémenter ton itérateur après la création de ton thread :$ )

Pas d'erreur... de ta part en tout cas. j'ai bien oublié le ++first et ++outp ^^

Ta réponse me plait dans le sens où c'est à peu près ce que j'imaginais. Si Op est long / complexe, on gagne potentiellement du temps.
Là où a me plait moins c'est la raison pour laquelle c'est comme ça... bâtir un thread est long !

du coup, dans le cas d'une opération simple mais sur une grande quantité d'éléments, on a tout intérêt à splitter le vecteur (des entrées) en X ou Y sous-vecteurs traités chacun par un thread différent... Le benchmark me semble "compliqué" à faire dans mon cas :/

Bref, je ferais quelques tests demain voir comment ça marche. Je pourrais peut être en tirer quelque chose tout de même.

Merci pour le retour en tout cas, ce dernier réponds clairement à ma question.
12/03/2020, 15h36
Bousk

Si tu penses avoir besoin de threads à un moment, tu peux très bien en démarer au début du programme.
Puis quand nécessaires, tu y pousses des opérations à paraléliser.

Ah ? cette méthode semble intéressante ; comment ça se met en place ?

Sinon, je me suis lancé dans un "cas" spécifique pour faire un benchmark concernant un certin nombre de fonctions que je serais susceptible d'utiliser dans un projet (parallélisables bien entendu). Cependant, je reste perplexe ; mon compilateur semble ne pas aimer mon code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 template<typename IT, typename OP> void operate(IT first, IT last, IT outp, OP op) { //std::cout << "called : " << *first << " to " << *last << '\n'; while(first != last) { op(*outp, *first); ++outp; ++first; } } template<typename IT, typename OP> void operate_t(IT first, IT last, IT outp, OP op, size_t const count) { auto sz{last-first}; auto modul{sz % count}; IT next_first{first}; IT next_last{last}; IT next_out{outp}; std::vector<std::thread> thd; thd.reserve(sz); while(next_first != last - modul) { next_last = std::next(next_first, count); thd.push_back(std::thread(operate<IT, OP>, next_first, next_last, next_out, op)); //operate(next_first, next_last, next_out, op); next_first = std::next(next_first, count); next_out = std::next(next_out, count); } operate(next_first, last, next_out, op); for(auto & t:thd) { t.join(); } }
A savoir, j'ai déjà modifié la manière dont j'incrémente mes itérateurs, mais visiblement, cela ne suffit pas. Dieu seul comprends pleinement ce que me recrache le compilateur, mais il me semble que cela vienne toujours des itérateurs... Ce que je pense : les fameux it = std::next(it, count) modifient les valeurs passées à mes threads. En gros, je modifie les itérateurs pendant que mes threads s'exécutent...
Quels sont les moyens de bypasser cette problématique ? J'ai bien pensé à faire une matrice d'itérateurs, mais ça me semble overkill pour ce genre de fonction. Est-il possible de s'assurer que les itérateurs transmis à mes threads ne sont que des copies ?
Et dans le cas où je devrais m'orienter vers une autre idée, quelles sont les points sur lesquels je devrais porter mon attention ?

Pour rappel, comme vous l'avez certainement déjà compris, mon but est de paralléliser des fonctions venant s'appliquer sur des vecteurs potentiellement longs, comme par exemple, retourner la racine carré de l'ensemble des valeurs d'un vecteur de +- 40'000 floats.

Pour info, si je retire le code des threads et traite la fonction comme une simple boucle, les résultats semblent corrects, et, bien entendu, je n'ai pas d'erreur de compilation.

Merci d'avance.

PS: pour les curieux, voici le message que me recrache geany (compilé sous debian)

Citation:

g++ -Wall --std=c++14 -o "test" "test.cpp"
/tmp/cc5G3qEN.o*: Dans la fonction «*std::thread::thread<void (&)(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&)), __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, float const& (*&)(float&, float const&)>(void (&)(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&)), __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >&, float const& (*&)(float&, float const&))*»*:
test.cpp:(.text._ZNSt6threadC2IRFvN9__gnu_cxx17__normal_iteratorIPfSt6vectorIfSaIfEEEES7_S7_PFRKfRfS9_EEJRS7_SF_SF_RSC_EEEOT_DpOT0_[_ZNSt6threadC5IRFvN9__gnu_cxx17__normal_iteratorIPfSt6vectorIfSaIfEEEES7_S7_PFRKfRfS9_EEJRS7_SF_SF_RSC_EEEOT_DpOT0_]+0x4b)*: référence indéfinie vers «*pthread_create*»
collect2: error: ld returned 1 exit status
Compilation échouée.

Je ne comprends pas trop le coup de la référence indéfinie là, mais bien entendu, j'ai bien un #include <thread>.

12/03/2020, 17h08
foetus

Citation:

Envoyé par koala01

De manière générale, le gros problème d'un thread, c'est que cela demande énormément de temps à créer, et qu'il faut parfois s'assurer de les synchroniser.

C'est pour cela qui a des bassins de threads ("thread pool" en anglais) :mrgreen:
On crée tous les threads au début et ensuite chacun va prendre en charge un traitement.
Le plus dur est de calibrer son bassin :wow: : pas trop de threads pour éviter de perdre des ressources et d'avoir un lancement long, pas assez pour ne pas avoir trop d'attente.

Citation:

Envoyé par BioKore

Ta réponse me plait dans le sens où c'est à peu près ce que j'imaginais. Si Op est long / complexe, on gagne potentiellement du temps.

Il y a aussi l'équilibrage des threads :whistle:

Par exemple, tu prends un jeu vidéo : tu as l'affichage, le son, l'IA, les entrées. Tu te dis : je vais créer 1 thread pour chacun ... mais cela ne fonctionne pas :aie::aie:
Le thread d'affichage va être surchargé à 80-90%, celui de l'IA 30 à 60% et celui du son à à peine 5%.
Il faut faire en sorte que tous tes threads aient la même quantité de charge : c'est pour cela que les développeurs sont passés au système ECS "Entity Component System" (<- lien wiki en anglais)

Citation:

Envoyé par BioKore

du coup, dans le cas d'une opération simple mais sur une grande quantité d'éléments, on a tout intérêt à splitter le vecteur (des entrées) en X ou Y sous-vecteurs traités chacun par un thread différent...

Il y a des structures de donnés sans verrous : on prend par le devant et on ajoute par derrière. :google: :wow:
12/03/2020, 19h37
BioKore
Citation:

les développeurs sont passés au système ECS "Entity Component System"

Encore ce fameux ECS...
J'ai bien, grâce aux experts de ce forum, déjà bâti un embryon d'ECS, et aussi je pense avoir compris l'intérêt principal de ce genre de paradigme tout comme la "facilité" qu'il en ressort pour paralléliser certaines tâches / fonctions / composants du programme ainsi créé.

Cependant, dans le cas qui m'intéresse ici, mes calculs sont simples. Autant présenter la chose sous un exemple plus concret : le calcul matriciel (ou du moins à représentation matricielle).
L'idée ici est de représenter un flux de valeurs sous forme matricielle afin d'en faciliter la manipulation et l'interprétation. Petit plus, on peut alors profiter des différentes opérations de transformation linéaires (produit matriciel, produit matrice / vecteur, etc...). Cependant, il n'est pas rare, pour certaines applications, de se retrouver avec des matrices de m x n (où m et n > 1'000 voire plus) et de devoir effectuer un dot product avec des vecteurs ou d'autres matrices (de dimensions similaires donc).
L'idée est alors de pouvoir paralléliser les différentes opérations matricielles éligibles à un tel fonctionnement.

Alors que le système d'ECS permet, selon les cas, de paralléliser tout un pan du programme, ainsi que d'apporter un certain nombre d'avantages qui sortent un peu du cadre de ce sujet, je ne cherche ici qu'à optimiser considérablement une opération "unitaire" qui, prise individuellement peut étouffer le fonctionnement général de l'application (ou du thread dans lequel cette opération est réalisée).

globalement, optimiser un code du genre :
Code:

1 2 3 4 5 matrix<float> Ma; matrix<float> Mb; matrix<float> res; //... res = dot_product(Ma, Mb);
Simple fonction que l'on peut retrouver dans n'importe quel code à destination graphique ou scientifique...

Précision qui tombe sous le sens, il s'agit ici de faire réaliser les opérations par le CPU ; je n'ai actuellement ni le temps ni l'envie de me plonger dans du CUDA ou toute autre joyeuseté fournie par le GPU Computing.

Citation:

Il y a des structures de donnés sans verrous : on prend par le devant et on ajoute par derrière.

Ca me rappelle justement un peu ce que j'avais fait pour mon ECS. J'avais dû ruser affin d'éviter d'invalider mes itérateurs en cas de suppression d'un composant en cours de lecture...
Cependant je pense que tu parles de conteneurs plus génériques comme queue ou dequeue j'imagine non ? Si tel est le cas, je vais me renseigner sur le sujet, mais comme ça là, je n'arrive pas à voir comment ça répondrait à la problématique posée...

Simple intuition : il me semble que je m'emporte encore dans un pétrin.... Visiblement, le C++ c'est comme repeindre un mur pourri ; une activité toute simple peut se transformer en un chantier considérable :mouarf:

Merci pour ce retour !
12/03/2020, 20h52
jo_link_noir
Le plus simple serait peut-être de partir sur les algorithmes parallèles de la STL (https://en.cppreference.com/w/cpp/al...n_policy_tag_t avec std::transform ou std::reduce_transform).

> Est-il possible de s'assurer que les itérateurs transmis à mes threads ne sont que des copies ?

C'est le cas, std::thread fait déjà des copies des, il faut utiliser std::ref/reference_wrapper si on veut des références.

Personnellement, je trouve plus simple et plus clair d'utiliser une lambda:
Code:

1 2 3 thd.emplace_back([=/*on ne veut que des copies*/] { operate/*plus besoin de <IT, OP>*/(next_first, next_last, next_out, op); });
Pour l'erreur de link, il manque la dépendance à pthread (-lpthread sur la ligne de commande).
12/03/2020, 21h28
Invité

Citation:

Envoyé par BioKore

L'idée ici est de représenter un flux de valeurs sous forme matricielle afin d'en faciliter la manipulation et l'interprétation. Petit plus, on peut alors profiter des différentes opérations de transformation linéaires (produit matriciel, produit matrice / vecteur, etc...). Cependant, il n'est pas rare, pour certaines applications, de se retrouver avec des matrices de m x n (où m et n > 1'000 voire plus) et de devoir effectuer un dot product avec des vecteurs ou d'autres matrices (de dimensions similaires donc).
L'idée est alors de pouvoir paralléliser les différentes opérations matricielles éligibles à un tel fonctionnement.

Salut,
Pourquoi tu n'utilises pas juste une lib matricielle optimisée (eigen, armadillo, mkl, openblas...) ? Il me semble que ça gère le multi-thread et aussi le SSE/AVX. Et si tu veux vraiment répartir à la main une boucle sur plusieurs threads, il y a openmp.
12/03/2020, 21h42
BioKore

@jo_link_noir: merci pour ce retour. Effectivement, il manquait -lpthread. Cependant, il semble que l'erreur vienne d'ailleurs ; j'ai essayé ta méthode (avec le lambda), et voici le retour :

Citation:

g++ -Wall --std=c++14 -lpthread -o "test" "test.cpp"
/tmp/ccajlMof.o*: Dans la fonction «*std::thread::thread<operate_t<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&)>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&), unsigned long)::{lambda()#1}>(operate_t<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&)>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const& (*)(float&, float const&), unsigned long)::{lambda()#1}&&)*»*:
test.cpp:(.text._ZNSt6threadC2IZ9operate_tIN9__gnu_cxx17__normal_iteratorIPfSt6vectorIfSaIfEEEEPFRKfRfSA_EEvT_SE_SE_T0_mEUlvE_JEEEOSE_DpOT0_[_ZNSt6threadC5IZ9operate_tIN9__gnu_cxx17__normal_iteratorIPfSt6vectorIfSaIfEEEEPFRKfRfSA_EEvT_SE_SE_T0_mEUlvE_JEEEOSE_DpOT0_]+0x2f)*: référence indéfinie vers «*pthread_create*»
collect2: error: ld returned 1 exit status
Compilation échouée.

Je précise, le "projet" ne se compose que d'un seul *.cpp et un seul *.hpp. L'ensemble des fonction est défini dans le *.hpp

@SimonDecoline: dans mon cas, je n'ai besoin que d'une seule, voire deux opérations simples (genre dot product). Il me parait, pour le moment, et pour ce simple exemple, un peu exagéré de m'appuyer sur une bibliothèque scientifique complète pour ça. Puis ça m'apprends à programmer :)
Néanmoins, je vais tout de même jeter un oeil à ces lib que tu proposes ; peut-être que certaines conviennent tout à fait..

EDIT : en fait il faut mettre -lpthread à la fin ! La positon de ce paramètre importe pour g++
Verdict, la solution fonctionne très bien et il s'avère que j'en arrive à des performances meilleures dès les premiers essais (je ne m'y attendais pas du tout).
12/03/2020, 21h51
jo_link_noir

les bibliothèques se mettent après les sources.
12/03/2020, 21h58
foetus

Citation:

Envoyé par BioKore

Il me parait, pour le moment, et pour ce simple exemple, un peu exagéré de m'appuyer sur une bibliothèque scientifique complète pour ça.

Le truc c'est que c'est un problème mathématiques :whistle:

Et donc pour paralléliser des calculs mathématiques :mrgreen:, il faut être fort en maths pour refaire les calculs en développant/ factorisant (exemple: transformation de Fourier rapide) ... voire utiliser des développements limités, interpolations ou des suites par exemple.
Donc rien à voir avec de la programmation :zoubi: ... et que les bibliothèques scientifiques font.

On n'est pas un cas :wow: comme une image et la compression par ondelettes (<- lien wiki) où on divise par 4 les images successivement.
12/03/2020, 22h24
BioKore

Merci pour toutes ces infos fort utiles.... J'ai enfin eu une première approche sur le threading (il me reste encore les mutex et tout le tintouin mais c'est un début).