How does newly introduced Arrays.parallelPrefix(...) in Java 8 work?

Question

I came across Arrays.parallelPrefix introduced in Java 8.

This overloaded method performs operation on each element of the input array in a cumulative fashion. For e.g. from docs:

Cumulates, in parallel, each element of the given array in place, using the supplied function. For example if the array initially holds [2, 1, 0, 3] and the operation performs addition, then upon return the array holds [2, 3, 3, 6]. Parallel prefix computation is usually more efficient than sequential loops for large arrays.

So, how does Java achieve this task in parallel when the operation on a term is dependent on the operation result on the previous term, and so on?

I tried going through the code myself and they do use ForkJoinTasks, but it's not so straightforward how they would merge result to get the final array.

Answer 1

The main point is that the operator is a

side-effect-free, associative function

This means that

(a op b) op c == a op (b op c) 

Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.

Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:

[2, 3]    and    [0, 3] 

Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:

[2, 3, 3, 6] 

EDIT: This answer suggests one way of computing the prefixes of an array in parallel. It's not necessarily the most efficient way, and not necessarily the way used by the JDK implementation. You can further read about parallel algorithms for solving that problem here.