Incorrect result with too many threads

c#, multithreading

Solution

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

Problem

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.

Original source