Incorrect result with too many threads

Question

Here is a seemingly simple class to sum all elements in an array:

class ArraySum
{
    class SumRange
    {
        int left;
        int right;
        int[] arr;
        public int Answer { get; private set; }

        public SumRange(int[] a, int l, int r)
        {
            left = l;
            right = r;
            arr = a;
            Answer = 0;
        }

        public void Run()
        {
            if (right - left == 1)
            {
                Answer = arr[left];
            }
            else
            {
                SumRange leftRange = new SumRange(arr, left, (left + right) / 2);
                SumRange rightRange = new SumRange(arr, (left + right) / 2, right);

                Thread leftThread = new Thread(leftRange.Run);
                Thread rightThread = new Thread(rightRange.Run);
                leftThread.Start();
                rightThread.Start();
                leftThread.Join();
                rightThread.Join();

                Answer = leftRange.Answer + rightRange.Answer;
            }
        }
    }

    public static int Sum(int[] arr)
    {
        SumRange s = new SumRange(arr, 0, arr.Length);
        s.Run();
        return s.Answer;
    }
}

Of course this is not an efficient way to perform this task. And this is also very inefficient usage of threads. This class is written to illustrate a basic divide and conquer solution concept, and it hopefully does so.

Here is also a simple unit test for this class:

public void should_calculate_array_sum()
{
    int N = 1000;
    int[] arr = System.Linq.Enumerable.Range(0, N).ToArray();

    int sum = ArraySum.Sum(arr);

    Assert.AreEqual(arr.Sum(), sum);
}

And here is the problem. When N is set to 1000, this test fails approximately 3 times out of 5 on my machine, with actual result being smaller than expected. When N is 100 and below - it never fails, or at least I never saw it fail.

Why does this program ever fail at all? This is obviously very inefficient approach, with too big overhead for threads management, but it should always work correctly at least, right? There is either some subtle bug that I do not see or some threading concept I do not understand.

Also, I am not looking for a better way to solve this particular problem, or for a better way to illustrate the same concept. I am just trying to figure out why this particular approach fails sometimes.

Answer 1

I put this code into a console application and ran it a few times, after wrapping the Run function in a try-catch (see code below). Several times when I saw the numbers be different, there were a number of OutOfMemory exceptions thrown.

Thus it appears that it depends on how and when the runtime allocates the threads and the resources it has available at that time. To elaborate, if the runtime decides to allocate threads and then move on to the next time slice without having any of the threads do their work, it's possible to have ALL 2000+ threads up and running at the same time (with each thread being allocated 1MB of stack space, among other memory resources). This will quickly deplete your 2GB process memory allocation (which all Windows 32 bit processes have).

Alternatively, if it allocates some threads, lets them do their work then die, then allocate more threads, you won't reach such a high peak memory and will successfully complete - it's all up to how the runtime decides to schedule the work. As others have noted, using the ThreadPool will solve the issue since it re-uses threads.

public void Run()
{
    try
    {
        if (right - left == 1)
        {
            Answer = arr[left];
        }
        else
        {
            SumRange leftRange = new SumRange(arr, left, (left + right) / 2);
            SumRange rightRange = new SumRange(arr, (left + right) / 2, right);

            Thread leftThread = new Thread(leftRange.Run);
            Thread rightThread = new Thread(rightRange.Run);
            leftThread.Start();
            rightThread.Start();
            leftThread.Join();
            rightThread.Join();

            Answer = leftRange.Answer + rightRange.Answer;
        }
    }
    catch(Exception e)
    {
        Console.WriteLine("Error: " + e.Message);
        Debug.WriteLine("Error: " + e.Message);
    }
}

Answer 2

You're not creating hundreds of threads, or even 1000 threads. It can be more like 2000 threads.

Proof

To make the maths easier, say N = 1024.

# bisections  Range  Number of threads
      1       1024     1      (main thread)
      2       512      2
      3       256      4
      4       128      8
      5       64       16
      6       32       32
      7       16       64
      8       8        128
      9       4        256
      10      2        512
      11      1        1024   (individual sum thread)

Total number of threads = 1024 + 512 + 256 + ... 4 + 2 + 1 = 2047. Obviously not all threads need to be active at the same time (when I ran it, many of the threads were killed during the computation), but you are definitely creating around 2000 threads.

---

I am not looking for a better way to solve this particular problem, or for a better way to illustrate the same concept.

If you want to (possibly) solve your problem with a minor change, follow my suggestion 1. I've added some other ways to do this (TPL, ThreadPool) in case you want to do it another way (but I'm pretty sure that's not what you want to do).

Suggestion 1: Reducing thread parallelisation

If you modify the way you use the threads, e.g.

Thread leftThread = new Thread(leftRange.Run);
leftThread.Start();
leftThread.Join();

Thread rightThread = new Thread(rightRange.Run);
rightThread.Start();
rightThread.Join();

then any given thread will only spawn one thread at a time, so the number of active threads will be at most 11.

Suggestion 2: Using the Task Parallel Library

Starting with the .NET Framework 4, the TPL is the preferred way to write multithreaded and parallel code

The Task Parallel Library is likely your best bet unless you specifically want to handle threads yourself.

What's below is far from optimised - there's quite a lot of overhead from using the TPL the way I do below, but it demonstrates the approach.

public void Run()
{
    if ( right - left == 1 )
    {
        Answer = arr[left];
    }
    else
    {
        Answer = new bool[] { true, false }
            .AsParallel()
            .Sum(isLeft =>
                {
                    SumRange sumRange = isLeft
                        ? new SumRange(arr, left, (left + right) / 2)
                        : new SumRange(arr, (left + right) / 2, right);
                    sumRange.Run();
                    return sumRange.Answer;
                });
    }
}

When I ran it it was ridiculously slow because it's running two items in parallel. You might want to consider breaking down into much larger groups (e.g. 10) instead of bisecting. Going back to N = 1000:

# bisections  Range  Number of threads
      1       1000     1      (main thread)
      2       100      10
      3       10       100
      4       1        1000

This reduces the maximum number of threads to 1111, but the TPL will reduce this greatly.

Suggestion 3: ThreadPool

I think you should maybe consider using a ThreadPool to create the threads - that way, the minimum number of threads is only 11 (i.e. the path from bisection 1 to bisection 11). I'm not au fait with how to use ThreadPool, but here's a link which looks useful: MSDN: How to use a Thread Pool.