Quel est le moyen le plus efficace de coordonner entre les threads concernant les threads qui sont libres?

Question

Je travaille sur un programme qui envoie des messages entre threads, il regarde quels threads sont occupés, s'il y en a un de libre il le prend en premier (ou dans certains cas plusieurs libres), le marque comme pris, envoie du travail à ce thread et fait son propre travail, puis une fois terminé attend que le thread termine. La partie qui est le goulot d'étranglement de tout cela est de coordonner entre les threads pour savoir lequel est pris. semble être un problème que d'autres ont sûrement rencontré, ont des solutions à partager, mais veulent aussi savoir si vous pouvez faire mieux que moi.

Ma solution se résume finalement à : Maintenir un ensemble représentant les index des threads libres, et pouvoir prendre un élément de l'ensemble en obtenant l'index d'un thread libre ou le rajouter à l'ensemble en augmentant la taille de un. L'ordre n'est pas important. Je connais la taille fixe de l'ensemble à l'avance.

J'ai essayé quelques manières de faire cela :

1. Maintenir un seul unsigned long long int et utiliser '__builtin_clz' (Le '__builtin_ffsll' était 10 fois plus lent... je pense pas pris en charge avec une seule instruction sur mon processeur) pour compter le nombre de bits dans un seul cycle d'instruction et obtenir le plus bas et utiliser une table de recherche de masques de bits pour activer et désactiver les bits, réclamant simultanément leur numéro de thread. J'ai adoré cette version parce que je n'avais besoin de partager qu'un seul unsigned long long atomique et je pouvais utiliser une seule opération atomique mais faire 'fetch_and' dans une boucle jusqu'à ce que vous ayez raison s'est avéré plus lent que verrouiller et faire non atomiquement. La version utilisant un verrou s'est avérée plus rapide, probablement parce que les threads ne restaient pas bloqués dans des boucles à répéter les mêmes opérations en attente que les autres terminent les leurs.

2. Utilisez une liste chaînée, allouez tous les nœuds à l'avance, maintenez un nœud de tête et une liste, si elle pointe vers nullptr, alors nous avons atteint la fin de la liste. Je n'ai fait cela qu'avec un verrou car cela nécessite deux opérations simultanées.

3. Maintenir un tableau qui représente tous les index des threads à réclamer. Soit incrémenter un index du tableau et renvoyer un pointeur précédent pour réclamer un thread, soit échanger le dernier thread pris avec celui qui est libéré et décrémenter le pointeur. Vérifiez s'il est libre.

4. Utilisez la file d'attente moodycamel qui maintient une file d'attente sans verrouillage.

Heureux de partager du code C++, la réponse était en train de devenir assez longue cependant lorsque j'ai essayé de l'inclure.

Tous les trois sont rapides, '__builtin_clzll' n'est pas universellement pris en charge, donc même si un peu plus rapide, probablement pas assez pour en valoir la peine et probablement 10 fois plus lent sur les ordinateurs qui ne le prennent pas en charge nativement, semblable à la façon dont '__builtin_ffsll' était lent. Le tableau et la liste chaînée sont à peu près aussi rapides l'un que l'autre, le tableau semble légèrement plus rapide en l'absence de contention. Moodey est 3 fois plus lent.

Pensez-vous pouvoir faire mieux et avoir un moyen plus rapide de le faire ? Toujours la partie la plus lente de ce processus, juste en valant à peine le coût dans certains cas.

Idées de directions à explorer :

• Sentir qu'il devrait y avoir un moyen d'utiliser quelques atomiques, peut-être un tableau d'atomiques, un à la fois, doit maintenir l'intégrité de l'ensemble à chaque opération cependant, ce qui rend cela difficile. La plupart des solutions nécessitent à un moment donné deux opérations à faire simultanément, les atomiques semblent pouvoir fournir une solution significativement plus rapide que le verrouillage dans mon benchmarking.
• Pourrait être possible d'utiliser un verrou mais de supprimer le besoin de vérifier si la liste est vide ou de permuter les éléments dans le tableau
• Peut-être utiliser une structure de données différente, par exemple, deux tableaux, ajouter à l'un tout en vidant l'autre, puis changer celui qui est rempli et celui qui est vidé. Cela signifie pas besoin de permuter les éléments mais plutôt de permuter deux pointeurs vers des tableaux et uniquement lorsque l'un est vide.
• Pourrait avoir des threads lançant des threads ajoutant du travail à une liste de travaux à effectuer, alors un autre thread peut le récupérer pendant que ce thread continue. Au final, il faut toujours un ensemble sûr pour les threads similaires.
• Voir si les brillantes personnes de stackoverflow voient des directions à explorer que je n'ai pas encore vues :)

Answer 1

Tout ce dont vous avez besoin est un pool de threads, une file d'attente (une list, deque ou un tampon circulaire), un mutex et une condition_variable pour signaler qu'un nouvel élément de travail a été ajouté à la file d'attente.

Emballer les éléments de travail dans un packaged_task si vous avez besoin d'attendre le résultat de chaque tâche.

Lors de l'ajout d'un nouvel élément de travail à la file d'attente, 1) verrouiller le mutex, 2) ajouter l'élément, 3) relâcher le verrou et 4) appeler cv::notify_one, ce qui débloquera le premier thread disponible.

---

Une fois que la configuration de base fonctionne, si les tâches sont trop fines, le vol de travail peut être ajouté à la solution pour améliorer les performances. Il est également important d'utiliser le thread principal pour effectuer une partie du travail au lieu d'attendre simplement que toutes les tâches soient terminées. Ces simples (bien que maladroites) optimisations entraînent souvent une amélioration de >15% des performances globales en raison de la réduction des changements de contexte.

N'oubliez pas non plus de penser au faux partage. Il pourrait être judicieux de rembourrer les éléments de tâche à 64 octets, juste pour être du bon côté.