JAVA Multithreading to check primality of several numbers at once is slower than single threading [duplicate]

Question

(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.

Answer 1

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