What is the most efficient List-Type for Java parallelStream?

Question

I have a List<String> toProcess which I want to process further with

toProcess.parallelStream().map(/*some function*/).collect(Collectors.toList());

Which is the best List-type (like LinkedList, ArrayList ect.) for the initial list to gain the best speed from this multithreading?

Additional information: The expected element-count ranges in the size of 10^3-10^5, but the individual element can become quite big (10^5-10^6 chars).

---

Alternativly I can use String[] all over the place, as the amount of strings is guaranteed to not change (results will contain as many elements as toProcess).

---

Either way I have to iterate over all elements in order at the end. At the moment I use a foreach-loop to assemble the final result. This can be easily changed to a regular for-loop.

Answer 1

If you are certain that the number of output elements equals the number of input elements, and you're satisfied with an array as the result, then definitely use toArray instead of a collector. If the pipeline has a fixed size throughout, the destination array will be preallocated with the right size, and the parallel operations deposit their results directly into the destination array at the right locations: no copying, reallocation, or merging.

If you want a List, you can always wrap the result using Arrays.asList, but of course you can't add or remove elements to the result.

Collectors

If one of the above conditions doesn't hold, then you need to deal with collectors, which have different tradeoffs.

Collectors work in parallel by operating on intermediate results in a thread-confined manner. The intermediate results are then merged into the final result. There are two operations to consider: 1) the accumulation of individual elements into the intermediate results, and 2) the merging (or combining) of the intermediate results into a final result.

Between LinkedList and ArrayList, it's likely that ArrayList is faster, but you should probably benchmark this to be sure. Note that Collectors.toList uses ArrayList by default, although this may change in a future release.

LinkedList

Each element being accumulated (LinkedList.add) involves allocating a new list node and hooking it to the end of the list. Hooking the node to the list is quite fast, but this involves an allocation for every single stream element, which will probably incur minor garbage collections as accumulation proceeds.

Merging (LinkedList.addAll) is also quite expensive. The first step is to convert the source list to an array; this is done by looping over every node of the list and storing the element into a temporary array. Then, the code iterates over this temporary array and adds each element to the end of the destination list. This incurs allocation of a new node for each element, as noted above. Thus a merge operation is quite expensive, because it iterates over every element in the source list twice and incurs allocation for each element, which probably introduces garbage collection overhead.

ArrayList

Accumulation of each element usually involves appending it to the end of the array contained within the ArrayList. This is usually quite fast, but if the array is full, it must be reallocated and copied into a larger array. The growth policy for ArrayList is to allocate the new array to be 50% larger than the current one, so reallocations occur proportional to the log of the number of elements being added, which isn't too bad. All the elements have to be copied over, however, which means that the earlier elements might need to be copied multiple times.

Merging an ArrayList is probably much cheaper than LinkedList. Converting an ArrayList to an array involves a bulk copy (not one-at-a-time) of the elements from the source into a temporary array. The destination array is resized if necessary (which is likely in this case), requiring a bulk copy of all the elements. The source elements are then bulk-copied from the temporary array to the destination, which has been pre-sized to accomodate them.

Discussion

Given the above, it seems like ArrayList will be faster than LinkedList. However, even collection to an ArrayList requires some unnecessary reallocation and copying of many elements, probably several times. A potential future optimization would be for Collectors.toList to accumulate elements into a data structure that's optimized for fast-append access, preferably one that's been pre-sized to accommodate the expected number of elements. A data structure that supports fast merging is a possibility as well.

If all you need to do is iterate over the final result, it shouldn't be too difficult to roll your own data structure that has these properties. Significant simplification should be possible if it doesn't need to be a full-blown List. It could accumulate into pre-sized lists to avoid reallocations, and merging would simply gather these into a tree structure or list-of-lists. See the JDK's SpinedBuffer (a private implementation class) for ideas.