Les algorithmes sans verrou fonctionnent-ils vraiment mieux que leurs homologues complets?

Raymond Chen a réalisé une énorme série sur les algorithmes sans verrou . Au-delà des cas simples des fonctions InterlockedXxx , il semble que le modèle qui prévaut avec tous ces éléments est qu’ils implémentent leurs propres verrous . Bien sûr, il n’y a pas de verrou de processeur, mais le concept de bouclage sur chaque processeur pour assurer la cohérence ressemble beaucoup à un verrou tournant. Et étant un spinlock, ils seront moins efficaces que les verrous généraux fournis avec le système d’exploitation, car ils ne permettent pas de contrôler leurs quanta en attendant d’autres threads. Par conséquent, chaque fois que quelqu’un vient me voir et me dit “mais mon algorithme est sans verrou”, ma réponse générale est “alors”?

Je suis curieux – y a-t-il des points de référence disponibles qui montrent des algorithmes sans verrou pour avoir une longueur d’avance sur leurs homologues complets?

    En général, les algorithmes sans verrou sont moins efficaces par thread – vous faites plus de travail, comme vous l’avez mentionné, pour implémenter un algorithme sans verrou qu’un simple verrou.

    Cependant, ils ont tendance à améliorer considérablement le débit global de l’algorithme dans son ensemble face aux conflits. La latence de commutation de threads et les changements de contexte , qui, rapidement, sur de nombreux threads, ralentissent considérablement le débit de votre application. Les algorithmes sans verrou implémentent effectivement leurs propres “verrous”, mais ils le font d’une manière qui empêche ou réduit le nombre de changements de contexte, raison pour laquelle ils ont tendance à exécuter leurs homologues de locking.

    Cela étant dit – la plupart de cela dépend de l’algorithme (et de la mise en œuvre) en question. Par exemple, j’ai eu quelques routines que j’ai réussi à passer aux nouvelles collections simultanées de .NET 4 au lieu d’utiliser les mécanismes de locking précédents et j’ai mesuré des améliorations de près de 30% de la vitesse totale de mon algorithme. Cela étant dit, vous pouvez trouver de nombreux points de référence qui montrent des performances réduites en utilisant certaines de ces mêmes collections par rapport à un verrou de base. Comme pour toutes les optimisations de performances, vous ne le savez vraiment pas avant de mesurer .

    Au-delà des cas simples des fonctions InterlockedXxx, il semble que le modèle qui prévaut avec tous ces éléments est qu’ils implémentent leurs propres verrous.

    Aucune des réponses ne semble vraiment aller au cœur de la différence entre une boucle CAS “sans verrou” et un mutex ou un spin-lock.

    La différence importante est que les algorithmes sans verrou sont garantis pour progresser par eux-mêmes , sans l’aide d’autres threads. Avec un verrou ou un verrou de rotation, tout thread de mauvaise qualité qui ne peut pas acquérir un verrou est entièrement à la merci du thread propriétaire du verrou. Le thread médiocre qui ne peut pas acquérir le verrou ne peut rien faire d’autre que d’ attendre (via une attente chargée ou un sumil assisté par le système d’exploitation).

    Avec des algorithmes sans verrou qui effectuent une boucle sur un CAS, chaque thread est assuré de progresser, indépendamment de ce que font les autres threads rivaux. Chaque fil est essentiellement en contrôle de son propre destin. Oui, il se peut qu’il doive toujours effectuer une boucle plusieurs fois, mais le nombre de fois qu’il boucle est limité par le nombre de threads en conflit. Il ne peut pas boucler à l’infini, pour la plupart. (En pratique, il est possible que le locking en direct se produise, par exemple, une boucle LL / SC qui échoue en raison d’un faux partage) – mais le thread lui-même peut prendre des mesures pour y remédier – il n’est pas à la merci d’un autre thread tenant une serrure.

    Quant à la performance, cela dépend. J’ai vu des exemples flagrants d’algorithmes sans locking être totalement surpassés par leurs homologues de locking, même avec des conflits de threads élevés. Sur une machine x86-64 exécutant Debian 7, j’ai comparé les performances entre la queue C ++ Boost.Lockfree (basée sur l’algorithme Michael / Scott) et une vieille std::queue surround par un std::mutex . Sous contention de thread élevé, la version lockfree était presque deux fois plus lente.

    Alors pourquoi ça? Eh bien, la performance des algorithmes sans locking dépend des détails de la mise en œuvre. Comment l’algorithme évite-t-il l’ABA? Comment accomplit-il la récupération de la mémoire en toute sécurité? Il y a tellement de variantes … pointeurs balisés, récupération basée sur l’époque, état RCU / quiescent, pointeurs de danger, récupération de place générale à l’échelle du processus, etc. Toutes ces stratégies ont des conséquences sur les performances et certaines ressortingctions peut être conçu. En général, les approches de comptage de référence (ou les approches de pointeurs marqués) ont tendance à mal fonctionner, selon mon expérience. Mais les alternatives peuvent être beaucoup plus complexes à implémenter et requièrent beaucoup plus d’infrastructure de récupération de la mémoire basée sur le stockage local de threads ou la récupération de place généralisée.

    Sans verrou n’est pas nécessairement plus rapide, mais il peut éliminer la possibilité de blocage ou de blocage, vous pouvez donc garantir que votre programme progressera toujours vers la finition. Avec les verrous, il est difficile de faire une telle garantie – il est trop facile de manquer une séquence d’exécution possible qui se traduit par un blocage.

    Passé cela, tout dépend. Au moins dans mon expérience, les différences de vitesse ont tendance à dépendre davantage du niveau de compétences déployé dans l’implémentation que de l’utilisation ou non de verrous.

    Sous Windows sur x64, une freelist free-free (pas de combinaison en face de la version freelist) est de l’ordre d’un ordre de grandeur plus rapide que celle d’une freelist basée sur le mutex.

    Sur mon ordinateur portable (Core i5), pour un seul thread, je dispose d’environ 31 millions d’opérations freelist par seconde, contre environ 2,3 millions d’opérations par seconde pour le mutex.

    Pour deux threads (sur des cœurs physiques distincts), avec un sans verrou, j’obtiens environ 12,4 millions d’opérations freelist par thread. Avec un mutex, j’obtiens environ 80 milliers d’ opérations par seconde.

    Les algorithmes sans verrou peuvent être absolument plus rapides que leur homologue bloquant. Mais bien sûr, l’inverse est également vrai. En supposant que l’implémentation fonctionne mieux que la partie de compteur de locking, le seul facteur limitant est la contention.

    Prenez les deux classes Java, ConcurrentLinkedQueue et LinkedBlockingQueue. Dans un contexte de marché réel modéré, le CLQ surpasse largement le LBQ. Avec une forte contention, l’utilisation de threads de suspension permettra au LBQ de mieux fonctionner.

    Je ne suis pas d’accord avec user237815. Le mot-clé synchronisé ne nécessite pas autant de temps que par le passé, mais il est associé à un algorithme sans verrou par rapport à un seul CAS.

    Le principal avantage des algorithmes véritablement sans locking est qu’ils sont robustes même si une tâche est bloquée (notez que le locking libre est une condition plus difficile que “ne pas utiliser de verrous” (*)). Bien qu’il soit avantageux d’éviter les lockings inutiles, les structures de données les plus performantes sont souvent celles qui peuvent se verrouiller dans de nombreux cas, mais qui peuvent utiliser des verrous pour réduire les risques de coups.

    (*) J’ai vu des tentatives de “verrouiller” des files d’attente multi-producteurs où un producteur qui se faisait passer au mauvais moment empêcherait les consommateurs de voir de nouveaux éléments jusqu’à ce qu’il termine son travail); de telles structures de données ne devraient pas vraiment s’appeler “sans verrou”. Un producteur bloqué n’empêche pas d’autres producteurs de progresser, mais peut bloquer arbitrairement les consommateurs.

    En Java, au moins, le locking par lui-même peut être très rapide. Le mot-clé synchronisé n’ajoute pas beaucoup de surcharge. Vous pouvez le tester vous-même simplement en appelant une méthode synchronisée dans une boucle.

    Le locking ne devient lent que lorsqu’il y a conflit, et le processus verrouillé n’est pas instantané.

    Récemment, sur JavaOne Russia, un employé d’Oracle (spécialiste des performances et des benchmarks Java) a montré des mesures sur les opérations par seconde dans un access parallèle à un simple compteur, en utilisant des verrous CAS (java). .util.concurrent.locks.ReentrantLock)

    http://soffr.miximages.com/synchronization/lock-free-vs-locks.png // désolé, je ne peux pas coller d’images

    De ce fait, les verrous tournants ne sont plus performants que jusqu’à ce que le nombre de threads tente d’accéder au moniteur.

    Lock-free a également l’avantage de ne pas dormir. Il y a des endroits dans les kernelx où vous n’êtes pas autorisé à dormir – le kernel Windows en a beaucoup – et cela limite grandement votre capacité à utiliser des structures de données.