5

(I haven't been able to find the answer to this anywhere, so sorry if this is a question which has already been asked.)

I need to check whether each number up to a value specified by my user is a prime number. Therefore I brute force check whether each number up to that value (which I technically want to be as large as the user wishes it to be) is a prime number by the method of checking whether

p%i==0

is true where p is the user-entered value for every odd number 3

Obviously, cycling through every single odd number up to half of the entered value takes a while once the program starts checking very big numbers. Due to this limitation, my program in its current state slowed down its "numbers checked per second" rate by quite a lot on big numbers, which meant that the program could take a long time to finish for very big numbers.

To somewhat remedy this, I tried to implement multithreading for the prime checking aspect, as follows:

int CPUs = Runtime.getRuntime().availableProcessors();
int acCPU = 0;
//...
Thread pCheckThread[] = new Thread[CPUs-1];
class pCheckRunnable implements Runnable{
    long pr;
    int xp, yp;
    pCheckRunnable(long prime){
        pr=prime;
    }
    public void run(){
        if(isPrime(pr))
            //Do stuff...
    }
}
//...
for(long i=1; i<valueEntered; i++){
    pCheckThread[acCPU] = new Thread(new pCheckRunnable(i));
    pCheckThread[acCPU].start();
    acCPU++;
    if(acCPU>=CPUs){
    for(int t=0; t<pCheckThread.length; t++){
        try {
        pCheckThread[t].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    acCPU = 0;
    }
}

As you can hopefully see, the idea was to check whether several numbers are prime at once, with each check running in a separate thread up to a maximum number of threads equal to the number of processor cores available.

Problem is, the program seems to now actually be running slower.

This is my very first time trying my hand at multithreading and parallel processing, and I may just have made some very stupid mistakes or my code might be a huge mess in some of you more experienced coders' opinions, so feel free to tell me if I've done any serious mistake that could cause instability or corruption etc.

user3224223
  • 51
  • 2
  • One small optimization, you only have to check up to the square root of the entered number, not up to half of it. – Mike B Jan 22 '14 at 16:33
  • @user3224223: to me your multi-threading code is way too low-level. Moreover as I understand it you're only starting new threads once all the previous threads are done: so if, say, there's only one of 8 threads still working, it's going to prevent the 7 others from doing any work. Also typically you don't want to start 10 million threads if you have 10 million numbers to test: you'd start, say, 8 threads testing 1 250 000 number each. – TacticalCoder Jan 22 '14 at 16:37
  • @user3224223: also you probably want to use the *isProbablePrime* method to quickly discard all the composite numbers. – TacticalCoder Jan 22 '14 at 16:37
  • @TacticalCoder I was waiting for all the threads to be done so as to prevent opening more threads than processors available, but you just made me realize that I could've done it much more efficiently by only waiting for one thread to finish before starting the next one instead of waiting for all of them to finish before starting a new batch. I didn't want to use the isProbablePrime method as I wanted my prime check to be 100% accurate. – user3224223 Jan 22 '14 at 16:50
  • @user3224223: I didn't talk about not doing 100% accurate prime detection. I talked about using *isProbablePrime* first to discard for sure composite numbers. There's no false negative when using *isProbablePrime*, so if *isProbablePrime* says that a number is not prime, you can be sure it is not prime. You're then free to do whatever you want if *isProbablePrime* returns *true*. – TacticalCoder Jan 22 '14 at 16:54
  • @TacticalCoder Ah I now see what you mean, I feel a bit thick now. Sounds like a great suggestion. Do you per chance know how lengthy the processing of _isProbablePrime_ is? I'm just afraid that the extra time from having to _isProbablePrime_ check a number and it returning positive, therefore having to perform a brute force check might outweigh the gained time from the numbers for which _isProbablePrime_ will return negative. I hope you understand what I meant by that. I'll try out your method anyways and see if I notice an improvement. – user3224223 Jan 22 '14 at 17:00
  • @user3224223: But you do not need to wait till `isProbablePrime` finishes, so you only waste a single thread. Actually, I wouldn't bother with multithreading before I could be sure I'm using the best not-too-overcomplicated algorithm. With 16 cores, you get a speedup up to 16. With a better algorithm, there's a chance of gaining much more. – maaartinus Jan 22 '14 at 21:08

1 Answers1

3

The likeliest reason is that the unit of work (isPrime(p)) is fairly small and starting the threads takes more time than the calculation itself.

To improve the performance, you should submit the tasks to an ExecutorService with a number of threads = number of processors (above that number, your threads will compete for CPU resources and it will be counterproductive). You will then only create a few thread and reuse them, saving the overhead of thread creation.

Once that is done you should see a noticeable improvement. You can then try to group the tasks and submit more than one at a time to see if it further improves the performance.

So it would look like:

ExecutorService executor = 
    Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

for(long i=1; i<valueEntered; i++){
    executor.submit(new pCheckRunnable(i));
}
executor.shutdown();
executor.awaitTermination();
Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783
  • As far as i know if you have a P4 processor with hyper-threading it may also be the reason. Am i wrong? – Mr. P Jan 22 '14 at 16:34
  • @Pisek Yes - whatever the number of processors, starting a thread introduces a non negligible overhead. – assylias Jan 22 '14 at 16:37
  • what i meant is that in some systems HT is considered as another "core" in the processor. AFAIK in this case `Runtime.getRuntime().availableProcessors()` could get 2 times greater number. – Mr. P Jan 22 '14 at 16:41
  • @Pisek Ah I see - yes it would probably return 2 when 1 would probably work better. But I don't think you can deal with that issue in pure Java... – assylias Jan 22 '14 at 16:45
  • I didn't realise that starting the threads itself would take a significant amount of time. Thank you. So, as my code stands currently it would only be more efficient once it starts checking much bigger numbers, where the time to check isPrime(p) is longer than that required to start new threads? That ExecutorService solution looks to be really useful, much cleaner than my newbie attempt at threads. I'll try it out, thanks for the help! – user3224223 Jan 22 '14 at 16:54
  • 1
    Either this method - or if you really want to get maximum performance out of it, create n static threads and assign work round-robin to the threads (kth thread checks number 0, k, 2k, etc.). Prime number checking obviously isn't perfectly balanced, but in practice it works good enough to give better results than the Executor approach - at least last time I checked on a larger computer. – Voo Jan 22 '14 at 18:33
  • @Voo: I just wanted to write something like this. And if the balancing should be a problem, there's always the possibility to divide the work into reasonably sized pieces, and let the workers take them one after the other. – maaartinus Jan 22 '14 at 21:12
  • @maartinus Oh yes I just wanted to mention the other "extreme" so to speak. For many problems you want something somewhere in between indeed. – Voo Jan 22 '14 at 21:20