parallel streams

the picture

you know how .parallel() is one word and looks like free speed? it isn't free. splitting the work, waking threads, handing chunks around and merging the answers all cost time, and you only come out ahead if the actual work is bigger than that overhead.

think of grading a pile of exams. with a hundred exams and five teaching assistants, you split the pile and finish five times sooner. with three exams, by the time you've split them up and collected them back, you'd have been done alone. and if every TA writes their tallies on the same whiteboard at the same time, the totals are garbage.

three things in that picture are worth remembering. your own thread works too, it doesn't just wait. splitting is done by the source's Spliterator.trySplit(), so the source decides how well this goes. and nobody hands out work: idle threads steal from the back of busy threads' deques, which keeps everyone busy even when chunks take different amounts of time. more in fork/join and work stealing.

when it's actually faster

rough numbers, so read the shape, not the decimals: best of 10 to 200 runs (after warm-up) timed with System.nanoTime on jdk 25, 14-core arm mac. not JMH.

see the pattern? the prime count does real work per element and wins big. summing a thousand ints takes 0.3 µs sequentially, so parallel's ~2 µs of setup makes it 7 times slower. and the LinkedList barely helps, because a linked list can't split in half without walking to the middle.

Doug Lea's rule of thumb (from his guidance on parallel streams, written with Brian Goetz and others): multiply N (number of elements) by Q (cost per element, roughly in operations). if N × Q isn't at least around 10,000, which is about 100 µs of sequential work, don't bother.

the bug: shared mutable state

this is the one that bites. the lambdas run on several threads at once, so anything they share has to be thread-safe, and ArrayList isn't:

List<Integer> out = new ArrayList<>();
IntStream.range(0, 10_000).parallel().forEach(out::add);
IO.println(out.size());   // one run printed 4458

the fix isn't a synchronized list (that works, and serializes the whole thing, so why go parallel). the fix is to let the stream build the result, so each chunk builds its own piece and the pieces are merged:

import java.util.*;
import java.util.stream.*;
 
void main() {
    List<Integer> good = IntStream.range(0, 10_000).parallel().boxed().toList();
    IO.println(good.size() + " " + good.getFirst() + " " + good.getLast());
}

10000 0 9999

same rule as reduction: describe the result, don't mutate your way to it. the race itself is explained frame by frame in race conditions.

order

a parallel stream still knows the encounter order of its source, and some operations promise to respect it. that promise costs coordination.

import java.util.stream.*;
 
void main() {
    IntStream.range(0, 8).parallel().forEachOrdered(i -> IO.print(i + " "));
    IO.println();
    IO.println(IntStream.range(0, 100).parallel().filter(i -> i > 50).findFirst().getAsInt());
}

0 1 2 3 4 5 6 7 
51

forEach makes no promise: one run of IntStream.range(0, 8).parallel().forEach(...) printed 5 4 0 1 2 3 6 7, the next 5 7 6 1 4 2 3 0. forEachOrdered and findFirst give the sequential answer, but threads have to wait for each other to do it. if you don't care which element you get, findAny() is cheaper, and .unordered() tells limit, distinct and friends they can stop caring too.

IO.println(IntStream.range(0, 1000).parallel()
        .boxed()
        .limit(3)
        .toList());