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

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 2

Here would be the "correct" way of doing it, this would not require you to lock on your final total object and would only require you to do the interlocked operations at the end of each local thread's looping.

int x = 0;
Parallel.For(0, 100,
    () => 0, //LocalInit
    (i, loopstate, outerlocal) =>
    {
        Parallel.For(i + 1, 100,
            () => 0, //LocalInit
            (a, loopState, innerLocal) => { return innerLocal + 1; },
            (innerLocal) => Interlocked.Add(ref outerlocal, innerLocal)); //Local Final
        return outerlocal;
    },
    (outerLocal) => Interlocked.Add(ref x, outerLocal)); //Local Final

However, having two nested Parallel statements doing this little of work is likely a bad idea. There is a overhead cost that needs to be considered, if you are doing such small amount of work it would be much better to do only one Parallel statement or have none at all.

I highly recommend you go download and read Patterns for Parallel Programming, it goes in to good detail about why small nested parallel loops like this are not a good idea.