Why parallel stream get collected sequentially in Java 8

Question

Why forEach prints numbers in random order, while collect always collects elements in original order, even from parallel stream?

Integer[] intArray = {1, 2, 3, 4, 5, 6, 7, 8}; List<Integer> listOfIntegers = new ArrayList<>(Arrays.asList(intArray));  System.out.println("Parallel Stream: "); listOfIntegers   .stream()   .parallel()   .forEach(e -> System.out.print(e + " ")); System.out.println();  // Collectors          List<Integer> l = listOfIntegers   .stream()   .parallel()   .collect(Collectors.toList()); System.out.println(l); 

Output:

Parallel Stream:  8 1 6 2 7 4 5 3  [1, 2, 3, 4, 5, 6, 7, 8] 

Answer 1

There are two different kinds of "ordering" going on here, which makes the discussion confusing.

One kind is encounter order, which is defined in the streams documentation. A good way to think about this is the spatial or left-to-right order of elements in the source collection. If the source is a List, consider the earlier elements being to the left of later elements.

There is also processing or temporal order, which isn't defined in the documentation, but which is the time order in which elements are processed by different threads. If the elements of a list are being processed in parallel by different threads, a thread might process the rightmost element in the list before the leftmost element. But the next time it might not.

Even when computations are done in parallel, most Collectors and some terminal operations are carefully arranged so that they preserve encounter order from the source through to the destination, independently of the temporal order in which different threads might process each element.

Note that the forEach terminal operation does not preserve encounter order. Instead, it's run by whatever thread happens to produce the next result. If you want something like forEach that preserves encounter order, use forEachOrdered instead.

See also the Lambda FAQ for further discussion about ordering issues.

Answer 2

The Collectors.toList method specifies that the returned Collector adds elements to the list in encounter order.

Returns:

a Collector which collects all the input elements into a List, in encounter order

It doesn't matter whether the Stream is parallel; the order is preserved.

Additionally, looking at the Collectors source code, the returned Collector calls addAll on an ArrayList when merging, and that preserves the order. E.g. if one thread has {1, 2} and the next thread has {3, 4}, then the call to addAll yields {1, 2, 3, 4}. Also, the returned Collector doesn't have the UNORDERED characteristic.