Правильное использование параллельных потоков в Java

Question

Я экспериментирую с параллельными потоками в Java, и для этого у меня есть следующий код для вычисления числа простых чисел перед n,

В основном у меня есть 2 метода

• calNumberOfPrimes(long n) - 4 разных варианта
• isPrime(long n) - 2 разных варианта

На самом деле у меня есть 2 разных варианта каждого из вышеуказанного метода, один вариант, который использует параллельные потоки и другой вариант, который не использует параллельные потоки.

    // itself uses parallel stream and calls parallel variant isPrime
    private static long calNumberOfPrimesPP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .parallel()
                .filter(i -> isPrimeParallel(i))
                .count();
    }

    // itself uses parallel stream and calls non-parallel variant isPrime
    private static long calNumberOfPrimesPNP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .parallel()
                .filter(i -> isPrimeNonParallel(i))
                .count();
    }

    // itself uses non-parallel stream and calls parallel variant isPrime
    private static long calNumberOfPrimesNPP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .filter(i -> isPrimeParallel(i))
                .count();
    }

    // itself uses non-parallel stream and calls non-parallel variant isPrime
    private static long calNumberOfPrimesNPNP(long n) {
        return LongStream
                .rangeClosed(2, n)
                .filter(i -> isPrimeNonParallel(i))
                .count();
    }
    // uses parallel stream
    private static boolean isPrimeParallel(long n) {
        return LongStream
                .rangeClosed(2, (long) Math.sqrt(n))
                .parallel()
                .noneMatch(i -> n % i == 0);
    }

    // uses non-parallel stream
    private static boolean isPrimeNonParallel(long n) {
        return LongStream
                .rangeClosed(2, (long) Math.sqrt(n))
                .noneMatch(i -> n % i == 0);
    }

Я пытаюсь выяснить, какие из calNumberOfPrimesPP, calNumberOfPrimesPNP, calNumberOfPrimesNPP а также calNumberOfPrimesNPNP является лучшим с точки зрения правильного использования параллельных потоков с эффективностью и почему это лучшее.

Я попытался рассчитать все эти 4 метода в 50 раз и взял среднее значение, используя следующий код:

    public static void main(String[] args) throws Exception {
        int iterations = 50;
        int n = 1000000;
        double pp, pnp, npp, npnp;
        pp = pnp = npp = npnp = 0;
        for (int i = 0; i < iterations; i++) {
            Callable<Long> runner1 = () -> calNumberOfPrimesPP(n);
            Callable<Long> runner2 = () -> calNumberOfPrimesPNP(n);
            Callable<Long> runner3 = () -> calNumberOfPrimesNPP(n);
            Callable<Long> runner4 = () -> calNumberOfPrimesNPNP(n);

            pp += TimeIt.timeIt(runner1);
            pnp += TimeIt.timeIt(runner2);
            npp += TimeIt.timeIt(runner3);
            npnp += TimeIt.timeIt(runner4);
        }
        System.out.println("___________final results___________");
        System.out.println("avg PP = " + pp / iterations);
        System.out.println("avg PNP = " + pnp / iterations);
        System.out.println("avg NPP = " + npp / iterations);
        System.out.println("avg NPNP = " + npnp / iterations);
    }

TimeIt.timeIt просто возвращает время выполнения в миллисекундах. Я получил следующий вывод:

___________final results___________
avg PP = 2364.51336366
avg PNP = 265.27284506
avg NPP = 11424.194316620002
avg NPNP = 1138.15516624

Теперь я пытаюсь рассуждать о вышеупомянутых временах выполнения:

• PP вариант не такой быстрый как PNP вариант, потому что все параллельные потоки используют общий пул потоков fork-join и, если мы отправляем долгосрочную задачу, мы фактически блокируем все потоки в пуле.
• Но приведенный выше аргумент также должен работать на NPP вариант и так NPP вариант также должен быть примерно таким же быстрым, как PNP вариант. (Но это не так, NPP вариант худший с точки зрения затраченного времени). Может кто-нибудь объяснить, пожалуйста, причину этого?

Мои вопросы:

• Правильно ли мое рассуждение для малого времени PNP вариант?
• Я что-то пропустил?
• Зачем NPP вариант самый худший (с точки зрения времени работы)?

Как TimeIt измеряет время:

class TimeIt {
    private TimeIt() {
    }

    /**
     * returns the time to execute the Callable in milliseconds
     */
    public static <T> double timeIt(Callable<T> callable) throws Exception {
        long start = System.nanoTime();
        System.out.println(callable.call());
        return (System.nanoTime() - start) / 1.0e6;
    }
}

PS: я понимаю, что это не лучший способ подсчитать количество простых чисел. Для этого существует сито Эратосфена и другие более сложные методы. Но на этом примере я просто хочу понять поведение параллельных потоков и когда их использовать.

Answer 1

Я думаю, понятно, почему АЭС такая медленная.

Расставьте полученные цифры в таблице:

       |    _P    |   _NP
-------+----------+---------
  P_   |   2364   |   265
-------+----------+---------
  NP_  |  11424   |  1138
-------+----------+---------

Итак, вы видите, что всегда быстрее, когда внешний поток параллелен. Это потому, что в потоке еще много работы. Таким образом, дополнительные затраты на обработку параллельного потока невелики по сравнению с выполняемой работой.

Вы также видите, что всегда быстрее, когда внутренний поток не параллелен. isPrimeNonParallel быстрее чем isPrimeParallel, Это потому, что в потоке не так много работы. В большинстве случаев после нескольких шагов становится ясно, что число не простое. Половина чисел четная (только один шаг). Дополнительные издержки на обработку параллельного потока высоки по сравнению с работой, которую необходимо выполнить.