Les algorithmes sans verrou sont-ils vraiment plus performants que leurs homologues avec verrou ?

Question

Raymond Chen a fait un énorme série sur lockfree algorithmes . Au-delà des cas simples de la InterlockedXxx fonctions, il semble que le modèle dominant avec toutes ces fonctions est qu'elles mettre en place leurs propres verrous . Bien sûr, il n'y a pas de verrous de processeur, mais le concept de boucle sur chaque CPU pour assurer la cohérence est très proche d'un spinlock. Et comme il s'agit d'un spinlock, ils seront moins efficaces que les verrous généraux fournis avec le système d'exploitation, car ils ne cèdent pas le contrôle de 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 "et alors" ?

Je suis curieux y a-t-il repères disponibles qui montrent que les algorithmes sans verrou ont un avantage sur leurs homologues avec verrou ?

Answer 1

En général, les algorithmes sans verrou sont moins efficaces par thread - vous faites plus de travail, comme vous l'avez mentionné, afin de mettre en œuvre 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 en cas de conflit. Latence de commutation de threads et changements de contexte qui sont rapides, 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, ce qui explique pourquoi ils ont tendance à être plus performants que leurs homologues à verrouillage.

Cela dit, la plupart de ces éléments dépendent de l'algorithme (et de sa mise en œuvre) en question. Par exemple, j'ai quelques routines que j'ai réussi à faire passer aux nouvelles collections concurrentes de .NET 4 au lieu d'utiliser les mécanismes de verrouillage précédents, et j'ai mesuré des améliorations de près de 30% dans la vitesse totale de mon algorithme. Ceci étant dit, vous pouvez trouver de nombreux benchmarks qui montrent des performances réduites en utilisant certaines de ces mêmes collections par rapport à un verrouillage de base. Comme pour toutes les optimisations de performances, vous ne pouvez pas vraiment savoir avant d'avoir mesure .

Answer 2

L'absence de verrou n'est pas nécessairement plus rapide, mais elle permet d'éliminer la possibilité d'un verrou ou d'un livelock, de sorte que vous pouvez garantir que votre programme progressera toujours vers la fin. Avec des verrous, il est difficile de faire une telle garantie - il est trop facile de manquer une séquence d'exécution possible qui aboutit à un blocage.

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

Answer 3

L'avantage principal des algorithmes véritablement sans verrou est qu'ils sont robustes même si une tâche est bloquée (notez que l'absence de verrou est une condition plus difficile que de "ne pas utiliser de verrou"(*)). Bien qu'il y ait des avantages en termes de performances à éviter les verrouillages inutiles, les structures de données les plus performantes sont souvent celles qui peuvent utiliser les verrouillages dans de nombreux cas, mais qui peuvent utiliser les verrouillages pour minimiser le thrashing.

(*)J'ai vu quelques tentatives de files d'attente multi-producteurs "sans verrou" où un producteur qui se faisait bloquer au mauvais moment empêchait les consommateurs de voir les nouveaux éléments jusqu'à ce qu'il ait terminé son travail) ; de telles structures de données ne devraient pas vraiment être appelées "sans verrou". Un producteur qui se bloque n'empêchera pas les autres producteurs de progresser, mais peut bloquer arbitrairement les consommateurs.

Answer 4

Les algorithmes sans verrouillage peuvent absolument être plus rapides que leur homologue bloquant. Mais bien sûr, l'inverse est également vrai. En supposant que l'implémentation soit plus performante que son homologue bloquant, le seul facteur limitant est la contention.

Prenez les deux classes Java, ConcurrentLinkedQueue et LinkedBlockingQueue. Dans des conditions réelles de contention modérée, la CLQ surpasse la LBQ dans une large mesure. En cas de forte contention, l'utilisation de la suspension des threads permettra à la LBQ d'obtenir de meilleures performances.

Je ne suis pas d'accord avec l'utilisateur237815. Le mot-clé synchronisé ne nécessite pas autant de surcharge qu'auparavant, mais par rapport à un algorithme sans verrou, il a une bonne quantité de surcharge associée à lui par rapport à un CAS unique.

Answer 5

En Java, du moins, le verrouillage en lui-même peut être très rapide. Le mot-clé synchronized n'ajoute pas beaucoup de frais généraux. Vous pouvez l'évaluer vous-même en appelant simplement une méthode synchronisée dans une boucle.

Le verrouillage ne devient lent que lorsqu'il y a de la contention, et que le processus qui est verrouillé n'est pas instantané.