当计算 a^b 时，为什么 parallel 不起作用但 parallelStream 可以

Question

我想计算 a^b ，例如2^30，

public long pow(final int a, final int  b)

我第一次用这种方式

return LongStream.range(0, b).reduce(1, (acc, x) -> a * acc); // 1073741824

得到正确的结果。那我想并行计算，自然就改成了

return LongStream.range(0, b).parallel().reduce(1, (acc, x) -> a * acc); // 32

但在这种情况下，结果只是 32。为什么？

所以为了支持并行我改了一遍

return Collections.nCopies(b,a).parallelStream().reduce(1, (acc, x) -> acc * x); // 1073741824

在这种情况下有效。

那么 parallel 举止有什么问题？

Answer 1

reduce requires that the supplied function be associative。您的函数 (acc, x) -> a * acc 不满足要求，因此违反了合同。

要具有关联性，函数必须满足 (x op y) op z == x op (y op z) 对于任何 x、y 和 z。但是对于您的函数，(x op y) op z = x*a^2 而 x op (y op z) = x * a。

此外，提供给 reduce 的第一个参数必须是累加器函数的标识。所以对于任何 x，1 op x == x 一定是真的。但这也不适用于您的累加器函数，因为 1 op x == a.

正确的做法是：

LongStream.range(0, b).map(x -> a).reduce(1, (u, v) -> u * v);

无论流是并行的还是顺序的，这都能保证正常工作。

Answer 2

追源码后，终于知道为什么结果是32了

return LongStream.range(0, b).parallel().reduce(1, (acc, x) -> a * acc); // 32

相关源码

   // java.util.stream.ReduceOps.ReduceTask#onCompletion
    @Override
    public void onCompletion(CountedCompleter<?> caller) {
        if (!isLeaf()) {
            S leftResult = leftChild.getLocalResult();
            leftResult.combine(rightChild.getLocalResult()); // here to combine
            setLocalResult(leftResult);
        }

    }

    // java.util.stream.TerminalOp
    @Override
    public void combine(ReducingSink other) {
        accept(other.state);
    }
    @Override
    public void accept(long t) {
        state = operator.applyAsLong(state, t); // (acc, x)
    }

因为实际上没有在 lambda

中使用 x

(acc, x) -> a * acc;

所以实际效果是这样的

leftResult.combine(2);

Online demo来模拟这个现象。

当计算 a^b 时，为什么 parallel 不起作用但 parallelStream 可以

when calculate a^b why parallel not work but parallelStream could

java

parallel-processing

reduce

java-8

java-stream