在 Java 中正确使用并行流

Question

我正在 Java 中试验并行流，为此我有以下代码用于计算 n 之前的素数。

基本上我有两种方法

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 只是 returns 以毫秒为单位的执行时间。我得到以下输出：

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

现在我正在尝试对上述执行时间进行推理：

PP 变体不如 PNP 变体快，因为所有并行流都使用公共的 fork-join 线程池，如果我们提交一个 long-运行任务，我们是有效地阻塞池中的所有线程。
但上述论点也适用于 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：我知道这不是计算素数的最佳方法。 Sieve of Eratosthenes 和其他更复杂的方法可以做到这一点。但是通过这个例子，我只是想了解并行流的行为以及何时使用它们。

Answer 1

我想，很清楚了，为什么 NPP 这么慢。

将结果数字排列成 table:

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

所以你看到当外部流是并行的时候它总是更快。这是因为流中有很多工作要做。因此，与要完成的工作相比，处理并行流的额外开销很低。

您还看到，当内部流不并行时，它总是更快。 isPrimeNonParallel 比 isPrimeParallel 快。这是因为流中没有太多工作要做。在大多数情况下，经过几步就可以清楚地知道这个数不是质数。一半的数字是偶数（只有一步）。与要完成的工作相比，处理并行流的额外开销很高。

在 Java 中正确使用并行流

Proper usage of parallel streams in Java

java

parallel-processing

java-8

forkjoinpool

java-stream