My first attempt at multithreading in C# with Prime Numbers

Question

This is my first attempt at multithreading in C#. This entire program does several things with prime numbers, but the part I'm going to post is mainly focused with printing out all prime numbers starting at a high number all the way until it reaches 1. This was not originally intended to be a multi-threaded program, but I wanted to check out some large numbers (I actually have an overload that takes a BigInteger type I will eventually use) and I was watching the computer get bogged down whilst only using 20% of the CPU. In comes multithreading.

public void printAllPrimes(int number)
{
    Console.WriteLine(
        isItPrime(number)
            ? "{0} is prime. Below are all prime numbers between it and 1:\n"
            : "{0} is not prime but below are all prime numbers between it and 1:\n", number);

    int holder = number;

        while (--holder > 1){
            if (isItPrime(holder))
                Console.WriteLine("{0} \t Thread {1}", holder, Thread.CurrentThread.ManagedThreadId);
    }
}


public bool isItPrime(int number)
{
    if (number <= 1){ 
        return false;
    }
    //We don't want to decrement the number because we need it for the comparisons, so we use holder.
    int holder = number;

    while (--holder > 1){
        //Divisible = divide by a number and get no remainder.
        if (number % holder == 0){
            return false;
        }

    }
    return true;
}


static void Main(string[] args)
{
    Program program = new Program();
    Console.WriteLine("Enter an integer and find out whether it is prime, and find primes all the way down to 1!\n");
    int userEntry = 0;
    while (!Int32.TryParse(Console.ReadLine(), out userEntry)){
        Console.WriteLine("Enter a valid integer!");
    }

    int split = userEntry / 6;
    int[] workChunk = new int[6];
    for (int i = 0; i < 6; i++){
        workChunk[i] = (userEntry - split);
        userEntry -= split;
    }
    Thread t1 = new Thread(p => program.printAllPrimes(workChunk[0]));

    Thread t2 = new Thread(p => program.printAllPrimes(workChunk[1]));

    Thread t3 = new Thread(p => program.printAllPrimes(workChunk[2]));

    Thread t4 = new Thread(p => program.printAllPrimes(workChunk[3]));

    Thread t5 = new Thread(p => program.printAllPrimes(workChunk[4]));

    Thread t6 = new Thread(p => program.printAllPrimes(workChunk[5]));

    t1.Start();
    t2.Start();
    t3.Start();
    t4.Start();
    t5.Start();
    t6.Start();


}

The good news is, I got the CPU up and they are indeed printing output like this sample:

883      Thread 7
881      Thread 7
877      Thread 7
863      Thread 7
859      Thread 7
857      Thread 7
853      Thread 7
839      Thread 7
829      Thread 7
827      Thread 7
823      Thread 7
3733     Thread 4
3727     Thread 4
2731     Thread 5
2729     Thread 5
1511     Thread 6
1499     Thread 6
1493     Thread 6
1489     Thread 6
1487     Thread 6
3719     Thread 4
3709     Thread 4
3701     Thread 4
3697     Thread 4
3691     Thread 4

However, there are indeed repeats (e.g. 891 appears twice) so I ended up refactoring to this:

Main snippet:

int[] workChunk = new int[6];
workChunk[0] = userEntry; //e.g. 36
for (int i = 0; i < 6; i++){
    workChunk[i] -= split; // 36 - 6 = 30

}
Thread t1 = new Thread(p => program.printAllPrimes(userEntry,workChunk[0]));

Thread t2 = new Thread(p => program.printAllPrimes(workChunk[0],workChunk[1]));

Thread t3 = new Thread(p => program.printAllPrimes(workChunk[1],workChunk[2]));

Thread t4 = new Thread(p => program.printAllPrimes(workChunk[2],workChunk[3]));

Thread t5 = new Thread(p => program.printAllPrimes(workChunk[3],workChunk[4]));

Thread t6 = new Thread(p => program.printAllPrimes(workChunk[4],workChunk[5]));

Using this new overload on printAllPrimes:

public void printAllPrimes(int beginwork,int endwork)
{
    int holder = beginwork;

    while (--holder > endwork)
    {
        if (isItPrime(holder))
            Console.WriteLine("{0} \t Thread {1}", holder, Thread.CurrentThread.ManagedThreadId);
    }
}

Now good thing is, nothing gets repeated. However, now the work only ever gets handled by 2 threads max and I'm not sure why, where before all threads were properly firing up, the thread IDs do change. For example, sometimes it's 10 and 11, others 3 and 4, but only 2.

NOTE: I'm on an Intel i7 quad core machine with Environment.ProcessorCount = 8.

Answer 1

int split = userEntry / 6;
int[] workChunk = new int[6];
for (int i = 0; i < 6; i++){
    workChunk[i] = (userEntry - split);
    userEntry -= split;

This is not a very flexible and up-to-date solution. You not only need to calcucalte the number of threads/parallel tasks manually but the number of cpus is hardcoded and cannot be easily used on other machines.

One way to improve it would be to use the Environment.ProcessorCount.

But what you really need is the newer TPL. There is already a Partitioner Class for creating such chunks.

If you wanted to calculate primes for the range 1-4000 you would write (the last one is exclusive, thus +1)

 var partitioner = Partitioner.Create(1, 4001);

Then you let C# handle the threads with Parallel.ForEach

Parallel.ForEach(partitions, p =>
{
    Console.WriteLine($"Partition {p} [{Thread.CurrentThread.ManagedThreadId}]");
    Task.Delay(2000).Wait();
    for (int i = p.Item1; i < p.Item2; i++)
    {
        //Console.WriteLine($"IsPrime({i}) = {IsPrime(i)}");
    }
});

The Task.Delay(2000).Wait() pretends the loop is doing some heavy work. If it's not then it might not be necessary to spawn/use more threads so after all it might run with only one or two threads.

If you don't want to use all cpus you can specify another parameter and limit them with

new ParallelOptions { MaxDegreeOfParallelism = 4 },

On my machine for example (4 cpus) the delay causes that four parallel executions take place:

Partition (1, 334) [12]
Partition (1000, 1333) [14]
Partition (334, 667) [16]
Partition (667, 1000) [15]

Partition (1333, 1666) [10]
Partition (1666, 1999) [17]
Partition (1999, 2332) [15]
Partition (2332, 2665) [12]
Partition (2998, 3331) [16]
Partition (3331, 3664) [14]
Partition (2665, 2998) [19]
Partition (3664, 3997) [10]
Partition (3997, 4001) [17]

without it there are just two:

Partition (1, 334) [12]
Partition (334, 667) [12]
Partition (667, 1000) [12]
Partition (1000, 1333) [12]
Partition (1333, 1666) [12]
Partition (1666, 1999) [12]
Partition (1999, 2332) [12]
Partition (2332, 2665) [12]
Partition (2665, 2998) [12]
Partition (2998, 3331) [6]
Partition (3331, 3664) [12]
Partition (3664, 3997) [6]
Partition (3997, 4001) [12]

Answer 2

Bug in setting up work chunks

Your new code did not set up the work chunks correctly:

int[] workChunk = new int[6];
workChunk[0] = userEntry; //e.g. 36
for (int i = 0; i < 6; i++){
    workChunk[i] -= split; // 36 - 6 = 30

}

If userEntry is 36, the above code will result in workChunk[0] = 30 but all other other workChunk[x] = -6. This explains why only two threads were printing things, because the first thread handled the range [36..30) and the second handled the range [30..-6). All the other threads were handling the range [-6..-6). You probably meant to set each work chunk to the previous one minus split, like this:

int[] workChunk = new int[6];
workChunk[0] = userEntry - split; //e.g. 30
for (int i = 1; i < 6; i++) {
    workChunk[i] = workChunk[i-1] - split; // e.g. 24, 18, ..., 0
}