Conséquences sur les performances d’un grand nombre de mutex

Supposons que j’ai un tableau de 1 000 000 d’éléments et un nombre de threads de travail, chacun manipulant des données dans ce tableau. Les threads de travail peuvent mettre à jour des éléments déjà remplis avec de nouvelles données, mais chaque opération est limitée à un seul élément de tableau et est indépendante des valeurs de tout autre élément.

L’utilisation d’un seul mutex pour protéger l’ensemble du tableau entraînerait clairement une forte contention. À l’extrême opposé, je pourrais créer un tableau de mutex de la même longueur que le tableau d’origine et, pour chaque array[i] éléments array[i] je verrouillerais le mutex[i] tout en opérant dessus. En supposant une dissortingbution uniforme des données, cela éliminerait essentiellement les conflits de verrous, au prix de beaucoup de mémoire.

Je pense qu’une solution plus raisonnable serait d’avoir un tableau de n mutexes (où 1 <n <1000000). Ensuite, pour chaque array[i] éléments array[i] je verrouillerais le mutex[i % n] tout en l’opérant. Si n est suffisamment grand, je peux toujours minimiser les conflits.

Ma question est donc la suivante: existe-t-il un inconvénient, en termes de performances, à utiliser un grand nombre de mutex (par exemple> = 1000000) de cette manière, au-delà d’une utilisation accrue de la mémoire? Si tel est le cas, combien de mutex pouvez-vous raisonnablement utiliser avant de commencer à voir une dégradation?

Je suis sûr que la réponse à cette question dépend de la plate-forme. J’utilise des pthreads sur Linux. Je travaille également à la mise en place de mes propres points de repère, mais l’échelle de données sur laquelle je travaille me fait perdre beaucoup de temps. Des indications initiales seraient donc utiles.


C’était la question initiale. Pour ceux qui demandent des informations plus détaillées sur le problème, j’ai 4 fichiers de données binarys de plusieurs Go décrivant environ un demi-milliard d’événements analysés. Le tableau en question est en réalité le tableau de pointeurs soutenant une très grande table de hachage chaînée. Nous lisons les quatre fichiers de données dans la table de hachage, en les agrégeant éventuellement s’ils partagent certaines caractéristiques. L’implémentation existante comporte 4 threads, chacun lisant un fichier et insérant les enregistrements de ce fichier dans la table de hachage. La table de hachage a 997 verrous et 997 * 9973 = ~ 10 000 000 pointeurs. Lors de l’insertion d’un élément de hachage h , je verrouille d’abord le mutex[h % 997] avant d’insérer ou de modifier l’élément dans le bucket[h % 9943081] . Cela fonctionne très bien et, autant que je sache, nous n’avons pas eu beaucoup de problèmes de conflit, mais le goulot d’étranglement lié aux performances réside dans le fait que nous n’utilisons que 4 cœurs d’une machine à 16 cœurs. (Et encore moins au fur et à mesure, car les fichiers ne sont généralement pas tous de la même taille.) Une fois que toutes les données ont été lues en mémoire, nous les analysons, qui utilise de nouveaux threads et une nouvelle stratégie de locking adaptée aux différents types de fichiers. charge de travail.

J’essaie d’améliorer les performances de l’étape de chargement de données en passant à un pool de threads. Dans le nouveau modèle, il me rest un fil pour chaque fichier, qui lit simplement le fichier en morceaux d’environ 1 Mo et transmet chaque morceau à un fil de travail du pool à parsingr et à insérer. Le gain de performances jusqu’à présent a été minime, et le profil que j’ai fait semble indiquer que le temps passé à verrouiller et déverrouiller la masortingce était probablement le coupable. Le locking est intégré à l’implémentation de la table de hachage que nous utilisons, mais il permet de spécifier le nombre de verrous à utiliser indépendamment de la taille de la table. J’espère accélérer les choses sans changer l’implémentation de la table de hachage elle-même.

(Une réponse très partielle et éventuellement indirecte à votre question.)

Une fois que vous avez enregistré un énorme succès de performance, essayez ceci (sur un CentOS), augmentant ainsi le nombre de verrous d’un nombre premier d’environ 1K à un nombre maximal d’environ 1 M. Bien que je n’aie jamais bien compris sa raison, j’ai fini par comprendre (ou tout simplement par me convaincre) que c’était la mauvaise question.

Supposons que vous ayez un tableau de longueur M , avec n travailleurs. De plus, vous utilisez une fonction de hachage pour protéger les M éléments avec m verrous (par exemple, par un groupement aléatoire). Ensuite, en utilisant l’ approximation carrée du paradoxe de l’anniversaire , le risque de collision entre deux ouvriers – p – est donné par:

p ~ n 2 / (2m)


Il s’ensuit que le nombre de mutex dont vous avez besoin, m , ne dépend pas du tout de M – il ne dépend que de p et n .

Sous Linux, il n’y a aucun coût autre que la mémoire associée à davantage de mutex.

Cependant , rappelez-vous que la mémoire utilisée par vos mutex doit être incluse dans votre jeu de travail. Si la taille de votre jeu de travail dépasse la taille de la mémoire cache correspondante, vous constaterez une baisse importante des performances. Cela signifie que vous ne voulez pas d’un tableau de mutex de taille excessive.

Comme le souligne Ami Tavory , la controverse dépend du nombre de mutex et du nombre de threads, et non du nombre d’éléments de données protégés. Il n’y a donc aucune raison de lier le nombre de mutex au nombre d’éléments de données (avec la condition évidente n’a jamais de sens d’avoir plus de mutex que d’éléments).

Dans le scénario général, je conseillerais

  • Verrouiller simplement le tableau entier (simple, très souvent “assez bon” si votre application effectue principalement “d’autres tâches” en plus d’accéder au tableau)

    … ou …

  • Implémentation d’un verrou en lecture / écriture sur tout le tableau (en supposant que les lectures soient égales ou supérieures aux écritures)

Apparemment, votre scénario ne correspond à aucun cas.

Q: Avez-vous envisagé de mettre en place une sorte de “file d’écriture”?

Dans le pire des cas, vous n’auriez besoin que d’ un seul mutex. Dans le meilleur des cas, vous pourrez même utiliser un mécanisme sans verrou pour gérer votre queue. Recherchez ici quelques idées qui pourraient être applicables: https://msdn.microsoft.com/en-us/library/windows/desktop/ee418650%28v=vs.85%29.aspx