117 posts
Code hacker/developer
Edited by Todd on
I've watched a couple of the Multithreading HH episodes, but this is my first time actually implementing it. This is in C#, but it's pretty clear what I'm trying to do:

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.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71  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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  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. The work is also not getting done in a particularly fast way, but I'm sure that's because I'm throwing numbers like 5798238593 in there on purpose (it's quite fast with smaller numbers), and also I'm sure my code could be improved as well.

I'm on an Intel i7 quad core machine with Environment.ProcessorCount = 8 (8 logical cores).

I remember Casey talking a lot about the LockedIncrement, InterLockedCompareExchange, and InterlockedExchange, but my confusion is in that I have fired the same function in 6 different threads with 6 different parameters, so I'm assuming each thread is getting its own "instance" of the function, no? Whereas if I had two threads going thru the exact same function with the exact same local variables, then I would need the locking? Please correct me if I'm wrong and sorry if my code looks bad, I actually did all of this completely from scratch and haven't seen a "proper" implementation of finding primes or anything on multithreading other than HH. Last but not least, is breaking the work up like this even the proper way to go about doing this with multiple threads? Is there some way to use a mutex to have the same effect without doing the divide by 6 part? Thank you.
Mārtiņš Možeiko
2262 posts / 2 projects
Edited by Mārtiņš Možeiko on
Print out (or look in debugger) at workChunk array.

For second program, assuming userEntry is 36 and split = 6, you have it like this: { 36, -6, -6, -6, -6, ... -6 };
That seems pretty wrong. I assume you want it like this: { 36, 30, 24, 18, 12, 6, 0 };

But doing multithreading this way will not be very efficient. The way you check if number is prime will take much more work for checking numbers from 36 to 30, than to check from 6 to 0. The larger the numbers, the worse it will get. So some threads will take longer time to finish, but other (most of them) will finish fast and then will be idle while you wait for those long threads to finish.

If you want to keep the algorithm as it is currently, then don't create one thread per chunk. Create one thread per core in your CPU. Then have one atomic number shared with all threads that will store number that needs to be checked next (initialize it with userEntry). Each thread should atomically decrement it to get number it needs to check. So first thread will get 36, next thread will get 35, and so on. Once they get to 1 (or 1) they can return from the thread.

For much larger numbers this will be very slow algorithm. You should look into Miller-Rabin or similar probabilistic primality tests.
117 posts
Code hacker/developer