Comment créer une collection de collection Lockfree

Question

Je dois créer une collection de collections. La collection est appelée par plusieurs threads pour ajouter des éléments et des éléments de recherche. Une fois ajoutés, les éléments ne seront pas supprimés. Actuellement, tout en ajoutant des éléments, je dois prendre un verrou sur l'ensemble de la collection. Y a-t-il un moyen de le contourner pour le rendre verrouillé? Ou y a-t-il une meilleure infrastructure de données ou un modèle que je peux utiliser? Voici une version simplifiée de mon code:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>(); 

void AddUpdateItem(string s, int k, int v) 
{ 
    ConcurrentDictionary<int, int> subDict; 
    if (dict.TryGetValue(s, out subDict)) 
    { 
     subDict[k] = v; 
    } 
    else 
    { 
     lock (dict) 
     { 
      if (dict.TryGetValue(s, out subDict)) 
      { 
       subDict[k] = v; 
      } 
      else 
      { 
       subDict = new ConcurrentDictionary<int, int>(); 
       subDict[k] = v; 
       dict[s] = subDict; 
      } 
     } 
    } 
} 

Answer 1

La méthode ConcurrentDictionary.GetOrAdd est thread-safe (bien que non atomique). Cela garantit que l'objet retourné est le même pour tous les threads. Votre code pourrait être réécrit comme:

void AddUpdateItem(string s, int k, int v) 
{ 
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>()); 
    subDict[k] = v; 
} 

Answer 2

Utilisez-vous des tâches ou threads dans votre code? Dans tous les cas, ConcurrentDictionary est conçu pour être thread-safe. Vous n'avez pas besoin d'utiliser des verrous lorsque vous ajoutez ou supprimez des éléments. Le lien de MSDN How to: Add and Remove Items from a ConcurrentDictionary explique comment l'utiliser.

Answer 3

Vous pouvez créer une table de hachage sans verrou, en utilisant l'immuabilité, mais il est peu probable qu'elle soit efficace en cas de conflit. Fondamentalement, vous avez besoin d'une classe de dictionnaire-contenu qui peut être échangé de manière atomique. Vous créez une copie du contenu actuel, avec la modification effectuée, puis utilisez une primitive de comparaison et d'échange pour l'échanger avec la version existante. Si compare-and-swap échoue, recommencez avec l'étape de copie.

Vous pourriez être en mesure d'échanger de manière atomique juste un seul hachage, ce qui rendrait la contention beaucoup moins commune, et réessayer moins cher. (ConcurrentDictionary utilise déjà cette optimisation, pour réduire les conflits de verrous). Cependant, augmenter le nombre de compartiments nécessitera toujours la méthode décrite ci-dessus.

Jetez un coup d'œil au blog d'Eric Lippert, dans lequel il couvre les structures de données immuables. Il a a nice example of a binary tree, qui devrait vous montrer les techniques nécessaires pour faire une table de hachage sans clé.

Answer 4

Si vous créez spéculativement le sous-dictionnaire, il y a une solution plus simple:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>(); 

void AddUpdateItem(string s, int k, int v) 
{ 
    ConcurrentDictionary<int, int> subDict; 

    while (true) 
    { 
     if (dict.TryGetValue(s, out subDict)) 
     { 
      subDict[ k ] = v; 
      break; 
     } 

     // speculatively create new sub-dictionary 
     subDict = new ConcurrentDictionary<int, int>(); 
     subDict[ k ] = v; 

     // this can only succeed for one thread 
     if (dict.TryAdd(s, subDict)) break; 
    } 
} 

Answer 5

avant d'aller sur la route de la mise en œuvre d'une collection de lockless un coup d'oeil à ReadWriteLock qui résolvent votre problème. Si ce n'est pas le cas (par exemple parce que vous avez des conflits d'écriture importants), il n'y a pas vraiment d'approche unique.

Une technique que j'ai utilisée dans le passé est d'avoir un thread dédié à la gestion de la collection et d'utiliser Interlocked.Exchange pour rassembler de nouveaux objets sur ce thread et une collection immuable. Avec cette approche, vos threads d'écriture sont gérés dans une liste distincte que vous devez verrouiller chaque fois qu'un script est créé ou détruit. Par conséquent, cela ne fonctionne que s'il s'agit d'un événement rare.