when calculate a^b why parallel not work but paral

Question

I want to calculate a^b , e.g. 2^30,

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

first I used this manner

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

Got right result. Then I want to calculate it parallelly, so naturally I changed it to

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

but in this case the result is just 32. Why?

So for supporting parallel I changed it again

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

in this case it works.

So what's wrong with parallel manner?

Answer 1

After tracing source code, I finally knew why the result is 32.

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

Related source code

   // 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)
    }

because actually not used x in lambda

(acc, x) -> a * acc;

so the actual effect is like this

leftResult.combine(2); 

Online demo to simulate this phenomenon.

Answer 2

reduce requires that the supplied function be associative. Your function (acc, x) -> a * acc does not satisfy the requirement and thus violates the contract.

To be associative, the function must satisfy (x op y) op z == x op (y op z) for any x, y and z. But for your function, (x op y) op z = x*a^2 while x op (y op z) = x * a.

Furthermore, the first parameter supplied to reduce must be an identity with respect to the accumulator function. So it must be true that 1 op x == x for any x. But that also doesn't hold for your accumulator function since 1 op x == a.

The correct way to do this is:

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

This is guaranteed to work correctly whether the stream is parallel or sequential.