Pourquoi ConcurrentBag est-il si lent dans .Net (4.0)? Est-ce que je le fais mal?

Avant de commencer un projet, j’ai écrit un test simple pour comparer les performances de ConcurrentBag à partir de (System.Collections.Concurrent) relatives au locking et aux listes. Je suis extrêmement surpris que ConcurrentBag soit 10 fois plus lent que le locking avec une simple liste. D’après ce que j’ai compris, le ConcurrentBag fonctionne mieux lorsque le lecteur et le rédacteur sont du même fil. Cependant, je ne pensais pas que ses performances seraient tellement pires que les serrures traditionnelles.

J’ai effectué un test avec deux parallèles pour les boucles d’écriture et de lecture dans une liste / un sac. Cependant, l’écriture par elle-même montre une énorme différence:

private static void ConcurrentBagTest() { int collSize = 10000000; Stopwatch stopWatch = new Stopwatch(); ConcurrentBag bag1 = new ConcurrentBag(); stopWatch.Start(); Parallel.For(0, collSize, delegate(int i) { bag1.Add(i); }); stopWatch.Stop(); Console.WriteLine("Elapsed Time = {0}", stopWatch.Elapsed.TotalSeconds); } 

Sur ma boîte, cela prend entre 3 et 4 secondes, contre 0,5 à 0,9 secondes pour ce code:

  private static void LockCollTest() { int collSize = 10000000; object list1_lock=new object(); List lst1 = new List(collSize); Stopwatch stopWatch = new Stopwatch(); stopWatch.Start(); Parallel.For(0, collSize, delegate(int i) { lock(list1_lock) { lst1.Add(i); } }); stopWatch.Stop(); Console.WriteLine("Elapsed = {0}", stopWatch.Elapsed.TotalSeconds); } 

Comme je l’ai mentionné, les lectures et écritures simultanées ne facilitent pas le test simultané. Est-ce que je fais quelque chose de mal ou est-ce que cette structure de données est vraiment lente?

[EDIT] – J’ai supprimé les tâches car je n’en ai pas besoin ici (le code complet comportait une autre tâche en cours de lecture)

[EDIT] Merci beaucoup pour les réponses. J’ai du mal à choisir “la bonne réponse”, car cela semble être un mélange de quelques réponses.

Comme Michael Goldshteyn l’a souligné, la vitesse dépend vraiment des données. Darin a fait remarquer qu’il devrait y avoir plus de conflits pour que ConcurrentBag soit plus rapide, et Parallel.For ne démarre pas nécessairement le même nombre de threads. Un point à retenir est de ne rien faire à l’ intérieur d’une écluse. Dans le cas ci-dessus, je ne me vois pas faire quoi que ce soit à l’intérieur du verrou, sauf peut-être atsortingbuer la valeur à une variable temporaire.

En outre, sixlettervariables a souligné que le nombre de threads en cours d’exécution peut également affecter les résultats, même si j’ai essayé d’exécuter le test d’origine dans l’ordre inverse et que ConcurrentBag était encore plus lent.

J’ai effectué quelques tests avec le démarrage de 15 tâches et les résultats dépendaient notamment de la taille de la collection. Cependant, ConcurrentBag a réalisé presque aussi bien ou mieux que de verrouiller une liste, pour un million d’insertions au maximum. Au-delà de 1 million, le locking semblait parfois beaucoup plus rapide, mais je n’aurai probablement jamais de plus grande infrastructure de données pour mon projet. Voici le code que j’ai couru:

  int collSize = 1000000; object list1_lock=new object(); List lst1 = new List(); ConcurrentBag concBag = new ConcurrentBag(); int numTasks = 15; int i = 0; Stopwatch sWatch = new Stopwatch(); sWatch.Start(); //First, try locks Task.WaitAll(Enumerable.Range(1, numTasks) .Select(x => Task.Factory.StartNew(() => { for (i = 0; i  Task.Factory.StartNew(() => { for (i = 0; i < collSize / numTasks; i++) { concBag.Add(x); } })).ToArray()); sWatch.Stop(); Console.WriteLine("Conc Bag test. Elapsed = {0}", sWatch.Elapsed.TotalSeconds); 

Permettez-moi de vous poser la question suivante: dans quelle mesure est-il réaliste d’avoir une application qui ne cesse d’append à une collection et de ne jamais la lire ? A quoi sert une telle collection? (Ce n’est pas une question purement rhétorique. J’imagine qu’il existe des utilisations où, par exemple, vous lisez uniquement la collection à la fermeture (pour la journalisation) ou à la demande de l’utilisateur. Je pense que ces scénarios sont plutôt rares.)

C’est ce que simule votre code. La List.Add appels List.Add va être List.Add rapide dans tous les cas, sauf dans les cas occasionnels où la liste doit redimensionner son tableau interne; mais cela est atténué par tous les autres ajouts qui arrivent assez rapidement. Il est donc peu probable que vous soyez confronté à un certain nombre de querelles dans ce contexte, en particulier les tests sur un PC personnel avec, par exemple, même 8 cœurs (comme vous l’avez indiqué dans un commentaire quelque part). Vous pourriez peut-être voir plus de conflits sur quelque chose comme une machine à 24 cœurs, où de nombreux cœurs peuvent essayer d’append littéralement à la liste.

La contention est beaucoup plus susceptible de se glisser là où vous lisez de votre collection, en particulier. dans les boucles foreach (ou les requêtes LINQ qui se foreach boucles sous le capot) qui nécessitent de verrouiller l’ensemble de l’opération afin de ne pas modifier votre collection en l’itérant.

Si vous pouvez reproduire ce scénario de manière réaliste, je pense que vous verrez que ConcurrentBag beaucoup plus efficace que votre test actuel.


Mise à jour : Voici un programme que j’ai écrit pour comparer ces collections dans le scénario que j’ai décrit ci-dessus (plusieurs auteurs, plusieurs lecteurs). En exécutant 25 essais avec une taille de collection de 10000 et 8 threads de lecteur, j’ai obtenu les résultats suivants:

 Pris 529.0095 ms pour append 10000 éléments à une liste  avec 8 threads de lecteur.
 A pris 39.5237 ms pour append 10000 éléments à un ConcurrentBag  avec 8 threads de lecteur.
 Pris 309.4475 ms pour append 10000 éléments à une liste  avec 8 threads de lecteur.
 A pris 81.1967 ms pour append 10000 éléments à un ConcurrentBag  avec 8 threads de lecteur.
 A pris 228,7669 ms pour append 10000 éléments à une liste  avec 8 threads de lecteur.
 Pris 164.8376 ms pour append 10000 éléments à un ConcurrentBag  avec 8 threads de lecteur.
 [...]
 Temps de liste moyen: 176.072456 ms.
 Temps moyen de sac: 59.603656 ms.

Donc, cela dépend clairement de ce que vous faites avec ces collections.

Il semble y avoir un bogue dans le .NET Framework 4 corrigé par Microsoft dans la version 4.5, il semble qu’ils ne s’attendaient pas à ce que ConcurrentBag soit beaucoup utilisé.

Voir le post Ayende suivant pour plus d’informations

http://ayende.com/blog/156097/the-high-cost-of-concurrentbag-in-net-4-0

En réponse générale:

  • Les collections simultanées qui utilisent le locking peuvent être très rapides s’il y a peu ou pas de conflit pour leurs données (par exemple, les verrous). Cela est dû au fait que de telles classes de collection sont souvent construites en utilisant des primitives de locking très peu coûteuses, surtout lorsqu’elles ne sont pas soumises à des contraintes.
  • Les collections sans locking peuvent être plus lentes, en raison des astuces utilisées pour éviter les lockings et des autres goulots d’étranglement tels que le faux partage, la complexité nécessaire pour mettre en œuvre leur nature sans verrou, ce qui conduit à des erreurs de cache, etc.

En résumé, la décision de savoir quelle voie est la plus rapide dépend fortement des structures de données utilisées et de la quantité de conflits entre les problèmes (par exemple, lecteurs numériques / auteurs dans un arrangement de type partagé / exclusif).

Votre exemple particulier est très controversé, alors je dois dire que je suis surpris par ce comportement. D’un autre côté, la quantité de travail effectuée pendant que le verrou est maintenu est très petite, alors peut-être qu’il y a peu de conflit pour le verrou lui-même, après tout. Il pourrait également y avoir des lacunes dans l’implémentation de la gestion des access simultanés de ConcurrentBag, ce qui rend votre exemple particulier (avec des insertions fréquentes et aucune lecture) un mauvais exemple d’utilisation.

L’examen du programme à l’aide du visualiseur de contention de MS montre que le coût associé à l’insertion parallèle est beaucoup plus élevé avec ConcurrentBag qu’avec le simple locking sur une List . Une chose que j’ai remarquée, c’est qu’il semble y avoir un coût associé à la rotation des 6 threads (utilisés sur ma machine) pour commencer la première exécution de ConcurrentBag (exécution à froid). 5 ou 6 threads sont alors utilisés avec le code List , qui est plus rapide (run à chaud). L’ajout d’un autre ConcurrentBag après la liste montre que cela prend moins de temps que le premier (exécution à chaud).

D’après ce que je vois dans l’affirmation, beaucoup de temps est consacré à l’implémentation de la mémoire dans l’implémentation ConcurrentBag . La suppression de l’allocation explicite de la taille du code List ralentit, mais pas assez pour faire la différence.

EDIT: il semble que ConcurrentBag conserve en interne une liste par Thread.CurrentThread , se verrouille 2 à 4 fois selon qu’il s’exécute sur un nouveau thread et effectue au moins un Interlocked.Exchange . Comme indiqué dans MSDN: “optimisé pour les scénarios où le même thread produira et consumra des données stockées dans le sac.” C’est l’explication la plus probable de votre baisse de performance par rapport à une liste brute.

Ceci est déjà résolu dans .NET 4.5. Le problème sous-jacent était que ThreadLocal, utilisé par ConcurrentBag, ne prévoyait pas beaucoup d’instances. Cela a été corrigé et peut maintenant fonctionner assez rapidement.

source – Le coût élevé de ConcurrentBag dans .NET 4.0

Comme @ Darin-Dimitrov l’a dit, je soupçonne que votre Parallel.For ne crée pas le même nombre de threads dans chacun des deux résultats. Essayez de créer manuellement des threads N pour vous assurer que vous constatez réellement des conflits de threads dans les deux cas.

Vous avez fondamentalement très peu d’écritures simultanées et pas de conflit ( Parallel.For ne signifie pas nécessairement beaucoup de threads). Essayez de paralléliser les écritures et vous observerez différents résultats:

 class Program { private static object list1_lock = new object(); private const int collSize = 1000; static void Main() { ConcurrentBagTest(); LockCollTest(); } private static void ConcurrentBagTest() { var bag1 = new ConcurrentBag(); var stopWatch = Stopwatch.StartNew(); Task.WaitAll(Enumerable.Range(1, collSize).Select(x => Task.Factory.StartNew(() => { Thread.Sleep(5); bag1.Add(x); })).ToArray()); stopWatch.Stop(); Console.WriteLine("Elapsed Time = {0}", stopWatch.Elapsed.TotalSeconds); } private static void LockCollTest() { var lst1 = new List(collSize); var stopWatch = Stopwatch.StartNew(); Task.WaitAll(Enumerable.Range(1, collSize).Select(x => Task.Factory.StartNew(() => { lock (list1_lock) { Thread.Sleep(5); lst1.Add(x); } })).ToArray()); stopWatch.Stop(); Console.WriteLine("Elapsed = {0}", stopWatch.Elapsed.TotalSeconds); } } 

Je suppose que les verrous ne connaissent pas beaucoup de conflits. Je vous recommande de lire l’article suivant: Théorie et pratique Java: Anatomie d’un microbenchmark défectueux . L’article traite d’un microbenchmark de locking. Comme indiqué dans l’article, il y a beaucoup de choses à prendre en compte dans ce genre de situations.

Il serait intéressant de voir une mise à l’échelle entre les deux.

Deux questions

1) à quelle vitesse se trouve la comparaison entre le sac et la liste, n’oubliez pas de verrouiller la liste

2) à quelle vitesse se trouve le sac vs liste pour la lecture pendant qu’un autre fil écrit

Comme le corps de la boucle est petit, vous pouvez essayer d’utiliser la méthode Create de la classe Partitioner …

qui vous permet de fournir une boucle séquentielle pour le corps du délégué, de sorte que le délégué ne soit appelé qu’une fois par partition, au lieu d’une fois par itération

Comment: accélérer les petites boucles

Il semble que ConcurrentBag est plus lent que les autres collections simultanées.

Je pense que c’est un problème d’implémentation. ANTS Profiler montre qu’il est bloqué à quelques endroits, y compris une copie de tableau.

Utiliser un dictionnaire simultané est des milliers de fois plus rapide.