1
\$\begingroup\$

A number is a prime when it is divisible by 1 and the number itself. To check if a given number is a prime we can divide the number by primes which are less than the square root of that number. If there is at least one prime which properly divide the number then the number is composite otherwise it is a prime number.

I have written a PrimeGenerator class which produces prime when the nextPrime() method is called. While returning the prime the class also stores that prime into an internal list to use during the later calls to the nextPrime() method.

I have two versions of this class:

  • Single-threaded - in this case the prime list divides the number in a single thread.
  • Multithreaded - in this case the prime list get split into sub-lists and every sub-list operate division on that number in different threads. The number of sub-lists and the number of threads is equals to the number of cpu core available.

Single-threaded version:

public class PrimeGeneratorSingleThreaded {
    private List<Integer> primes = new ArrayList<>(Arrays.asList(2, 3));
    private int lastIndex = -1;

    public PrimeGeneratorSingleThreaded() {

    }

    public Integer nextPrime() {
        if (++lastIndex < primes.size()) {
            return primes.get(lastIndex);
        } else {
            int n = primes.get(primes.size() - 1) + 2;

            while (true) {
                boolean primeFound = true;

                int finalN = n;
                int sqrt = (int) Math.sqrt(n) + 1;
                Optional<Integer> optional = primes.stream().filter((Integer i) -> i < sqrt).filter((Integer i) -> (finalN % i) == 0).findFirst();

                if (optional.isPresent()) {
                    primeFound = false;
                }

                if (primeFound) {
                    primes.add(n);
                    break;
                }

                n += 2;
            }

            return primes.get(lastIndex);
        }
    }
}

Multi-threaded version:

public class PrimeGeneratorMultiThreaded {
    int nbCores = Runtime.getRuntime().availableProcessors();
    private List<Integer> primes = new ArrayList<>(Arrays.asList(2, 3));
    private int lastIndex = -1;

    private List<List<Integer>> primePartitions = new ArrayList<>();
    private int lastAdded = 0;

    public PrimeGeneratorMultiThreaded() {
        IntStream.range(0, nbCores).forEach(i -> primePartitions.add(new ArrayList<>()));

        primePartitions.get(0).addAll(primes);
    }

    public Integer nextPrime() {
        if (++lastIndex < primes.size()) {
            return primes.get(lastIndex);
        } else {
            AtomicBoolean compositeFound = new AtomicBoolean(false);

            int n = primes.get(primes.size() - 1) + 2;

            while (true) {
                ExecutorService service = Executors.newFixedThreadPool(nbCores);
                List<Future<?>> workers = new ArrayList<>();
                int finalN = n;
                primePartitions.forEach((List<Integer> list) -> workers.add(service.submit(new DivisionWorker(compositeFound, new Integer(finalN), list))));

                workers.forEach((Future<?> worker) -> {
                    try {
                        worker.get();
                    } catch (Exception ignore) {
                    }
                });

                if (compositeFound.get()) {
                    n += 2;
                    compositeFound.set(false);

                    try {
                        service.shutdownNow();
                    } catch (Exception ignore) {
                    }
                } else {
                    primes.add(n);

                    if (++lastAdded == nbCores) {
                        lastAdded = 0;
                    }

                    primePartitions.get(lastAdded).add(n);

                    try {
                        service.shutdownNow();
                    } catch (Exception ignore) {
                    }

                    break;
                }
            }

            return primes.get(lastIndex);
        }
    }

    private class DivisionWorker implements Runnable {
        private AtomicBoolean compositeFound;
        private int num;
        private List<Integer> list;

        private DivisionWorker(AtomicBoolean compositeFound, int num, List<Integer> list) {
            this.compositeFound = compositeFound;
            this.num = num;
            this.list = list;
        }

        @Override
        public void run() {
            int sqrt = (int) Math.sqrt(num) + 1;
            Optional<Integer> optional = list.parallelStream().filter((Integer i) -> i < sqrt).filter((Integer i) -> compositeFound.get() || (num % i) == 0).findFirst();

            if (optional.isPresent()) {
                compositeFound.set(true);
            }
        }
    }
}

Following is the code snippet to test the generation of first 999 primes:

public class Test {

    public static void main(String[] args) {
        final PrimeGeneratorSingleThreaded primeGeneratorSingleThreaded = new PrimeGeneratorSingleThreaded();
        final PrimeGeneratorMultiThreaded primeGeneratorMultiThreaded = new PrimeGeneratorMultiThreaded();

        IntStream.range(1, 1000).forEach(i -> {
            long startTime1 = System.nanoTime();
            long n = primeGeneratorSingleThreaded.nextPrime();
            long executionTime1 = System.nanoTime() - startTime1;

            System.out.println(String.format("Single=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime1));

            long startTime2 = System.nanoTime();
            n = primeGeneratorMultiThreaded.nextPrime();
            long executionTime2 = System.nanoTime() - startTime2;
            System.out.println(String.format("Multi=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime2));

            System.out.println("==================================\n");
        });
    }
}

The problem

I have uploaded a gist there you can see the multithreaded version is taking more time than that of the single-threaded version. I was expecting that the multithreaded version would be faster, but it is not. Why is this happening?

\$\endgroup\$
  • \$\begingroup\$ Multi-threading doesn't speed up every process you can think off in some magical way. Either your implementation is flawed, the problem isn't easily multi-threaded or the overhead is simply not worth the benefit. \$\endgroup\$ – Mast Aug 14 '16 at 14:43
  • \$\begingroup\$ @Mast, I rechecked the multithreaded solution multiple times, but didn't find any flaws or any way to make it faster. I am suspecting that the extra overhead is taking times. \$\endgroup\$ – Tapas Bose Aug 14 '16 at 14:47
4
\$\begingroup\$

Your single threaded version could use a rewrite...

public Integer nextPrime() {
    if (++lastIndex < primes.size()) {
        return primes.get(lastIndex);
    } else {
        int n = primes.get(primes.size() - 1);

        Optional<Integer> optional = Optional.empty();
        do {
            n += 2;

            int finalN = n;
            int sqrt = (int) Math.sqrt(n) + 1;
            optional = primes.stream().filter((Integer i) -> i < sqrt).filter((Integer i) -> (finalN % i) == 0).findFirst();

        } while(!optional.isPresent());
        primes.add(n);
        return primes.get(lastIndex);
    }
}

The changes are pretty simple - first, relocate the += 2 so that there's no need to do it once for starting the loop and once per iteration. Next, change the loop into a do-while loop, because the first iteration doesn't need a check.

After that, we can see that the break only happens at the bottom. Which means it can be part of the loop condition.

And since the only way to exit the loop was via that break, we can move the adding to primes to outside of the loop.

The result is code which is much more compact and doesn't rely on flags such as primeFound and break.

\$\endgroup\$
3
\$\begingroup\$

Google

Google produces a number of results if you search. E.g. Should I always use a parallel stream when possible? is a top result for "parallelStream".

Test bigger

        IntStream.range(1, 1000).forEach(i -> {
            long startTime1 = System.nanoTime();
            long n = primeGeneratorSingleThreaded.nextPrime();
            long executionTime1 = System.nanoTime() - startTime1;

            System.out.println(String.format("Single=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime1));

            long startTime2 = System.nanoTime();
            n = primeGeneratorMultiThreaded.nextPrime();
            long executionTime2 = System.nanoTime() - startTime2;
            System.out.println(String.format("Multi=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime2));

            System.out.println("==================================\n");
        });

This is a horrid way to test. You never let the algorithm get up to speed. Instead you start up multiple threads and tear down multiple threads on each iteration. Do that work once and let the algorithm chug for a while.

Instead of testing a thousand sequentially and timing each prime, just get the first thousand primes via one method and then the other.

Parallelize disjoint operations

Worse, this suggests that you aren't parallelizing your search. Let's see.

            Optional<Integer> optional = list.parallelStream().filter((Integer i) -> i < sqrt).filter((Integer i) -> compositeFound.get() || (num % i) == 0).findFirst();

Well, that's difficult to read. Let's make it break it up into multiple lines

            Optional<Integer> optional = list.parallelStream()
                .filter((Integer i) -> i < sqrt)
                .filter((Integer i) -> compositeFound.get() || (num % i) == 0)
                .findFirst();

That's much easier to follow.

But why do this in parallel? Let's say you start by doing eight of these in parallel.

So you check if num is divisible by any of 2, 3, 5, 7, 11, 13, 17, or 19. Well, it will never be divisible by 2, because you don't allow num to be even. So that's wasted. One third of the time, it will be divisible by 3. That wastes the remaining six checks.

In any given ten numbers in sequence, three will be divisible by 3 and two will be divisible by five. At most one of those will overlap. So there's no point in checking the others four of ten times. Example:

31
32 divisible by 2
33 divisible by 3
34 divisible by 2
35 divisible by 5
36 divisible by 2
37
38 divisible by 2
39 divisible by 3
40 divisible by 2

So we find two primes but test divide by eight numbers when in fact we only needed to test two numbers (3 and 5). We skip all the even numbers, so there's five gone. There are two numbers divisible by 3 (and not 2). And one number divisible by 5 (and not 2 or 3). Why do forty divisions to find out that we only need to do twenty to get five answers?

Note that findFirst is a short-circuit operation. It ends on the first correct answer.

You might try findAny instead. Note that findFirst has to make sure that all the earlier checks finish. findAny can return the first result found, not the first of the sequence. But I don't think that's the biggest possible improvement.

Rather than parallelizing the division checks, parallelize the candidate generation. Those are disjoint, so checking 31, 33, 35, 37, 39, 41, 43, and 45 at the same time doesn't waste anything. As they fall out, switch in other numbers.

31, 33, 35, 37, 39, 41, 43, 45
31, 47, 35, 37, 49, 41, 43, 51

The second line replaces all the numbers divisible by 3 (33, 39, 45) with new numbers.

At this point, we know that all our original numbers are prime if they're still there, since everything less than 49, we only need to check 3 and 5. So we found 31, 37, 41, and 43. 35 was excluded as a multiple of 5.

Save the last number checked. So we know that 51 and below are not prime after we finish processing. Previously you would have retested 49 and 51 because you start with the last prime.

Obviously at the end, we may waste up to seven unnecessary checks. However, we only do that once for the entire thousand primes. By contrast, your original algorithm wasted checks on every number. In generating the thousandth prime, you only need to test division by twenty-two numbers. The square root of 7919 is less than 89, so the last prime to check is 83.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.