Using StringBuilder(...) as an identity value in the reduce operations gives unpredictable outcome

Question

The question is straight forward: Why can't we use StringBuilder(...) as identity function in the reduce(...) operations in the java8 streams, but string1.concat(string2) can be used as the identity function?

string1.concat(string2) can be seen as similar to builder.append(string) (though it is understood that there are few differences in these opeations), but I am not able to understand the difference in the reduce operation. Consider the following example:

  List<String> list = Arrays.asList("1", "2", "3"); 
  
  // Example using the string concatenation operation
  System.out.println(list.stream().parallel()
            .reduce("", (s1, s2) -> s1 + s2, (s1, s2)->s1 + s2));

  // The same example, using the StringBuilder
  System.out.println(list.stream() .parallel()
            .reduce(new StringBuilder(""), (builder, s) -> builder
                    .append(s),(builder1, builder2) -> builder1
                    .append(builder2)));
 
 // using the actual concat(...) method
 System.out.println(list.stream().parallel()
            .reduce("", (s1, s2) -> s1.concat(s2), (s1, s2)->s1.concat(s2)));

Here is the output after executing above lines:

 123
 321321321321   // output when StringBuilder() is used as Identity
 123

builder.append(string) is an associative operation as str1.concat(str2) is. Then why does concat work and append doesn't?

Answer 1

Yes, append is indeed associative, but that is not the only requirement for the function passed as the accumulator and combiner. According to the docs, they have to be:

• Associative
• Non-interfering
• Stateless

append is not stateless. It is stateful. When you do sb.append("Hello"), not only does it return a StringBuilder with Hello appended to the end, it also changes the contents (i.e. the state) of sb.

Also from the docs:

Stream pipeline results may be nondeterministic or incorrect if the behavioral parameters to the stream operations are stateful. A stateful lambda (or other object implementing the appropriate functional interface) is one whose result depends on any state which might change during the execution of the stream pipeline.

Also because of this, new StringBuilder() is not a valid identity, once the accumulator or the combiner has been applied. Something would have been added to the empty string builder, and the following equation, which all identities must satisfy, is no longer satisfied:

combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)

It is possible that the parallel stream makes use of the old string builders after calling the accumulators and/or combiners, and expects their contents to not be changed. However, the accumulators and combiners mutate the string builders, causing the stream to produce incorrect results.

On the other hand, concat satisfies all three of the above. It is stateless because it does not change the string on which it is called on. It just retunes a new, concatenated string. (String is immutable anyway and can't be changed :D)

Anyway, this is a use case of mutable reduction with collect:

System.out.println((StringBuilder)list.stream().parallel()
    .collect(
        StringBuilder::new, 
        StringBuilder::append, 
        StringBuilder::append
    )
);

Answer 2

After read the doc and do many tests, I think reduce is something like following steps:

1. there will be multi threads to do the reduce, every thread do a partial reduce;
2. for identity, there will be only one instance. Every accumulator will use this identity instance;
3. first do accumulate with identity instance and a string element to get a StringBuilder;
4. combine all these StringBuilders;

so the problem is every accumulate with identity instance and a string element will cause identity changed. the identity in the accumulates after first time is not identity anymore.

for example, we consider an list with 2 element {"1","2"}. there will be 2 threads and every thread do 1 accumulate and one of them do last combine. thread A do accumulate identity with element "1", then result is a StringBuilder which content is "1"(still be the identity, becuase return object of StringBuilder.append is itself), but identity also changed to content "1". then thread B do accumulate identity with element "2", then result is "12", not "2" any more. then do combine is the result of these two accumulate result, they are all the identity instance itself, so the result will be "1212". It like following code snippet:

StringBuilder identity = new StringBuilder();
StringBuilder accumulate1 = identity.append("1");
StringBuilder accumulate2 = identity.append("2");
StringBuilder combine = accumulate1.append(accumulate2);
// combine and accumulate1 and accumulate2 are all identity instance and result is "1212"
return combine; 

for more elements, because of threads running randomly, the result will different every time.

after we know the reason, if we fix the accumulator as following

new StringBuilder(builder).append(s)

and full line code will like:

System.out.println(list.stream().parallel().reduce(new StringBuilder(), (builder, s) -> new StringBuilder(builder).append(s),
        (builder1, builder2) -> new StringBuilder(builder1).append(builder2)));

then there will be no issue any more because accumulator will not change identity instance and return new StringBuilder every time. But it is not worth to do this as no benefit comparing with String concat method.

Edit: Thanks @Holger's example, seems if there is filter function, then some accumulators may be skipped. so the combiner function also need be changed to

new StringBuilder(builder1).append(builder2)

Answer 3

Don't use the .reduce() when there is already an implemantion (or own .collect() like Sweeper's answer).

List<String> list = Arrays.asList("1", "2", "3"); 
  
// Example using the string concatenation operation
System.out.println(list.stream()
   .parallel()
   .collect(Collectors.joining())
);
// prints "123"

Edit (this will not work for parallel streams)

Depends on of the implementation of .joining():

final List<String> list = Arrays.asList("1", "2", "3");
System.out.println(list.stream().reduce(new StringBuilder(), 
    StringBuilder::append, 
    StringBuilder::append)
    .toString()
);
// prints "123"