Самостоятельно обновляемые проблемы параллелизма в коллекции

Question

Я пытаюсь создать самообновляющуюся коллекцию. Каждый элемент в коллекции имеет позицию (x, y). Когда позиция меняется, происходит событие, и коллекция перемещает элемент.

Внутри коллекции используется «зазубренный словарь». Внешний словарь использует x-координату ключа, в то время как вложенный словарь использует y-координату ключа. Вложенный словарь имеет список элементов в качестве значения.

Коллекция также содержит словарь для хранения позиции элементов в том виде, в котором они хранятся во вложенных словарях - поиск элементов в сохраненных местоположениях.

У меня возникли проблемы с безопасностью потока коллекции, который мне действительно нужен.

Исходный код для коллекции:

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

    }
}

Я написал простой модульный тест для проверки проблем параллелизма:

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

Фактическая сохраненная позиция меняется каждый раз, когда я запускаю тест. Я ценю любые ваши отзывы.

Answer 1

Вы можете потенциально поддерживать список блокировок для каждой X-координаты, чтобы улучшить параллелизм, иначе вы не увидите значительного увеличения производительности.

Кроме того, вы можете переключиться на Quad-Tree или какую-либо другую систему пространственной индексации, чтобы минимизировать возмущение структуры данных при перемещении элементов. С помощью Quad-Tree вы можете минимизировать проблемы параллелизма, удерживая независимые блокировки на отдельных уровнях дерева, а не на всей структуре данных.

Ваша структура данных делает очень дорогой отслеживание движущихся объектов, поскольку она должна обновляться практически постоянно. Используя подход «с привязкой» (если у вас были границы координат X / Y), вы можете ограничить обновления только тогда, когда элемент изменил корзины.

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