Collections simultanées en 10 minutes

^{Photo de Robert V. Ruggiero}

Le sujet n'est pas nouveau. Mais en posant la question «que sont les collections simultanées et quand les utiliser?» lors d'une interview ou d'une révision de code, j'obtiens presque toujours une réponse composée d'une phrase: «ils nous protègent complètement des conditions de course» (ce qui est impossible même en théorie). Ou: «c'est comme des collections ordinaires, mais tout à l'intérieur est sur des serrures», ce qui ne correspond pas non plus tout à fait à la réalité.

Le but de cet article est de faire ressortir le sujet en 10 minutes. Il sera utile pour vous familiariser rapidement avec certaines subtilités. Ou pour vous rafraîchir la mémoire avant l'entretien.

Tout d'abord, nous allons jeter un coup d'œil au contenu de l'espace de noms System.Collections.Concurrent . Ensuite, nous discutons des principales différences entre les collections simultanées et classiques, notons quelques points non évidents. En conclusion, nous discutons des pièges possibles et des types de collections qui valent la peine d'être utilisés.

Contenu de System.Collections.Concurrent

Intellisense vous en dit un peu:



Voyons brièvement le but de chaque classe.

ConcurrentDictionary : collection polyvalente sans fil applicable à un large éventail de scénarios.

ConcurrentBag, ConcurrentStack, ConcurrentQueue : collections à usage spécial. La «spécialité» comprend les points suivants:

• Manque d'API pour accéder à un élément arbitraire
• La pile et la file d'attente (comme nous le savons tous) ont un ordre donné d'ajout et d'extraction d'éléments
• ConcurrentBag pour chaque thread conserve sa propre collection pour ajouter des éléments. Lors de la récupération, il «vole» les éléments d'un flux voisin si la collection est vide pour le flux actuel

IProducerConsumerCollection - contrat utilisé par la classe BlockingCollection (voir ci-dessous). Implémenté par les collections ConcurrentStack , ConcurrentQueue et ConcurrentBag .

BlockingCollection - utilisé dans les scénarios où certains flux remplissent une collection, tandis que d'autres en extraient des éléments. Un exemple typique est une file d'attente de tâches réapprovisionnée. Si la collection est vide au moment de la demande de l'élément suivant, alors le lecteur passe à l'état d'attente du nouvel élément (polling). En appelant la méthode CompleteAdding () , nous pouvons indiquer que la collection ne sera plus réapprovisionnée, puis lors de la lecture, l'interrogation ne sera pas effectuée. Vous pouvez vérifier l'état de la collection à l'aide des propriétés IsAddingCompleted ( true si les données ne seront plus ajoutées) et IsCompleted ( true si les données ne seront plus ajoutées et la collection est vide).

Partitioner, OrderablePartitioner, EnumerablePartitionerOptions - constructions de base pour implémenter la segmentation des collections . Utilisé par la méthode Parallel.ForEach pour spécifier comment répartir les éléments entre les threads de traitement.

Plus loin dans l'article, nous nous concentrerons sur les collections: ConcurrentDictionary et ConcurrentBag / Stack / Queue .

Différences entre les collections simultanées et classiques

Protection de l'état interne

Les collections classiques sont conçues avec des performances maximales à l'esprit, de sorte que leurs méthodes d'instance ne garantissent pas la sécurité des threads.

Par exemple, jetez un œil au code source de la méthode Dictionary.Add .
Nous pouvons voir les lignes suivantes (le code est simplifié pour plus de lisibilité):

if (this._buckets == null) { int prime = HashHelpers.GetPrime(capacity); this._buckets = new int[prime]; this._entries = new Dictionary<TKey, TValue>.Entry[prime]; } 

Comme nous pouvons le voir, l'état interne du dictionnaire n'est pas protégé. Lors de l'ajout d'éléments à partir de plusieurs threads, le scénario suivant est possible:

1. Thread 1 appelé Add , l'exécution s'est arrêtée immédiatement après avoir entré la condition if
2. Le thread 2 appelé Ajouter , a initialisé la collection, a ajouté l'élément
3. Le flux 1 est retourné au travail, a réinitialisé la collection, détruisant ainsi les données ajoutées par le flux 2.

Autrement dit, les collections classiques ne conviennent pas pour l'enregistrement à partir de plusieurs flux.

L'API tolère l'état actuel de la collection.

Comme nous le savons, les clés en double ne peuvent pas être ajoutées au dictionnaire . Si nous appelons deux fois Add avec la même clé, le deuxième appel lèvera une ArgumentException .

Cette protection est utile dans les scénarios à thread unique. Mais avec le multithreading, nous ne pouvons pas être sûrs de l'état actuel de la collection. Naturellement, les vérifications comme celles-ci ne nous épargnent que lorsque nous nous enveloppons constamment dans une serrure:

 if (!dictionary.ContainsKey(key)) { dictionary.Add(key, “Hello”); } 

L'API basée sur les exceptions est une mauvaise option et ne permettra pas un comportement stable et prévisible dans les scénarios multithreads. Au lieu de cela, vous avez besoin d'une API qui ne fait pas d'hypothèses sur l'état actuel de la collection, ne lève pas d'exceptions et laisse à l'appelant une décision sur l'admissibilité d'un état particulier.

Dans les collections simultanées, les API sont construites sur le modèle TryXXX . Au lieu des méthodes Add , Get et Remove habituelles , nous utilisons les méthodes TryAdd , TryGetValue et TryRemove . Et, si ces méthodes retournent fausses , alors nous décidons s'il s'agit d'une situation exceptionnelle ou non.

Il convient de noter que les collections classiques disposent désormais également de méthodes tolérantes à l'état. Mais dans les collections classiques, une telle API est un ajout intéressant, et dans les collections simultanées, c'est un must.

API minimisant les conditions de course

Considérez l'opération de mise à jour d'élément la plus simple:

 dictionary[key] += 1; 

Pour toute sa simplicité, le code effectue trois actions: il obtient la valeur de la collection, ajoute 1, écrit la nouvelle valeur. Dans une exécution multithread, il est possible que le code ait récupéré une valeur, effectué un incrément, puis effacé en toute sécurité la valeur qui a été écrite par un autre thread pendant que l'incrément était en cours d'exécution.

Pour résoudre ces problèmes, l'API des collections simultanées contient un certain nombre de méthodes d'assistance. Par exemple, la méthode TryUpdate , qui prend trois paramètres: la clé, la nouvelle valeur et la valeur actuelle attendue. Si la valeur de la collection ne correspond pas à ce qui était attendu, la mise à jour ne sera pas effectuée et la méthode renverra false .

Prenons un autre exemple. Littéralement, chaque ligne du code suivant (y compris Console.WriteLine ) peut provoquer des problèmes avec l'exécution multithread:

 if (dictionary.ContainsKey(key)) { dictionary[key] += 1; } else { dictionary.Add(key, 1); } Console.WriteLine(dictionary[key]); 

Ajouter ou mettre à jour une valeur, puis effectuer une opération avec le résultat, est une tâche assez typique. Par conséquent, le dictionnaire simultané a la méthode AddOrUpdate , qui effectue une séquence d'actions en un seul appel et est thread-safe:

 var result = dictionary.AddOrUpdate(key, 1, (itemKey, itemValue) => itemValue + 1); Console.WriteLine(result); 

Il y a un point à connaître.

L'implémentation de la méthode AddOrUpdate appelle la méthode TryUpdate décrite ci-dessus et lui transmet la valeur actuelle de la collection. Si la mise à jour a échoué (le thread voisin a déjà modifié la valeur), la tentative est répétée et le délégué de mise à jour transmis est appelé à nouveau avec la valeur actuelle mise à jour. Autrement dit, le délégué de mise à jour peut être appelé plusieurs fois , il ne doit donc pas contenir d'effets secondaires.

Verrouillez les algorithmes et les verrous granulaires

Microsoft a fait un excellent travail sur les performances des collections simultanées et n'a pas simplement encapsulé toutes les opérations avec des verrous. En étudiant la source, vous pouvez voir de nombreux exemples d'utilisation de verrous granulaires, l'utilisation d'algorithmes compétents au lieu de verrous, ainsi que l'utilisation d'instructions spéciales et de primitives de synchronisation plus «légères» que Monitor .

Ce que les collections simultanées ne donnent pas

D'après les exemples ci-dessus, il est évident que les collections simultanées n'offrent pas une protection complète contre les conditions de concurrence, et nous devons concevoir notre code en conséquence. Mais ce n’est pas tout, il y a deux ou trois points à connaître.

Polymorphisme avec des collections classiques

Les collections simultanées, comme les classiques, implémentent les interfaces IDictionary , ICollection et IEnumerable . Mais une partie de l'API de ces interfaces ne peut pas être thread-safe par définition. Par exemple, la méthode Add , dont nous avons discuté ci-dessus.

Les collections simultanées implémentent de tels contrats sans sécurité de thread. Et pour «cacher» une API non sécurisée, ils utilisent une implémentation explicite des interfaces. Cela vaut la peine de se rappeler lorsque nous transmettons des collections simultanées à des méthodes qui prennent en entrée, par exemple, ICollection.

De plus, les collections simultanées ne sont pas conformes au principe de substitution Liskov par rapport aux collections classiques.

Par exemple, le contenu d'une collection classique ne peut pas être modifié pendant l' itération , le code suivant lèvera une InvalidOperationException pour la classe List :

 foreach (var element in list) { list.Remove(element); } 

Si nous parlons de collections simultanées, la modification au moment de l'énumération ne conduit pas à une exception, de sorte que nous pouvons effectuer la lecture et l'écriture simultanées à partir de différents flux.

De plus, les collections simultanées implémentent différemment la possibilité de modification pendant l'énumération. ConcurrentDictionary n'effectue simplement aucune vérification et ne garantit pas le résultat de l'itération, et ConcurrentStack / Queue / Bag se verrouille et crée une copie de l'état actuel, à travers lequel itérer.

Problèmes de performances possibles

Nous avons mentionné ci-dessus que ConcurrentBag peut «voler» des éléments des threads voisins. Cela peut entraîner des problèmes de performances si vous écrivez et lisez le ConcurrentBag à partir de différents threads.

En outre, les collections simultanées imposent des verrous complets lors de l'interrogation de l'état de la collection entière ( Count , IsEmpty , GetEnumerator , ToArray , etc.) et sont donc considérablement plus lentes que leurs homologues classiques.

Conclusion: l'utilisation de collections simultanées ne vaut que si elles sont vraiment nécessaires, car ce choix n'est pas «gratuit».

Quand quels types de collections utiliser

• Scripts mono-thread: seules les collections classiques avec les meilleures performances.
• Enregistrement à partir de plusieurs flux: uniquement des collections simultanées qui protègent l'état interne et disposent d'une API appropriée pour un enregistrement compétitif.
• Lecture à partir de plusieurs threads: aucune recommandation définitive. Les collections simultanées peuvent créer des problèmes de performances avec des demandes d'état intensives pour l'ensemble de la collection. Cependant, pour les collections classiques, Microsoft ne garantit pas les performances, même pour les opérations de lecture. Par exemple, une implémentation interne d'une collection peut avoir des propriétés paresseuses qui sont lancées lors de la lecture de données et, par conséquent, il est possible de détruire l'état interne lors de la lecture à partir de plusieurs threads. Une bonne option moyenne consiste à utiliser des collections immuables .
• Et la lecture et l'écriture à partir de plusieurs threads: des collections uniquement simultanées, implémentant à la fois la protection de l'état et une API sécurisée.

Conclusions

Dans cet article, nous avons brièvement étudié les collections simultanées, quand les utiliser et quelles sont leurs spécificités. Bien sûr, l'article n'épuise pas le sujet, et avec un travail sérieux avec des collections multithread, vous devriez creuser plus profondément. La façon la plus simple de le faire est de regarder le code source des collections utilisées. C'est informatif et pas du tout compliqué, le code est très, très lisible.