Problèmes de simultanéité de la collection à mise à jour automatique

Question

J'essaie de créer une collection à mise à jour automatique. Chaque élément de la collection a une position (x, y). Lorsque la position est modifiée, un événement est déclenché et la collection déplace l'élément.

En interne, la collection utilise un "dictionnaire dentelé". Le dictionnaire externe utilise la clé x, tandis que le dictionnaire imbriqué utilise la clé y. Le dictionnaire imbriqué a alors une liste d'éléments en tant que valeur.

La collection gère également un dictionnaire pour stocker la position des éléments telle qu'elle est stockée dans l'élément de dictionnaires imbriqués dans la recherche d'emplacement stockée.

Je rencontre des problèmes pour sécuriser le thread de collecte, dont j'ai vraiment besoin.

code source de la collection:

public class PositionCollection<TItem, TCoordinate> : ICollection<TItem> 
    where TItem : IPositionable<TCoordinate> 
    where TCoordinate : struct, IConvertible 
{ 
    private readonly object itemsLock = new object(); 
    private readonly Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>> items; 
    private readonly Dictionary<TItem, Vector<TCoordinate>> storedPositionLookup; 

    public PositionCollection() 
    { 
     this.items = new Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>>(); 
     this.storedPositionLookup = new Dictionary<TItem, Vector<TCoordinate>>(); 
    } 

    public void Add(TItem item) 
    { 
     if (item.Position == null) 
     { 
      throw new ArgumentException("Item must have a valid position."); 
     } 

     lock (this.itemsLock) 
     { 
      if (!this.items.ContainsKey(item.Position.X)) 
      { 
       this.items.Add(item.Position.X, new Dictionary<TCoordinate, List<TItem>>()); 
      } 

      Dictionary<TCoordinate, List<TItem>> xRow = this.items[item.Position.X]; 

      if (!xRow.ContainsKey(item.Position.Y)) 
      { 
       xRow.Add(item.Position.Y, new List<TItem>()); 
      } 

      xRow[item.Position.Y].Add(item); 

      if (this.storedPositionLookup.ContainsKey(item)) 
      { 
       this.storedPositionLookup[item] = new Vector<TCoordinate>(item.Position); 
      } 
      else 
      { 
       this.storedPositionLookup.Add(item, new Vector<TCoordinate>(item.Position)); // Store a copy of the original position 
      } 

      item.Position.PropertyChanged += (object sender, PropertyChangedEventArgs eventArgs) => this.UpdatePosition(item, eventArgs.PropertyName); 
     } 
    } 

    private void UpdatePosition(TItem item, string propertyName) 
    { 
     lock (this.itemsLock) 
     { 
      Vector<TCoordinate> storedPosition = this.storedPositionLookup[item]; 
      this.RemoveAt(storedPosition, item); 
      this.storedPositionLookup.Remove(item); 
     } 

     this.Add(item); 

    } 
} 

J'ai écrit un simple test de l'unité pour vérifier les problèmes de concurrence:

 [TestMethod] 
    public void TestThreadedPositionChange() 
    { 
     PositionCollection<Crate, int> collection = new PositionCollection<Crate, int>(); 
     Crate crate = new Crate(new Vector<int>(5, 5)); 
     collection.Add(crate); 

     Parallel.For(0, 100, new Action<int>((i) => crate.Position.X += 1)); 

     Crate same = collection[105, 5].First(); 
     Assert.AreEqual(crate, same); 
    } 

La position réelle stockée varie chaque fois que je lance le test. J'apprécie tout commentaire que vous pourriez avoir.

Answer 1

Vous pourriez potentiellement maintenir une liste de verrous par coordonnée X afin d'améliorer la simultanéité, sinon vous ne verrez pas beaucoup de gain de performance.

Alternativement, vous pouvez passer à un Quad-Tree ou un autre système d'indexation spatiale afin de minimiser la perturbation de la structure de données lorsque les éléments sont en mouvement. Avec un Quad-Tree, vous pouvez minimiser les problèmes de simultanéité en maintenant des verrous indépendants à des niveaux d'arborescence individuels plutôt qu'à une structure de données étendue.

Votre structure de données rend très coûteux le suivi des objets en mouvement car elle doit se mettre à jour presque constamment. En utilisant une approche "seau" (si vous aviez des limites à vos coordonnées X/Y), vous pouvez limiter les mises à jour uniquement lorsqu'un élément a changé de compartiments.

private void UpdatePosition(TItem item) 
{ 
    // each bucket holds some MxN section of the X,Y grid 
    var nextBucket = CalculateBucket(item.Position); 
    if (nextBucket != item.Bucket) 
    { 
     lock (wholeCollectionLock) 
     { 
      this.buckets[nextBucket].Add(item); 
      this.buckets[item.Bucket].Remove(item); 
      item.Bucket = nextBucket; 
     } 
    } 
} 

public IEnumerable<TItem> ItemsAt(TPosition position) 
{ 
    var bucket = CalculateBucket(position); 
    lock (wholeCollectionLock) 
    { 
     // this will be efficient enough for cases where O(n) searches 
     // have small enough n's 
     // needs to be .ToArray for "snapshot" 
     return this.buckets[bucket].Where(xx => xx.Position == position).ToArray(); 
    } 
}