Self-updating collection concurrency issues

Question

I am trying to build a self-updating collection. Each item in the collection has a position (x,y). When the position is changed, an event is fired, and the collection will relocate the item.

Internally the collection is using a “jagged dictionary”. The outer dictionary uses the x-coordinate a key, while the nested dictionary uses the y-coordinate a key. The nested dictionary then has a list of items as value.

The collection also maintains a dictionary to store the items position as stored in the nested dictionaries – item to stored location lookup.

I am having some trouble making the collection thread safe, which I really need.

Source code for the 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);

    }
}

I have written a simple unit test to check for concurrency issues:

        [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);
    }

The actual stored position varies every time I run the test. I appreciate any feedback you may have.

Answer 1

You could potentially maintain a list of locks per X-coordinate in order to improve concurrency, otherwise you won't see much of a gain in performance.

Alternately, you could switch to a Quad-Tree or some other spatial indexing system in order to minimize the perturbation of the data structure as items are moving. With a Quad-Tree you could minimize the concurrency issues by holding independent locks at individual tree levels rather than data structure wide.

Your data structure makes it very expensive to track moving objects as it has to update itself almost constantly. Using a "bucketed" approach (if you had bounds to your X/Y coordinates) you could limit updates to only when an item changed buckets.

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();
    }
}