1
    static void Main(string[] args)
    {
            var sw = new Stopwatch();
            sw.Start();

            int noOfThreads = Environment.ProcessorCount;
            //int minVal = 1;
            int maxVal = 10000000;
            int  blockSize = maxVal / noOfThreads;
            List<Thread> threads = new List<Thread>();
            List<List<int>> results = new List<List<int>>();
            object thisLock = new object();

            for (int i = 0; i < noOfThreads; ++i)
            {
                lock(thisLock)
                {
                    Thread th = new Thread(() =>
                    {
                        results.Add(GetPrimeNumbers(i * blockSize, i * blockSize + blockSize));
                    });

                    th.Start();
                    threads.Add(th);
                }
            }

            foreach (var elem in threads)
                elem.Join();
   }

   private static List<int> GetPrimeNumbers(int low, int high)
   {
        List<int> result = new List<int>();
        //Debug.WriteLine("Low: {0}. High: {1}", low, high);
        for(int i = low; i <= high; ++i)
        {
            if (IsPrime(i))
                result.Add(i);
        }

        return result;
    }

    static bool IsPrime(int number)
    {
        if (number % 2 == 0)
            return false;
        else
        {
            var topLimit = (int)Math.Sqrt(number);
            for (int i = 3; i <= topLimit; i += 2)
                if (number % i == 0) 
                    return false;

            return true;
        }
    }

With the above code, I was expecting that when I put breakpoint in the GetPrimeNumbers(int low, int high) I would see range of values for low and high, e.g: (0, 1250000), (1250000, 2500000).....(8750000, 10000000). But what I observing is that there are certain blocks that gets passed multiple times - (2500000, 3750000) while certain do not passed at all -(0, 1250000) and this behaviour also matches the results I am getting.

I am curious why I am seeing this behaviour. Is there a way to prevent this?

I am aware of the fact that I can use Parallel.For() and over here I do see the expected behaviour at breakpoint in GetPrimes(int low, int high). But as I mentioned before I am curious why I am seeing the former behaviour.

Thanks in advance!

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
Dwight Schrute
  • 359
  • 1
  • 5
  • 17
  • 1
    Shouldn't be the cause, but your `lock` is at the wrong level. The threads should be locking when they add to `results`, not your loop when it's creating threads. – Jeroen Mostert Apr 12 '21 at 14:48
  • Yes, I did left the IsPrime function but I did not think it was relevant over here since I saw the behaviour even before the function is called. Yes, it is properly scoped. – Dwight Schrute Apr 12 '21 at 14:49
  • 1
    Show us the code for isPrime anyway. It's not a proper MCVE unless we can reproduce your code in an IDE. – Robert Harvey Apr 12 '21 at 14:50
  • 1
    `IsPrime` isn't relevant to my remark -- each individual invocation of `GetPrimeNumbers` is thread-safe (assuming `IsPrime` is), but your calls to `results.Add` are *not* since threads aren't synchronizing there. There is no need for your `Main` to lock on anything, but the thread delegates should. – Jeroen Mostert Apr 12 '21 at 14:51
  • Updated the code with edit. – Dwight Schrute Apr 12 '21 at 14:54
  • Related: [Captured variable in a loop in C#](https://stackoverflow.com/questions/271440/captured-variable-in-a-loop-in-c-sharp) – Theodor Zoulias Apr 12 '21 at 15:22

2 Answers2

3

The problem is that a for loop reuses the same i variable across iterations, and your thread delegate is closing over that variable.

There are various ways to fix this. A simple one is to use a new variable declared within your loop:

for (int i = 0; i < noOfThreads; ++i)
{
    int j = i; // capture the value
    lock(thisLock)
    {
        Thread th = new Thread(() =>
        {
            results.Add(GetPrimeNumbers(j * blockSize, j * blockSize + blockSize));
        });

        th.Start();
        threads.Add(th);
    }
}

This still has other issues, though. I'd recommend something more like this:

var allPrimeNumbers = Enumerable.Range(0, numberOfThreads)
    .AsParallel()
    .SelectMany(i => GetPrimeNumbers(i * blockSize, i * blockSize + blockSize))
    .ToList();

Further Reading
Is there a reason for C#'s reuse of the variable in a foreach?

StriplingWarrior
  • 151,543
  • 27
  • 246
  • 315
1

StriplingWarrior had it close, but as mentioned in the comments, you still have a threading bug. You need to move the lock inside the Thread action. Also, to get the best performance, hold the lock for the shortest amount of time possible, which is when modifying the shared results variable. To do that I separated the GetPrimeNumbers call from the results.Add call.

for (int i = 0; i < noOfThreads; ++i)
{
    int j = i; // capture the value
    Thread th = new Thread(() =>
    {
        result = GetPrimeNumbers(j * blockSize, j * blockSize + blockSize);
        lock(thisLock) 
        {
           results.Add(result);
        }
    });

    th.Start();
    threads.Add(th);
}

Also, unless you really need to manage your own threads I would recommend using Tasks (TPL) instead. Here is a modification using Tasks

Task<List<int>> tasks = new Task<List<int>>();
for (int i = 0; i < noOfThreads; ++i)
{
    int j = i; // capture the value
    tasks.Add(Task.Run(() => GetPrimeNumbers(j * blockSize, j * blockSize + blockSize)));
}

Task.WaitAll(tasks);
results = tasks.Select(t => t.Result).ToList();
Ted Elliott
  • 3,415
  • 1
  • 27
  • 30