javamultithreadingsieve-of-eratosthenes

Multithreading slows down with more cores


Im trying to implement Eratosthenes prime sieve with multithreading. The threads are taken care of by a treadpool

ThreadPoolExecutor executor = 
    new ThreadPoolExecutor(
        6,   // cores
        10,  // threads
        1000,
        TimeUnit.MILLISECONDS, 
        new ArrayBlockingQueue<Runnable>(n)
    );

And the sieve it self is implemented like this

for (int i=2; i<Math.sqrt(n); i++ ){
    if (list[i].get()) { // boolean list initialized earlier
        executor.execute(new Calc(i,n));
    }
}

with the run method looking like this

public void run(){
    for (int j=start*2;j<n;j=j+start){ 
        list[j].set(false); 
    }   
}

Now, what i dont understand is why, when the corePoolSize is lower (other parameters stay the same), the program runs faster. (2 cores 2.5 Milliseconds; 7 - 3.3; etc.). I think i might be making some rookie mistake, but i dont understand why this is happening?

EDIT: Full class looks like this (have to use a single class for the cluster, hence everything is in Main:

int start;
int n;
Main(int start,int n){
    this.start=start;
    this.n=n;
}
public void run(){
            for (int j=start*2;j<n;j=j+start){
                list[j].set(true);
            }


        }


private static list myBoolean[];

   public static void main(String[] args) {
    int  n = 20000;     
    list= new AtomicBoolean[n+1];


for (int i=2; i<n; i++ ){
            list[i]=new AtomicBoolean(false);
       }
      ThreadPoolExecutor executor = 
                new ThreadPoolExecutor(
                        7,
                    10,
                    1000,
                    TimeUnit.MILLISECONDS, 
                    new ArrayBlockingQueue<Runnable>(n));

    long startedTime = System.nanoTime();
    for (int i=2; i<Math.sqrt(n); i++ ){
        if (list[i]){
            executor.execute(new Main(i,n));
        }
    }   

    executor.shutdown();
    try {
        executor.awaitTermination(60, TimeUnit.MINUTES);
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }   
    System.out.println("Work time "+(float)(System.nanoTime()-startedTime)/1000000+" s.");

    }

}

Solution

  • It depends a lot on how many cores you have. If you have 2 cores and you want to execute on 7 threads will just make the things slower because of the thread context switching. This is called Amdahl’s law.

    Also is worth mentioning that the first 2 parameters for the executor constructor are corePoolSize and maximumPoolSize java doc corePoolSize means the number of threads to keep in the pool, even if they are idl while maximumPoolSize is the maximum number of threads to allow in the pool

    Anyways the main reason is that the only thing you are measuring is how much it takes for the executor to shut down. You initialize the array with false: list[i]=new AtomicBoolean(false); Then the only situation you create a task for the thread pool is when you find a true element if (list[i]){. since there is no true element this will never happen so no task will be scheduled/executed.