"ConcurrentDictionary" en 5 min

A partir du framework 4.0, la structure de données "ConcurrentDictionary" permet de stocker des objets rangés par clé tout en autorisant des accès provenant de "threads" multiples sans se préoccuper des problématiques de synchronisation.

Son utilisation est très similaire à celle du dictionaire mise à part qu’elle possède des méthodes pour guider l’implémentation et s’affranchir des problématiques d’accès concurrent.

Le "ConcurrentDictionary" permet d’échapper à la majorité des erreurs lors de l’implémentation de mécanismes de synchronisation, toutefois il est nécessaire d’observer quelques précautions pour conserver un niveau de performance comparable à celui d’une structure de données non "thread-safe".

Le ConcurrentDictionary<TKey, TValue> se trouve dans le namespace System.Collections.Concurrent: https://msdn.microsoft.com/fr-fr/library/dd287191%28v=vs.110%29.aspx.

A partir du framework 4.6

A partir du framework 4.6, ConcurrentDictionary<TKey, TValue> satisfait les interfaces IReadOnlyCollection<KeyValuePair<TKey, TValue>> et IReadOnlyDictionary<TKey, TValue>. Il peut être très intéressant d’utiliser ces interfaces dans des signatures de fonctions pour imposer l’utilisation du "ConcurrentDictionary" en lecture seule, sachant que les accès en lecture d’une "ConcurrentDictionary" sont bien plus performants que les accès en écriture et sont sans "lock".

Le "Dictionary<TKey, TValue>" autorise les accès concurrents

Dans certaines conditions, il n’est pas toujours nécessaire d’utiliser une structure entièrement "thread-safe".
Comme indiqué sur MSDN:

"A Dictionary<TKey, TValue> can support multiple readers concurrently, 
  as long as the collection is not modified."

Ainsi le Dictionary<TKey, TValue> classique autorise les accès multiples et concurents en lecture. Dans ce cas, il n’est pas nécessaire d’utiliser une structure plus complexe ou d’implémenter un mécanisme de synchronisation.

En revanche, les accès en écriture et les énumérations doivent être protégées contre les accès concurrents.
Le gros intérêt du dictionaire par rapport à une autre structure est la performance puisque l’accès en lecture d’un dictionaire est très rapide (pour plus de détails: Is It Faster to Preallocate Dictionary Sizes?).

Pour la lecture, il est préférable d’utiliser TryGetValue():

var simpleDictionary = new Dictionary<int, string>
{
  { 1, "first value" },
  { 2, "secund value" },
  { 3, "third value" }
};

string secundValue;
if (simpleDictionary.TryGetValue(2, out secundValue))
{
  ...
}

Plutôt que:

if (simpleDictionary.ContainsKey(2))
{
  string secundValue = simpleDictionary[2];
}

L’implémentation avec ContainsKey() peut mener à des erreurs si la valeur correspondant à la clé "2" est supprimée entre l’appel à ContainsKey() et simpleDictionary[2].

Pour protéger les accès en écriture et les énumérations, on peut utiliser un "lock" classique:

private readonly object dictionaryLock = new object();

private void AddToDictionary(int key, string newValue)
{
  lock (this.dictionaryLock)
  {
    this.simpleDictionary[key] = newValue;
  }
}

private void EnumerateDictionary()
{
  lock (this.dictionaryLock)
  {
    foreach (var kvp in this.simpleDictionary)
    {
      ...
    }
  }
}

Le "ConcurrentDictionary" ne protège pas contre des accès concurrents à une même valeur

Le "ConcurrentDictionary" fournit une solution pour accéder aux valeurs de façon concurrente. Il n’y a pas de précautions particulières à prendre pour effectuer une énumération ou une écriture dans la structure. En revanche, les objets correspondant aux valeurs du dictionaire ne sont pas protégés. Il faut donc prévoir des mécanismes de synchronisation si plusieurs "threads" sont susceptibles de modifier les propriétés des valeurs du dictionaire en même temps.

Par exemple, si on considère:

var values = new ConcurrentDictionary<int, List<string>>
{
  { 1, new List<string>{ "first", "secund", "third", "fourth", "fifth" }},
};

Si on exécute le code:

Task t1 = Task.Run(() => {
  for (int i = 0; i < 100; i++)
  {
    values[1].Add(i.ToString());
  }
});

Task t2 = Task.Run(() => {
  foreach (var value in values[1])
  {
    Console.WriteLine(value);
  }
});

On aura une erreur du type "Collection was modified; enumeration operation may not execute" car la liste est énumérée au moment où on y ajoute des éléments. Le "ConcurrentDictionary" n’a donc pas protégé la valeur des accès concurrents.

Utiliser des "struct"

Si les valeurs du "ConcurrentDictionary" doivent être utilisées de façon concurrente, une solution peut être d’utiliser des objets de type "struct". Sachant que les "struct" sont des types par valeur, chaque utilisation d’une "struct" sera une valeur copiée à partir de sa valeur d’origine. Les "threads" accédant à cette valeur en auront une copie spécifique et il ne sera plus nécessaire d’implémenter un mécanisme de synchronisation.

Par exemple, si on reprends l’exemple précédent:
On déclare la "struct":

public struct StoredList
{
  public List<string> Values = new List<string>();
  
  public Point(IEnumerable<string> newValues) 
  {
    this.Values.AddRange(newValues);
  }
}

Le dictionaire devient:

var firstValueList = new List<string>{ "first", "secund", "third", "fourth", "fifth" };
var values = new ConcurrentDictionary<int, StoredList>
{
  { 1, new StoredList(firstValueList) },
};

On peut ensuite utiliser la valeur en faisant:

Task t1 = Task.Run(() => {
  var storedList = values[1]; // On obtient une copie de la valeur stockée dans le dictionaire
  for (int i = 0; i < 100; i++)
  {
    storedList.Values.Add(i.ToString());
  }
  values[1] = storedList; // On recopie la valeur modifiée
});

Task t2 = Task.Run(() => {
  // La liste énumérée provient d'une copie de la valeur du dictionaire.
  foreach (var value in values[1].Values) 
  {
    Console.WriteLine(value);
  }
});

Lecture et écriture des valeurs d’un "ConcurrentDictionary"

On peut lire et écrire des valeurs dans un "ConcurrentDictionary" comme pour un dictionaire classique:

var values = new ConcurrentDictionary<int, string>();

Ecriture avec:

values[1] = "new value";

Lecture avec:

string newValue = values[1];

D’autres méthodes permettent une implémentation plus flexible:

GetOrAdd(TKey, Func<TKey, TValue>)

Permet de lire une valeur si la clé existe dans le ConcurrentDictionary ou d’ajouter une pair clé/valeur si elle n’existe pas.

La surcharge ConcurrentDictionary<TKey, TValue>.GetOrAdd(TKey, Func<TKey, TValue>) permet d’implémenter une logique dans le cas où la valeur doit être ajoutée en exécutant l’expression lambda Func<TKey, TValue>.

Par exemple:

public TValue GetOrAddValueWithSimpleLock<TKey, TValue>(
  ConcurrentDictionary<TKey, TValue> dictionary, TKey key)
{
  return dictionary.GetOrAdd(key, (k) => CreateValue<TKey, TValue>(k));
}

public TValue CreateValue<TKey, TValue>(TKey key)
{
  ...
}
Quelques remarques importantes:

1. Si plusieurs "threads" exécutent cette méthode avec la même clé et qu’elle n’existe pas encore dans le ConcurrentDictionary, l’expression lambda Func<TKey, TValue> peut être exécutée plusieurs fois mais tous les appels n’aboutiront pas à l’ajout de la pair clé/valeur.
Ainsi, seul le premier "thread" exécutant l’expression lambda ajoutera effectivement la pair clé/valeur, les "threads" suivant ne feront que récupérer la valeur. Toutefois, suivant la simultanéïté des exécutions l’expression lambda peut avoir été exécutée plusieurs fois.
Plus de détails sur MSDN.

2. L’ajout de valeurs dans le ConcurrentDictionary est plus lent par rapport l’utilisation d’un Dictionary<TKey, TValue> avec un "lock" simple. Les performances du ConcurrentDictionary<TKey, TValue> sont toutefois bonnes pour les accès en lecture.

Il faut tester pour comparer les différences entre "ConcurrentDictionary" et "Dictionary + Lock"

Il convient de tester les performances du ConcurrentDictionary<TKey, TValue> par rapport au Dictionary<TKey, TValue> + "lock" car la différence peut être déterminante.

En effet dans le cas où on utilise ConcurrentDictionary<TKey, TValue>.GetOrAdd(TKey, Func<TKey, TValue>) et si plusieurs "threads" exécutent cette méthode simultanément et que la clé n’existe pas déjà, l’expression lambda sera exécutée simultanément et un thread ne sera pas bloqué par rapport aux autres. Une seule exécution de l’expression lambda servira réellement à l’ajout de la pair clé/valeur, toutefois, le CPU aura été occupé à exécuter plusieurs fois l’expression lambda pour les autres "threads" pour rien.

Une implémentation judicieuse du "lock" permet d’éviter d’exécuter du code inutilement, par exemple:

public TValue GetOrAddValueWithSimpleLock<TKey, TValue>(
  ConcurrentDictionary<TKey, TValue> dictionary, TKey key)
{
  TValue result;
  lock(dictionary)
  {
    if (!dictionary.TryGetValue(key, out result))
    {
      result = CreateValue<TKey, TValue>(key);
      dictionary.Add(key, result);
    }
  }

  return result;
}

Dans le cas où plusieurs "threads" exécutent cette fonction pour une même clé, les "threads" suivant le premier "thread" seront bloqués lors de l’accès du premier "thread" à la section critique du "lock". Toutefois sachant que le premier "thread" aura rajouté la valeur dans le dictionaire, les threads suivant ne vont pas exécuter inutilement CreateValue(key).

AddOrUpdate(TKey, Func<TKey, TValue>)

Cette méthode permet de rajouter une paire clé/valeur si la clé n’existe pas ou de mettre à jour la valeur si la clé existe dans le "ConcurrentDictionary".

Il existe 2 surcharges:
TValue AddOrUpdate(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory): addValue est utilisé pour rajouter la valeur si la clé n’existe pas. L’expression lambda updateValueFactory permet de mettre à jour la valeur si la clé est présente.
TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory): addValueFactory est exécuté pour rajouter la valeur si la clé n’existe pas. updateValueFactory permet de mettre à jour la valeur si la clé est présente.

Par exemple, on peut utiliser la 2e surcharge de la façon suivante:

var simpleDictionary = new Dictionary<int, string>
{
  { 1, "first value" },
  { 2, "secund value" },
  { 3, "third value" }
};

simpleDictionary.AddOrUpdate(2, 
(key) => "new secund value",
(key, currentValue) => 
{
  if (currentValue.Equals("secund value"))
    return "secund value updated";
  else
    return currentValue;
});
Remarques importantes:

Les mêmes remarques concernant GetOrAdd(TKey, Func<TKey, TValue>) s’appliquent à AddOrUpdate (voir plus haut).

Performances

Les performances sont assez différentes suivant les membres et méthodes utilisés:

Membres utilisés Opérations Performant ? Remarques
TryGetValue() Lecture Oui Pas de "lock" pour les accès en lecture, seulement des "memory barriers" sont utilisées.
GetOrAdd(), AddOrUpdate() Ecriture Non Plusieurs objets de "lock" sont utilisés lors des accès en écriture.
Les performances sont différentes entre le framework 4.0 et 4.5.
Un "lock" est assigné à chaque objet suivant sa clé de hachage ("Hash code").
GetEnumerator() Enumeration Oui Pas de "lock" toutefois l’énumération ne correspond pas au contenu du "ConcurrentDictionary" à un moment donné.
Count (et non Count()) Nombre d’objets Non Cette méthode est particulièrement pas performante car elle nécessite l’acquisition de tous les "locks" à la fois.
Utiliser la méthode via LinQ en faisant dictionary.Skip(0).Count() n’utilise pas de "lock".
Keys, Values Obtenir les clés (respectivement les valeurs) Non Fait l’acquisition de tous les "locks" à la fois.Utiliser la méthode LinQ en faisant dictionary.Select(kvp => kvp.Key) (respectivement dictionary.Select(kvp => kvp.Value)) n’utilise pas de "lock".
ToArray() Obtenir un tableau de KeyValuePair Non Tous les "locks" sont acquis.
CopyTo() Copie les KeyValuePair du dictionaire dans un autre
Clear() Supprimer toutes les valeurs

Améliorations des performances à partir du framework 4.5

Lorsque le type de la valeur d’un "ConcurrentDictionary" est un type large (comme System.Guid par exemple), les écritures et les lectures en mémoire par le CLR ne sont pas atomiques. Ainsi, si l’écriture n’est pas complète et si on effectue une lecture en mémoire au même moment, la valeur lue pourrait être un "mélange" entre la nouvelle valeur et l’ancienne valeur.
Pour éviter ces problèmes, le "ConcurrentDictionary" en .NET 4.0, entoure toutes les valeurs dans un objet noeud. Lorsqu’on effectue une mise à jour de la valeur, un nouvel objet noeud est alloué par le "ConcurrentDictionary".
A partir du framework 4.5, le ConcurrentDictionary évite d’allouer un nouvel objet pour les types primitifs simples comme les Int32, byte etc… Pour ces types, les performances sont ainsi améliorées puisqu’il n’y a pas de réallocation en cas de mis à jour.

La 2e amélioration concerne les "locks". En .NET 4.0, le "ConcurrentDictionary" crée 4 fois le nombre de processeurs d’objets "lock". A partir du framework 4.5, ce nombre n’est pas fixe et augmente en fonction du nombre d’éléments dans le dictionaire. Ainsi plus il y a de "locks" et moins il y a de chances que ces "locks" soient acquis lorsqu’on essaie d’accèder à des valeurs de façons concurrentes.

TODO: parler des changements de contexte entre threads.

Pour résumer

1. Les écritures dans le "ConcurrentDictionary" sont lents par rapport à un "Dictionary + lock" mais ils se font en parallèle.
2. Les accès en lecture sont très rapides car non bloquants et sans "lock".
3. L’utilisation du "ConcurrentDictionary" permet d’éviter des erreurs d’implémentation dans les mécanismes de synchronisation entre "threads".
4. Les propriétés Count, Keys, Values et les méthodes ToArray(), CopyTo() et Clear() sont très peu performantes car elle nécessite l’acquisition de tous les "locks".
5. Les performances sont meilleures à partir du framework 4.5.
6. A partir du framework 4.6, "ConcurrentDictionary" satisfait les interfaces "IReadOnlyCollection" et "IReadOnlyDictionary".

Références:

Leave a Reply