Which one of these two concurrent implementations is a better faster

Question

I've two implementations of generating prime numbers in parallel. The core code is taken from another post here in Stackoverflow.

I'd like to know which one of these implementations is preferred and why? Also if there are better and faster solutions for this?

Implementation 1:

import java.util.Scanner;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class PrimeThreads {

    private static int currentPrime = 0;

    public static void main(String[] args) {

        Object lock = new Object();

        Thread primerGenThread = new Thread(() -> {
            String threadName = Thread.currentThread().getName();
            System.out.println("Starting thread: " + threadName);
            int currentPrimeNo = 0;
            synchronized (lock) {
                try {
                    currentPrimeNo = generateNextPrime();
                } catch (InterruptedException e) {

                    e.printStackTrace();
                }
            }
            System.out.println("Prime Number Associated with this thread " + threadName + " is: " + currentPrimeNo);
            System.out.println("Completed thread: " + threadName);
        });

        System.out.println("****This is where the project starts*****");

        Scanner reader = new Scanner(System.in);
        System.out.print("Enter number of threads you want to create: ");
        int n = reader.nextInt();
        reader.close();

        ExecutorService executor = Executors.newFixedThreadPool(n);
        for(int i=1;i<=n; i++) {
            executor.submit(primerGenThread);
        }
        executor.shutdown();
        try {
            executor.awaitTermination(10, TimeUnit.MINUTES);
        } catch (InterruptedException e1) {
            e1.printStackTrace();
        }
        System.out.println("****This is where the project ends*****");

    }

    private static int generateNextPrime() throws InterruptedException {

        long startTime = System.nanoTime();

        currentPrime++;
        if (currentPrime < 2) {
            currentPrime = 2;
            return currentPrime;
        }
        for (int i = 2; i < currentPrime; i++) {
            if (currentPrime % i == 0) {
                currentPrime++;
                i = 2;
            } else {
                continue;
            }
        }       

        long endTime = System.nanoTime();
        System.out.println("Time taken: " + (endTime - startTime) + " naoseconds.");
        return currentPrime;
    }

}

And implementation 2:

import java.util.Scanner;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class PrimeAsyncThreads {

    private static int currentPrime = 0;

    public static void main(String[] args) {

        System.out.println("****This is where the project starts*****");

        Scanner reader = new Scanner(System.in);
        System.out.print("Enter number of threads you want to create: ");
        int n = reader.nextInt();
        reader.close();

        ExecutorService executor = Executors.newFixedThreadPool(n);

        for (int i = 1; i <= n; i++) {
            CompletableFuture.supplyAsync(() -> {
                try {
                    return generateNextPrime();
                } catch (InterruptedException e) {

                    e.printStackTrace();
                }
                return n;
            }, executor).thenAccept(s -> System.out.println("Prime Number Associated with this thread "
                    + Thread.currentThread().getName() + " is: " + currentPrime));
        }

        executor.shutdown();

        try {
            executor.awaitTermination(10, TimeUnit.MINUTES);
        } catch (InterruptedException e1) {
            e1.printStackTrace();
        }

        System.out.println("****This is where the project ends*****");
    }

    private static int generateNextPrime() throws InterruptedException {

        long startTime = System.nanoTime();

        currentPrime++;
        if (currentPrime < 2) {
            currentPrime = 2;
            return currentPrime;
        }
        for (int i = 2; i < currentPrime; i++) {
            if (currentPrime % i == 0) {
                currentPrime++;
                i = 2;
            } else {
                continue;
            }
        }

        long endTime = System.nanoTime();
        System.out.println("Time taken: " + (endTime - startTime) + " naoseconds.");
        return currentPrime;
    }
}

Appreciate your suggestions and helps.

EDIT: Also noticed that the second implementation does not guarantee that each thread will get a new prime. In this case sometimes multiple threads get the same value of currentPrime variable.

Thanks.

Answer 1

The main difference between these implementations is how they are executed.

Implempentation 1 is basically equal to a sequential execution. There is no advantage of using threads because how the synchronized block is used. Every thread waits for the previous thread to complete before the next prime is generated.

You already noticed that Implementation 2 calculates the same prime multiple times. This is because there is no synchronization. Only the counter currentPrime is used to have some way of control which number should be considered as prime in the next thread.

Hence, both implementations are not able to calculate primes in parallel to produce a viable result.

Think about the routine. You use a value to determine if its a prime number. This value should be the input for every thread to do the calculation. Now the only thing to consider is how to make this value thread safe to make sure it is only used once.

This can be achived, e.g. by using an Atomic variable for currentPrime.

Another improvement could be to increment currentPrime outside the generateNextPrime() method. This method could take the value as a parameter. Something like

generateNextPrime(currentPrime.incrementAndGet());