Existe-t-il une implémentation en C++ d'une file d'attente ou d'un hachage sans verrou, prête à être produite ?

Question

J'ai pas mal cherché sur Google une file d'attente sans verrou en C++. J'ai trouvé du code et quelques essais - mais rien que je puisse compiler. Un hash sans verrou serait également le bienvenu.

RÉSUMÉ : Jusqu'à présent, je n'ai pas de réponse positive. Il n'y a pas de bibliothèque "prête pour la production", et étonnamment aucune des bibliothèques existantes n'est conforme à l'API des conteneurs STL.

Answer 1

Boost.lockfree est une tentative de créer des implémentations c++ des classes de pile et fifo lockfree.

dépôt git public

Answer 2

Après avoir vérifié la plupart des réponses données, je ne peux qu'affirmer :

La réponse est NON .

Il n'existe pas de droit qui puisse être utilisé dès la sortie de la boîte.

Answer 3

La chose la plus proche que je connaisse est Listes singulièrement liées imbriquées de Windows . Bien entendu, il s'agit d'une application Windows uniquement.

Answer 4

Si vous avez une file d'attente/FIFO à producteurs multiples et à consommateurs uniques, vous pouvez facilement la rendre LockFree à l'aide de SLIST ou d'une pile LIFO triviale Lock Free. Il s'agit d'avoir une deuxième pile "privée" pour le consommateur (qui peut également être réalisée sous forme de SLIST pour plus de simplicité ou tout autre modèle de pile de votre choix). Le consommateur retire des éléments de la pile privée. Chaque fois que le LIFO privé est épuisé, vous effectuez un Flush plutôt qu'un Pop sur la SLIST concurrente partagée (en saisissant toute la chaîne SLIST), puis vous parcourez la liste Flushed dans l'ordre en poussant les éléments sur la pile privée.

Cela fonctionne pour un producteur unique / un consommateur unique et pour un producteur multiple / un consommateur unique.

Cependant, il ne fonctionne pas pour les cas de consommateurs multiples (avec un producteur unique ou des producteurs multiples).

Par ailleurs, les tables de hachage sont un candidat idéal pour le "striping", qui consiste simplement à diviser la table de hachage en segments et à disposer d'un verrou par segment du cache. C'est ainsi que procède la bibliothèque concurrente de Java (en utilisant 32 bandes). Si vous disposez d'un verrou lecteur-écrivain léger, la table de hachage peut être accédée simultanément pour des lectures simultanées et vous ne bloquerez que lorsque des écritures se produiront sur des bandes contestées (et éventuellement si vous autorisez la croissance de la table de hachage).

Si vous créez le vôtre, veillez à intercaler vos verrous avec les entrées de hachage plutôt que de placer tous vos verrous dans un tableau les uns à côté des autres, afin de réduire les risques de faux partages.

Answer 5

J'arrive peut-être un peu tard sur ce sujet.

L'absence de solutions (au moment où la question a été posée) est principalement due à un problème important en C++ (avant C++0x/11) : Le C++ n'a pas de modèle de mémoire concurrente.

Maintenant, en utilisant std::atomic, vous pouvez contrôler les problèmes d'ordre de la mémoire et avoir des opérations de comparaison et d'échange correctes. J'ai moi-même écrit une implémentation de la file d'attente sans verrou de Micheal&Scott (PODC96) en utilisant C++11 et les pointeurs aléatoires de Micheal (IEEE TPDS 2004) pour éviter les problèmes de libération précoce et d'ABA. Cela fonctionne bien mais c'est une implémentation rapide et sale et je ne suis pas satisfait des performances actuelles. Le code est disponible sur bitbucket : Expérience LockFree

Il est également possible d'implémenter une file d'attente sans verrou sans pointeurs de danger en utilisant le CAS à deux mots (mais les versions 64bit ne seront possibles que sur x86-64 en utilisant cmpxchg16b), j'ai un article de blog à ce sujet (avec un code non testé pour la file d'attente) ici : Mise en œuvre d'une comparaison générique à deux mots et d'un échange pour x86/x86-64 (Blog de la LSE.)

Mes propres benchmarks me montrent que la file d'attente doublement verrouillée (également dans l'article de Micheal&Scott de 1996) fonctionne aussi bien que la file d'attente sans verrou (je n'ai pas atteint un niveau de contention suffisant pour que les structures de données verrouillées aient des problèmes de performances, mais mes benchs sont trop légers pour l'instant) et la file d'attente concurrente du TBB d'Intel semble même meilleure (deux fois plus rapide) pour un nombre relativement faible (dépendant du système d'exploitation, sous FreeBSD 9, la limite la plus basse que j'ai trouvée jusqu'à présent, ce nombre est de 8 threads sur un i7 avec 4 ht-core, et donc 8 CPUs logiques) de threads et ont un comportement très étrange (le temps d'exécution de mon benchmark simple passe de quelques secondes à des heures ! )

Une autre limitation concernant les files d'attente sans verrou dans le style STL : le fait d'avoir des itérateurs sur une file d'attente sans verrou n'a pas de sens.