CODEWITHSUNDEEP
javaparallel-processingjava-8java-stream
Timo Türschmann
Timo Türschmann

Reputation: 4696

Why is the result of a reduction different for a sequential and a parallel stream?

I have the following list integers (all numbers from 0 to 999,999):

List<Integer> integers = new ArrayList<>();
for (int i = 0; i != 10_000_000; ++i) {
    integers.add(i);
}

I'm trying to run the following as a Java 8 Stream:

int sum = 0;
for (Integer i : integers) {
    sum = i % 2 == 0 ? i - sum : i + sum;
}
System.out.println(sum);

I expect the following output:

0 - 0 = 0  
1 + 0 = 1  
2 - 1 = 1   
3 + 1 = 4  
4 - 4 = 0  
5 + 0 = 5  
6 - 5 = 1  
7 + 1 = 8
8 - 8 = 0   
...
999,998 - 999,997 = 1
999,999 + 1 = 10,000,000

10,000,000(btw, can someone maybe express this mathematically? I can't...)

If I run this:

int sum = integers.stream().reduce(
                0,
                (sum, i) -> i % 2 == 0 ? i - sum : i + sum
            );

sum is the expected amount, 10,000,000.

However, if I change the stream to being parallel:

int sum = integers.parallelStream().reduce(
                0,
                (sum, i) -> i % 2 == 0 ? i - sum : i + sum
            );

sum is 0!

I can't seem to figure out why this is the case, can someone explain this?

Upvotes: 2

Views: 143

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200168

Javadoc for reduce:

Performs a reduction on the elements of this stream, using an associative accumulation function,

Note the word "associative": this is a property your reducing function does not possess.

Associativity is key to parallelization: the order of application of operations is not defined, and without associativity the result will not be invariant under reordering.

If you have more than two availableProcessors, you can play with the following code to convince yourself that the answer depends on the number of subtasks (note that you shouldn't use 10_000_000 as the problem size because it has to many two's in its factorization; use 10_000_001):

System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism", "2");
System.out.println(IntStream.range(0,10_000_001).parallel().reduce(0,
    (sum, i) -> i % 2 == 0 ? i - sum : i + sum
));

As you change the value of the system property, the result also changes.

Upvotes: 6

Related Questions