Using nested Parallel.For

Question

Consider this example:

var x = 0;

for (var i = 0; i < 100; i++ )
{
    for (var a = i+1; a < 100; a++)
        x += 1;
}

When printing x we always get 4950. What about if I want to parallelise this?

This is what I come up with

Parallel.For(0, 100, i => Parallel.For(i + 1, 100, a => { x += 1; }));

However this does Not print 4950 each time I run it. Why?

Answer 1

What have you done to ensure that updating x is atomic ? Or, if you prefer, how do you prevent separate threads of execution from overlapping reads and writes of x in a non-deterministic manner ?

Answer 2

Parallel Extensions helps you with task creation, allocation, running and rendezvous, in a near-imperative syntax. What it doesn't do is take care of every kind of thread safety (one of the pitfalls). You are trying to make parallel threads simultaneously update a single shared variable. To do anything like this correctly, you have to introduce e.g. locking.

I'm not sure what you're trying to do. I assume your code is just a placeholder or experiment. Parallelization is only suitable when you can isolate your different pieces of work; not when you constantly have to rendezvous with shared data.

Answer 3

As was previously mentioned, the issue here is controlling multithreaded access to the 'x' variable. One way to deal with it is by locking the variable:

lock(x){x+=1;}

Another approach is to use .Net's 'Increment' operator:

System.Threading.Interlocked.Increment(ref x);

I have never benchmarked the two approaches, but using 'Increment' is supposed to be more efficient than setting a lock. See 'General Recommendations' in http://msdn.microsoft.com/en-us/library/1c9txz50.aspx

Answer 4

As an alternative to locking each time, you could use thread-local variables in combination with a lock:

Object thisLock = new Object();
var globalSum = 0;
System.Threading.Tasks.Parallel.For(0, 100, i => {
    System.Threading.Tasks.Parallel.For(i + 1, 
                                        100, 
                                        () => 0, 
                                        (num, loopState, subSum) => ++subSum, 
                                        subSum => { lock(thisLock) { globalSum += subSum; } });
});

Console.WriteLine(globalSum);

Answer 5

The problem in your example is that you are using a non-atomic way (and therefore not thread-safe) of updating variable 'x'. The "+=" operator (i.e. The addition assignment operator) is not atomic as it involves a read of the variable and then an assignment to the variable. If you have multiple threads using the "+=" operator then they may interleave read and write operations ,or perform them at the same time, and so update values in unintended ways - a classic race condition.

For example, two threads may read variable 'x' value as 1, and then both update the value to 2.

If you are updating any shared state you should use atomic operations so that multiple threads do not see intermediary values in what you intend to be a single compound operation.

For your example which is incrementing variable 'x', you can use the Interlocked API:

Parallel.For(0, 100, i => Parallel.For(i + 1, 100, a => Interlocked.Increment(ref x)));

This will guarantee that the increment of variable 'x' is carried our atomically.