Why calling the reduce method in the parallel stream with a mutable object as identity does not reserve the order in the result?

Question

There is the following seemingly "correct" code:

List<String> list = Arrays.asList("1","2","3","4","5","6",
    "7","8","9","10","11","12");
String result = list.parallelStream()
   .reduce(new StringBuilder(), StringBuilder::append, 
       StringBuilder::append).toString();
System.out.println(result);

The problem of this snippet is that the identity, new StringBuilder(), in the reduce method call is mutable, thus the result is undermined, i.e. the order of the result does not preserve. But I cannot fully understand the reason, thus I am not able to visualize a case of producing the result with in the different order from the original list. So I drew the corresponding map-reduce diagram, which by chance got the result preserving the order:

Question: First, I would like to confirm this diagram is correct. Second, if this diagram is correct, I would like to know where is the cause for this code snippet not always producing the result preserving the order

Answer 1

Your diagram is not correct - you assume that each parallel reduction starts with a new StringBuilder. Instead of that each parallel reduction starts with the same identity element - with the same StringBuilder (the one that you create and pass as the first parameter to the reduce method).

Each parallel stream calls StringBuilder.append on the (one and only) StringBuilder that you pass to the reduce method, thereby appending the currently encountered element to it.

The next step is combining partial results, also by calling StringBuilder.append on the same StringBuilder, appending copies of the contents of the StringBuilder onto itself.

---

To create the diagram that you have drawn, you would have to pass a Supplier<StringBuilder> as the first parameter to the reduce operation.

Actually, according to the comment from Holger, this is possible when using Mutable Reduction.

For this you don't call the reduce method, but rather the collect method:

List<String> list = Arrays.asList("1","2","3","4","5","6",
    "7","8","9","10","11","12");
String result = list.parallelStream()
   .collect(StringBuilder::new, StringBuilder::append, 
       StringBuilder::append).toString();
System.out.println(result);