Concurrent modification of double[][] elements without locking

Question

I have a jagged double[][] array that may be modified concurrently by multiple threads. I should like to make it thread-safe, but if possible, without locks. The threads may well target the same element in the array, that is why the whole problem arises. I have found code to increment double values atomically using the Interlocked.CompareExchange method: Why is there no overload of Interlocked.Add that accepts Doubles as parameters?

My question is: will it stay atomic if there is a jagged array reference in Interlocked.CompareExchange? Your insights are much appreciated.

With an example:

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

Personally, I'd rename `newCurrentValue` to `oldValue` - that's just confusing :) — Marc Gravell, Jan 31 '17 at 10:58
Do you realize that while() is basically the same as using a SpinLock but with added complexity? — Gusman, Jan 31 '17 at 11:01
@Gusman you do need the loop though - you need to redo from start in the (rare) case of a collision — Marc Gravell, Jan 31 '17 at 11:02
@MarcGravell With his code, yes, but the point of the question is to avoid locks, and that loop at the end is the same as a spinlock, so, is not better to use the provided mechanisms than rolling your own? — Gusman, Jan 31 '17 at 11:04
@Gusman the only loop in the code that I can see is the "repeat until we succeed" loop that is required and unrelated to spinning; am I missing something? — Marc Gravell, Jan 31 '17 at 11:08
After each cycle of the loop the user calls spi.SpinOnce(), and that's exactly what a spinlock will do internally to acquire a lock, so all that code can be resumed using an spinlock to `lock.Enter(ref locked); items[i][j] += addendum; lock.Exit();` — Gusman, Jan 31 '17 at 11:14
@Gusman I did not realise but I shall look `SpinLock` up, thank you. Please bear with me, I am a mere physicist :) — tethered.sun, Jan 31 '17 at 11:25
@tethered.sun Np, just was pointing it because if you don't know SpinLocks is not obvious. — Gusman, Jan 31 '17 at 11:26
I did some research on the performance of different solutions addressing concurrency, and found this: http://kejser.org/synchronisation-in-net-part-3-spinlocks-and-interlocks/ I was surprised how competitive an ordinary lock seems in the domain of high contention. In my task I expect low contention (Monte Carlo simulation of the propagation of photons within a tissue; events that would modify the array are rare, and even then the chance that two such events are concurrent *and* address the very same pixel is very low). In this range, Interlocked operations seem to outperform SpinLock. — tethered.sun, Feb 02 '17 at 09:34

Marc Gravell · Accepted Answer · 2017-01-31T11:04:27.233

Yes, it will still be atomic and thread-safe. Any calls to the same cell will be passing the same address-to-a-double. Details like whether it is in an array of as a field on an object are irrelevant.

However, the line:

double newCurrentValue = items[i][j];

is not atomic - that could in theory give a torn value (especially on x86). That's actually OK in this case because in the torn-value scenario it will just hit the loop, count as a collision, and redo - this time using the known-atomic value from CompareExchange.

score 2 · Answer 2 · answered Feb 01 '17 at 11:24

Seems that you want eventually add some value to an array item.

I suppose there are only updates of values (array itself stays the same piece of memory) and all updates are done via this AddToItem method.
So, you have to read updated value each time (otherwise you lost changes done by other thread, or get infinite loop).

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

Note that we have to use some volatile method to read items[i][j]. Volatile.Read is used to avoid some unwanted optimizations that are allowed under .NET Memory Model (see ECMA-334 and ECMA-335 specifications).
Since we update value atomically (via Interlocked.CompareExchange) it's enough to read items[i][j] via Volatile.Read.

If not all changes to this array are done in this method, then it's better to write a loop in which create local copy of array, modify it and update reference to new array (using Volatile.Read and Interlocked.CompareExchange)

And there is not much sense in SpinLock here. In most cases loop itself is more than enough. — Valery Petrov, Feb 01 '17 at 11:41

Concurrent modification of double[][] elements without locking

2 Answers2