Is .collect guaranteed for parallel threads?

Question

Given that I have a list of strings List<String> toProcess . The results should be in the order indicated in the source lines. I want to use new parallel threads.

Does the following code provide that the results will be in the same order as they were in the original list?

 // ["a", "b", "c"] List<String> toProcess; // should be ["a", "b", "c"] List<String> results = toProcess.parallelStream() .map(s -> s) .collect(Collectors.toList()); 

Answer 1

TL; DR

Yes, the order is guaranteed.

API documentation Stream.collect ()

The starting point is to look at what determines whether the reduction is simultaneous or not. Stream.collect() description says the following:

If the stream is parallel and Collector is concurrent , and either the stream is unordered or the collector is unordered , then parallel reduction will be performed (see Collector for more information on parallel reduction.)

The first condition is fulfilled: the flow is parallel. What about the second and third: is Collector simultaneous and disordered?

API Documentation Collectors.toList ()

toList() documentation reads:

Returns a Collector that accumulates input elements in a new List . There are no guarantees regarding the type, variability, serializability or security of List streams; if more control is required on the returned List , use toCollection(Supplier) .

Returns:
a collector that collects all input elements into a list in the order of meeting

An operation that works in search order works with elements in their original order. This cancels concurrency.

Implementation code

Checking the implementation of Collectors.java confirms that toList() contains no CONCURRENT or UNORDERED .

 public static <T> Collector<T, ?, List<T>> toList() { return new CollectorImpl<>((Supplier<List<T>>) ArrayList::new, List::add, (left, right) -> { left.addAll(right); return left; }, CH_ID); } // ... static final Set<Collector.Characteristics> CH_ID = Collections.unmodifiableSet(EnumSet.of(Collector.Characteristics.IDENTITY_FINISH)); 

Note that the collector has a feature set CH_ID , which has only one feature IDENTITY_FINISH . CONCURRENT and UNORDERED do not exist, so the reduction cannot be parallel.

Noncompetitive reduction means that if the flow is parallel, the collection can continue in parallel, but it will be divided into several intermediate results with flow restriction, which are then combined. This ensures that the combined result is in the search order.

See also: Why concurrent thread builds sequentially in Java 8

Answer 2

You are guaranteed to receive items in the search order.

From the toList documentation :

Returns: a collector that collects all input elements in a list, in the order of meeting

See java.util.streams for more information on the term meeting order.

In addition, the List#spliterator documentation requires that all List implementations produce separators that are ORDERED :

The separator reports Spliterator.SIZED and Spliterator.ORDERED. Implementations must document the reporting of additional attribute values.

Oddly enough, while the List interface requires iterator() to create the items in the "correct sequence", spliterator() only needs to be ordered, but it is not necessary to follow the natural ordering of the list.

So, to answer your question, the list created by toList is guaranteed to contain elements, such as the original list . It does not matter if the stream is parallel or sequential.