Salut, habrozhiteli! Le langage C ++ est choisi lorsque vous devez créer des applications vraiment rapides comme l'éclair. Et un traitement compétitif de haute qualité les rendra encore plus rapides. Les nouvelles fonctionnalités de C ++ 17 vous permettent d'utiliser toute la puissance de la programmation multithread pour résoudre facilement les problèmes de traitement graphique, d'apprentissage automatique, etc. Anthony Williams, un expert en traitement compétitif, examine des exemples et décrit des tâches pratiques, et partage des secrets qui seront utiles à tous dans y compris les développeurs les plus expérimentés.
Dans le livre • Un aperçu complet des fonctionnalités de C ++ 17. • Lancement et contrôle de flux. • Synchronisation des opérations concurrentielles. • Développement d'un code compétitif. • Débogage d'applications multithread. Le livre convient aux développeurs de niveau intermédiaire utilisant C et C ++. Une expérience en programmation compétitive n'est pas requise.
Développement de code compétitif
8.1. Façons de répartir le travail entre les threads
Imaginez que vous ayez besoin de construire une maison. Pour ce faire, vous devrez creuser une fosse de fondation, remplir la fondation elle-même, ériger des murs, poser des tuyaux et du câblage électrique, etc. Théoriquement, avec des compétences suffisantes, tout peut être fait indépendamment, mais cela prendra probablement beaucoup de temps et vous devrez passer d'un travail à un autre. Mais vous pouvez embaucher des assistants. Ensuite, il faudra choisir le nombre d'assistants à embaucher et décider de ce qu'ils devraient être en mesure de faire. Vous pouvez, par exemple, embaucher deux ouvriers et travailler avec eux. Ensuite, vous devez toujours passer d'une œuvre à une autre, mais maintenant les choses iront plus vite, car il y aura plus d'artistes.
Vous pouvez choisir une autre option - embaucher une équipe de spécialistes, comme un maçon, un charpentier, un électricien et un plombier. Chacun travaillera dans sa propre spécialité, par conséquent, jusqu'à ce que le plombier ait un front de travail, il restera inactif. Et pourtant, les choses iront plus vite qu'avant, car il y a plus de travailleurs, et tandis que l'électricien effectuera le câblage dans la cuisine, le plombier peut aller aux toilettes. Mais lorsqu'il n'y a pas de travail pour un spécialiste spécifique, plus de temps d'arrêt sont obtenus. Cependant, on peut noter que même avec les temps d'arrêt pris en compte, le travail se déplace plus rapidement lorsque des spécialistes viennent au travail, plutôt qu'une équipe de travailleurs. Les spécialistes n'ont pas besoin de changer constamment d'outils et chacun d'entre eux accomplira sa tâche plus rapidement que l'ouvrier. Que ce soit effectivement le cas, cela dépend des circonstances spécifiques: tout est appris dans la pratique.
Même si vous impliquez des spécialistes, vous devez toujours choisir un nombre différent de travailleurs de différentes spécialités. Il est peut-être judicieux d'embaucher, par exemple, plus de maçons que d'électriciens. De plus, la composition de votre équipe et l'efficacité globale de son travail peuvent changer si vous devez construire plusieurs maisons à la fois. Même s'il y a peu de travail pour un plombier dans une seule maison, alors lors de la construction de plusieurs maisons à la fois, il peut être pris pour toute la journée. De plus, si vous n'avez pas à payer de spécialistes pour les temps d'arrêt, vous pouvez recruter une équipe plus importante, même si le nombre de personnes travaillant simultanément ne change pas.
Mais arrêtez de parler de la construction. Qu'est-ce que tout cela a à voir avec les threads? Et vous pouvez leur appliquer des considérations similaires. Vous devez décider du nombre de threads à utiliser et des tâches à effectuer. Avons-nous besoin de fils universels qui effectuent le travail nécessaire à un moment particulier, ou de fils spécialisés bien adaptés à une seule chose? Ou peut-être vaut-il la peine de combiner les deux? Ces décisions doivent être prises quelles que soient les raisons de la parallélisation du programme, et les performances et la clarté du code dépendent considérablement de leur succès. Par conséquent, il est si important d'imaginer quelles options sont disponibles afin de prendre une décision compétente lors du développement de la structure de l'application. Dans cette section, nous considérerons un certain nombre de méthodes de distribution des tâches, en commençant par la distribution des données entre les threads jusqu'à ce que tout autre travail soit effectué.
8.1.1. Répartition des données entre les threads avant traitement
Les plus faciles à paralléliser sont des algorithmes simples, tels que std :: for_each, qui effectuent des opérations sur chaque élément d'un ensemble de données. Pour paralléliser cet algorithme, vous pouvez affecter chaque élément à l'un des threads de traitement. À l'avenir, lors de l'examen des problèmes de performances, il deviendra clair que la meilleure option de distribution pour obtenir des performances optimales dépend des caractéristiques de la structure des données.
Lors de la distribution de données, le cas le plus simple est celui où les N premiers éléments sont affectés à un flux, les N éléments suivants à un autre, et ainsi de suite (Fig. 8.1), mais d'autres schémas peuvent être utilisés. Quelle que soit la méthode de distribution des données, chaque thread ne traite que les éléments qui lui sont attribués, sans interagir avec les autres threads jusqu'à la fin du traitement.
La structure doit être familière à toute personne ayant
travaillé avec la programmation dans les environnements Message Passing Interface (MPI,
www.mpi-forum.org ) ou OpenMP (http://www.openmp.org/): la tâche est divisée en plusieurs tâches exécutées en parallèle, les workflows les exécutent indépendamment les uns des autres et les résultats sont collectés au stade final de l'information. Cette approche a été utilisée dans l'exemple avec la fonction d'accumulation de la section 2.4: les tâches parallèles et l'étape de réduction sont une accumulation. Pour un algorithme for_each simple, l'étape finale est manquante, car il n'y a rien à réduire.
Le fait qu'un mix soit défini comme l'essence de l'étape finale joue un rôle très important: une implémentation élémentaire similaire à celle montrée dans l'extrait 2.9 effectuera ce mix comme une étape séquentielle finale. Mais souvent, cette étape est également parallélisée: l'accumulation est une opération de réduction, de sorte que le code du Listing 2.9 peut être modifié pour obtenir un appel récursif du même code lorsque, par exemple, le nombre de threads est supérieur au nombre minimal d'éléments traités par le thread. Vous pouvez également forcer les workflows à effectuer des étapes de cumul dès que chacun d'eux a terminé sa tâche, plutôt que de démarrer de nouveaux threads à chaque fois.
Malgré toute son efficacité, cette technique n'est pas polyvalente. Parfois, les données ne peuvent pas être divisées à l'avance avec précision, car la composition de chaque pièce n'est connue qu'au cours du traitement. En particulier, cela est évident lorsque vous utilisez des algorithmes récursifs tels que Quicksort, ils nécessitent donc une approche différente.
8.1.2. Distribution de données récursive
L'algorithme Quicksort comporte deux étapes principales: la division des données en deux parties - tout ce qui revient à l'un des éléments (référence), et tout ce qui se trouve après dans l'ordre de tri final, et le tri récursif de ces deux moitiés. Il est impossible de le paralléliser en divisant au préalable les données, car il est possible de déterminer dans quelle «moitié» elles tombent uniquement lors du traitement des éléments. Si vous avez l'intention de paralléliser cet algorithme, vous devez utiliser l'essence même de la récursivité. À chaque niveau de récursivité, de plus en plus d'appels à la fonction quick_sort sont effectués, car vous devez trier ceux qui sont plus grands que la référence et ceux qui sont plus petits que lui. Ces appels récursifs sont indépendants les uns des autres car ils font référence à des ensembles d'éléments distincts. De ce fait, ils sont les premiers candidats à la compétitivité. Cette distribution récursive est représentée sur la Fig. 8.2.
Cette implémentation a déjà été rencontrée au chapitre 4. Au lieu de faire deux appels récursifs pour les moitiés plus grandes et plus petites, nous avons utilisé la fonction std :: async (), qui exécute des tâches asynchrones pour la moitié la plus petite à chaque étape. En raison de l'utilisation de std :: async (), la bibliothèque de threads C ++ a dû décider quand démarrer la tâche dans un nouveau thread et quand - en mode synchrone.
Il existe une circonstance importante: lors du tri d'un grand ensemble de données, le démarrage d'un nouveau thread pour chaque récursivité entraînera une augmentation rapide du nombre de threads. Lors de l'examen des problèmes de performances, il sera démontré qu'un trop grand nombre de threads peuvent ralentir l'application. En outre, avec un grand nombre de flux de données, cela peut tout simplement ne pas suffire. L'idée même de diviser la tâche entière dans un tel mode récursif semble très réussie, il vous suffit de surveiller attentivement le nombre de threads. Dans les cas simples, la fonction std :: async () gère cela, mais il existe d'autres options.
L'un d'eux consiste à utiliser la fonction std :: thread :: hardware_concurrency () pour sélectionner le nombre de threads, comme cela a été fait dans la version parallèle de la fonction accumulate () du Listing 2.9. Ensuite, au lieu de démarrer un nouveau thread pour chaque appel récursif, vous pouvez placer le fragment à trier sur une pile adaptée aux threads, par exemple, comme indiqué dans les chapitres 6 et 7. Si le thread n'a rien à faire ou s'il a fini de traiter tous ses fragments ou attend que le fragment soit trié, il peut prenez un fragment de la pile et triez-le.
Le listing 8.1 montre une implémentation simple de cette technologie. Comme dans la plupart des autres exemples, il ne fait que démontrer l'intention et n'est pas un code prêt pour une utilisation pratique. Si vous utilisez le compilateur C ++ 17 et que votre bibliothèque le prend en charge, vous devez utiliser les algorithmes parallèles fournis par la bibliothèque standard conformément aux descriptions données au chapitre 10.
Listing 8.1. Un algorithme Quicksort parallèle qui utilise une pile de fragments en attente de tri
Ici, la fonction parallel_quick_sort
(19) place la majeure partie des responsabilités fonctionnelles sur la classe sorter
(1) , qui fournit un moyen facile de regrouper la pile de fragments non triés
(2) et de plusieurs threads
(3) . Le travail principal est effectué dans la fonction du composant do_sort
(9) , qui est occupée par le partitionnement de données habituel
(10) . Cette fois, au lieu de démarrer un nouveau thread pour chaque fragment, il pousse ce fragment sur la pile (11) et ne démarre un nouveau thread que s'il existe une ressource processeur libre (12). Puisqu'un fragment avec des valeurs inférieures à celle de la référence peut être traité par un autre flux, nous devons attendre sa disponibilité
(13) . Afin que le temps ne soit pas perdu (dans le cas où nous avons un seul thread ou que tous les autres threads sont déjà occupés), une tentative est faite pour traiter les fragments de la pile pendant cette période d'attente
(14) . La fonction try_sort_chunk récupère un fragment de la pile
(7) , le trie
(8) et enregistre les résultats dans la promesse de promesse afin qu'ils puissent recevoir le flux qui a mis ce fragment sur la pile
(15) .
Maintenant, les threads qui viennent d'être lancés sont en boucle et essaient de trier les fragments de la pile
(17) si l'indicateur end_of_data
(16) n'est pas défini. Entre les vérifications, ils abandonnent la ressource informatique à d'autres threads afin de pouvoir pousser du travail supplémentaire sur la pile. Le travail du code en termes de mise en ordre de ces threads dépend du destructeur de votre classe sorter
(4) . Lorsque toutes les données sont triées, la fonction do_sort renverra le contrôle (même en maintenant l'activité des threads de travail), le thread principal reviendra de parallel_quick_sort
(20) et détruira l'objet trieur. Il définira l'indicateur end_of_data
(5) et attendra que les threads finissent de fonctionner
(6). La définition de l'indicateur arrêtera la boucle dans la fonction des threads (16).
Avec cette approche, le problème du nombre illimité de threads inhérent à la fonction spawn_task qui a lancé le nouveau thread disparaîtra et la dépendance à la bibliothèque de threads C ++, qui sélectionnera le nombre de threads pour vous, comme lors de l'utilisation de std :: async (), disparaîtra. Au lieu de cela, pour éviter un changement de tâche trop fréquent, le nombre de threads est limité par la valeur renvoyée par la fonction std :: thread :: hardware_concurrency (). Mais un autre problème se pose: la gestion de ces flux et l'échange de données entre eux compliquent grandement le code. De plus, malgré le fait que les threads traitent des éléments de données individuels, tous accèdent à la pile, y ajoutant de nouveaux fragments et prenant des fragments pour traitement. Une concurrence aussi intense peut réduire les performances, même si une pile sans verrouillage (et donc non bloquante) est utilisée, et les raisons de cela seront bientôt examinées.
Cette approche est une version spéciale du pool de threads - un ensemble de threads, chacun recevant le travail de la liste des travaux différés, l'exécute, puis se tourne vers la liste pour un nouveau. Certains problèmes potentiels inhérents au pool de threads (y compris la concurrence lors de l'accès à la liste des travaux) et les moyens de les résoudre sont abordés dans le chapitre 9. Sur la mise à l'échelle de l'application créée afin qu'elle s'exécute sur plusieurs processeurs, nous aborderons ce chapitre un peu plus tard (voir sous-section 8.2.1).
Lors de la distribution des données avant le traitement et en mode récursif, il est supposé qu'elles sont fixées à l'avance et une recherche est en cours pour leur distribution. Mais cela ne se produit pas toujours: si les données sont créées en mode dynamique ou proviennent d'une source externe, cette approche ne fonctionne pas. Dans ce cas, il peut être plus raisonnable de répartir le travail en fonction du type de tâche et non en fonction des données elles-mêmes.
8.1.3. Répartition du travail par type de tâche
La répartition du travail entre les threads en attribuant à chacun d'entre eux (à l'avance ou de manière récursive pendant le traitement des données) différentes données dans tous les cas est basée sur l'hypothèse que les threads vont faire le même travail sur chaque pièce. Une autre distribution du travail est la spécialisation des flux, où chacun effectue une tâche distincte, car les plombiers et les électriciens effectuent différentes tâches dans la construction d'une maison. Les flux peuvent fonctionner avec des données différentes ou identiques, mais dans ce dernier cas, ils le font à des fins différentes.
Cette division particulière du travail résulte de la séparation des tâches à l'aide de la concurrence: chaque fil a une tâche distincte, qu'il effectue indépendamment des autres flux. Parfois, d'autres threads peuvent fournir des données au flux ou produire des événements auxquels il doit répondre, mais en général, chaque flux se concentre sur les performances de haute qualité d'une seule tâche. C'est une bonne conception de base, où chaque morceau de code doit être responsable d'une chose.
Répartition du travail par type de tâche afin de partager les responsabilités
Une application monothread doit faire face à des conflits liés au principe de responsabilité unique, lorsque plusieurs tâches doivent être exécutées en continu pendant un certain temps, ou que l'application doit faire face au traitement des événements entrants en temps opportun (par exemple, un utilisateur appuie sur une touche ou des données arrivent sur le réseau) en présence d'autres tâches inachevées. Dans un environnement informatique à thread unique, vous devez créer indépendamment du code qui exécute une partie de la tâche A, une partie de la tâche B, vérifie si une touche est enfoncée et s'il n'y a pas de paquets réseau, puis revient cycliquement à la partie suivante de la tâche A. tâches A en raison de la nécessité de maintenir son état et de rendre périodiquement le contrôle à la boucle principale. Si vous ajoutez trop de tâches au cycle, le travail peut ralentir considérablement et l'utilisateur remarquera probablement une réaction lente aux frappes. Je suis sûr que tout le monde a observé les manifestations extrêmes d'une situation similaire dans certaines applications: vous définissez une tâche pour l'application, et l'interface ne réagit à rien tant qu'elle n'est pas terminée.
Ici, les flux entrent en scène. Si vous exécutez chaque tâche dans un thread distinct, le système d'exploitation peut le faire à votre place. Dans le code de la tâche A, vous pouvez vous concentrer sur l'achèvement de la tâche sans vous soucier du maintien de l'état et du retour à la boucle principale, ni du temps qui s'écoulera avant que cela ne se produise. Autrement dit, le système d'exploitation enregistrera automatiquement l'état et passera au bon moment à la tâche B ou C, et si le système sur lequel le programme sera exécuté a plusieurs cœurs ou processeurs, il sera possible d'exécuter simultanément les tâches A et B. Le code de traitement des frappes ou des reçus les paquets réseau peuvent maintenant être exécutés en temps opportun, et tout le monde en bénéficiera: l'utilisateur recevra une réponse adéquate du programme et vous, en tant que développeur, recevrez un code simplifié, car chaque flux peut être dirigé effectuer des opérations directement liées à ses fonctions, sans les mélanger avec le flux de contrôle et l'interaction avec l'utilisateur.
Une image idéale se dessine. Mais tout peut-il se passer de cette façon? Comme toujours, tout dépend des circonstances spécifiques. Si l'indépendance totale est respectée et que les flux n'ont pas besoin d'échanger des données entre eux, c'est exactement ce qui se passera. Malheureusement, une situation similaire est observée assez rarement. Souvent, les actions nécessaires à l'utilisateur ont la forme de tâches d'arrière-plan pratiques, et elles doivent informer l'utilisateur de la tâche, mettant à jour l'interface utilisateur d'une manière ou d'une autre. Ou l'utilisateur peut avoir besoin d'arrêter la tâche, donc l'interface utilisateur devra en quelque sorte envoyer un message à la tâche en arrière-plan, ce qui provoquera l'arrêt de son exécution. Dans les deux cas, il est nécessaire de considérer soigneusement la conception et la synchronisation appropriée, mais les tâches effectuées resteront fragmentées. Le thread d'interface utilisateur contrôle toujours cette interface, mais il peut être affecté à l'exécution d'une mise à jour à la demande d'autres threads. Un thread qui implémente une tâche en arrière-plan se concentre toujours sur les opérations requises pour la terminer; il arrive également que l'un des threads en arrière-plan permette à la tâche d'arrêter l'autre thread. Dans les deux cas, les flux ne se soucient pas de l'origine de la demande, ils se soucient uniquement du fait qu'elle soit conçue pour eux et directement liée à leurs responsabilités.
Le partage des responsabilités entre plusieurs threads présente deux dangers graves. Premièrement, il peut s’avérer que des responsabilités inappropriées sont réparties. Un signe de cela est trop de données partagées par les flux, ou le fait que différents flux doivent s’attendre les uns les autres. . . , , , , . , , — , , .
. , , .
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»Plus d'informations sur le livre sont disponibles sur
le site Web de l'éditeur»
Contenu»
Extrait25% —
C++Lors du paiement de la version papier du livre, un livre électronique est envoyé par e-mail.