CODEWITHSUNDEEP
c#multithreadingconcurrencythread-safetytask-parallel-library
Matias Cicero
Matias Cicero

Reputation: 26331

Reading and writing a multi-thread shared array

I have the following code:

const int MAX = 101;
const int MIN_COMBINATORIC = 1000000;

int[,] pascalTriangle = new int[MAX, MAX];

Parallel.For(0, MAX, i =>
{
     pascalTriangle[i, 0] = 1;
     pascalTriangle[i, i] = 1;
}); 

int counter = 0;

Parallel.For(0, MAX, x => Parallel.For(1, x, y => 
{
      int value = pascalTriangle[x - 1, y] + pascalTriangle[x - 1, y - 1];
      Interlocked.Exchange(ref pascalTriangle[x, y], value < MIN_COMBINATORIC ? value : MIN_COMBINATORIC);
      if(value > MIN_COMBINATORIC)
          Interlocked.Increment(ref counter);
}));

Console.WriteLine("Result: {0}", counter);

The problem is that it sometimes prints out the correct answer (Result: 4075), but sometimes it prints a random (and wrong) answer, such as:

I'm guessing it has something to do with the fact that I'm reading and writing a shared array between multiple threads. As you can see, I tried adding Interlocked.Exhange() for thread-safe write operations, but I could not find a similar method for reading (There's a Interlocked.Read() but it can only read long variables)

How can I make the above code run concurrently in a thread-safe manner?

Upvotes: 0

Views: 1168

Answers (2)

Mayoor
Mayoor

Reputation: 181

The value variable in

int value = pascalTriangle[x - 1, y] + pascalTriangle[x - 1, y - 1];

is dependent on two items in the array. Due to concurrency, those values can change between adding those two items, storing them into value, and passing that value into Interlocked.Exchange. This means that by the time you store value in pascalTriangle[x, y], the values in pascalTriangle[x - 1, y] and/or pascalTriangle[x - 1, y - 1] could have changed.

I actually can't think of an easy concurrent solution for this. The obvious solution is to not do this concurrently. If this the actual code you want to use, there is no real benefit to running this concurrently since it is only looping 101 * 101 = 10,201 times, which can be done very quickly (the first parallel code to initialize the triangle is only looping 101 times, so that can be single-threaded too). If you are creating multiple triangles like this, then you might benefit from concurrently creating triangles (in other words, this method that creates a triangle is single-threaded, but the caller calls this method multiple times on separate threads).

If you really want a concurrent solution, you will need to figure out how to implement a locking mechanism that can lock the 3 array items you are accessing, and (the difficult part) lock them in such a way that deadlocking cannot occur. And even if you come up with a solution, the overhead of all of the locks might actually make the code slower than doing it non-concurrently.

Upvotes: 3

rmn36
rmn36

Reputation: 656

You should look into using a BlockingCollection in the Systems.Collections.Concurrent namespace.

If BlockingCollection doesn't fit your needs this namespace has a bunch of different types of collections that are all thread-safe like a dictionary, stack, queue, etc.

Upvotes: 0

Related Questions