Параллельная модификация элементов double[][] без блокировки

У меня есть зубчатый массив double[][], который может одновременно изменяться несколькими потоками. Я хотел бы сделать его потокобезопасным, но, если возможно, без блокировок. Потоки вполне могут нацеливаться на один и тот же элемент в массиве, поэтому и возникает вся проблема. Я нашел код для атомарного увеличения двойных значений с использованием метода Interlocked.CompareExchange: Почему нет перегрузки Interlocked.Add, которая принимает Doubles в качестве параметров?

Мой вопрос: останется ли он атомарным, если в Interlocked.CompareExchange есть ссылка на зубчатый массив? Ваши идеи очень ценятся.

На примере:

    public class Example
    {
        double[][] items;

        public void AddToItem(int i, int j, double addendum)
        {
            double newCurrentValue = items[i][j];
            double currentValue;
            double newValue;
            SpinWait spin = new SpinWait();

            while (true) {
               currentValue = newCurrentValue;
               newValue = currentValue + addendum;
               // This is the step of which I am uncertain:
               newCurrentValue = Interlocked.CompareExchange(ref items[i][j], newValue, currentValue);
               if (newCurrentValue == currentValue) break;
               spin.SpinOnce();
            }
        }
    }

multithreading arrays c# concurrency interlocked
person tethered.sun    schedule 31.01.2017    source источник
comment
Лично я бы переименовал newCurrentValue в oldValue - это просто сбивает с толку :)   -  person Marc Gravell    schedule 31.01.2017
comment
Вы понимаете, что while() в основном то же самое, что и использование SpinLock, но с дополнительной сложностью?   -  person Gusman    schedule 31.01.2017
comment
@Gusman, вам действительно нужен цикл - вам нужно повторить с самого начала в (редком) случае столкновения   -  person Marc Gravell    schedule 31.01.2017
comment
@MarcGravell С его кодом, да, но суть вопроса в том, чтобы избежать блокировок, и этот цикл в конце такой же, как спин-блокировка, поэтому не лучше ли использовать предоставленные механизмы, чем накатывать свой собственный?   -  person Gusman    schedule 31.01.2017
comment
@Gusman, единственный цикл в коде, который я вижу, - это повторение до тех пор, пока мы не выполним цикл, который требуется и не связан с вращением; я что-то упускаю?   -  person Marc Gravell    schedule 31.01.2017
comment
После каждого цикла цикла пользователь вызывает spi.SpinOnce(), и это именно то, что спин-блокировка будет делать внутри, чтобы получить блокировку, поэтому весь этот код может быть возобновлен с помощью спин-блокировки для lock.Enter(ref locked); items[i][j] += addendum; lock.Exit();   -  person Gusman    schedule 31.01.2017
comment
@Gusman Я не понял, но я посмотрю SpinLock, спасибо. Пожалуйста, потерпите меня, я простой физик :)   -  person tethered.sun    schedule 31.01.2017
comment
@tethered.sun Np, просто указал на это, потому что, если вы не знаете SpinLocks, это не очевидно.   -  person Gusman    schedule 31.01.2017
comment
Я провел небольшое исследование производительности различных решений для обеспечения параллелизма и нашел следующее: kejser.org/ Я был удивлен, насколько конкурентоспособна обычная блокировка в домене высокой конкуренции. В моей задаче я ожидаю низкой конкуренции (моделирование Монте-Карло распространения фотонов в ткани; события, которые могли бы изменить массив, редки, и даже тогда вероятность того, что два таких события происходят одновременно и затрагивают один и тот же пиксель очень низкий). В этом диапазоне операции Interlocked превосходят SpinLock.   -  person tethered.sun    schedule 02.02.2017

Ответы (2)


arrow_upward
5
arrow_downward

Да, он по-прежнему будет атомарным и потокобезопасным. Любые вызовы в одну и ту же ячейку будут передавать один и тот же адрес-двойнику. Такие детали, как то, находится ли он в массиве или в качестве поля объекта, не имеют значения.

Однако строчка:

double newCurrentValue = items[i][j];

не является атомарным - это может теоретически дать разорванное значение (особенно на x86). На самом деле в данном случае это нормально, потому что в сценарии с порванным значением он просто попадает в цикл, считается коллизией и повторяется — на этот раз с использованием известного атомарного значения из CompareExchange.

person Marc Gravell    schedule 31.01.2017
comment
Большое спасибо, сэр. - person tethered.sun; 31.01.2017

arrow_upward
3
arrow_downward

Кажется, вы хотите в конечном итоге добавить некоторое значение к элементу массива.

Я полагаю, что есть только обновления значений (сам массив остается той же частью памяти), и все обновления выполняются с помощью этого метода AddToItem.< br/> Итак, вам нужно каждый раз читать обновленное значение (иначе вы потеряете изменения, сделанные другим потоком, или получите бесконечный цикл).

public class Example
{
    double[][] items;

    public void AddToItem(int i, int j, double addendum)
    {
        var spin = new SpinWait();

        while (true)
        {
            var valueAtStart = Volatile.Read(ref items[i][j]);
            var newValue = valueAtStart + addendum;

            var oldValue = Interlocked.CompareExchange(ref items[i][j], newValue, valueAtStart);

            if (oldValue.Equals(valueAtStart))
                break;
            spin.SpinOnce();
        }
    }
}


Обратите внимание, что для чтения items[i][j] нам нужно использовать какой-то изменчивый метод. Volatile.Read используется, чтобы избежать некоторых нежелательных оптимизаций, разрешенных моделью памяти .NET (см. спецификации ECMA-334 и ECMA-335).
Поскольку мы обновляем значение атомарно (через Interlocked.CompareExchange), достаточно прочитать items[i][j] через Volatile.Read.< br/>
Если не все изменения этого массива выполняются в этом методе, то лучше написать цикл, в котором создается локальная копия массива, модифицируется и обновляется ссылка на новый массив (используя Volatile.Read и Interlocked.CompareExchange)

person Valery Petrov    schedule 01.02.2017
comment
И особого смысла в SpinLock здесь нет. В большинстве случаев самого цикла более чем достаточно. - person Valery Petrov; 01.02.2017
comment
Большое спасибо за ваши предложения! - person tethered.sun; 01.02.2017