How does a parallel stream divide its source for parallel processing, and why does the source's data structure affect performance?
answer
- Spliterator.trySplit() recursively halves the source into a tree of chunks
- arrays / ArrayList / IntStream.range split O(1) and balanced → great
- LinkedList walks to split → unbalanced, poor
- Stream.iterate / lines() are sequential → essentially unsplittable
- SIZED + SUBSIZED characteristics enable balanced pre-sizing
basics
~20 sA parallel stream uses a Spliterator, whose trySplit() repeatedly cuts the source into halves so different threads can process them. Sources that split cheaply and evenly — arrays and ArrayList — parallelize well; LinkedList and Stream.iterate split poorly, so parallelism barely helps.
solid answer
~50 sBehind every stream is a Spliterator ("splittable iterator"). For parallelism, the framework calls its trySplit(), which carves off a portion of the remaining elements into a second Spliterator; this recurses, building a tree of chunks distributed to fork/join workers. The cost and quality of that split is everything. Index-addressable, size-known sources — arrays, ArrayList, IntStream.range — split in O(1) into near-equal halves, so work is balanced and overhead is tiny. A LinkedList has no random access, so it can only split by walking nodes, producing unbalanced or expensive splits. Stream.iterate and BufferedReader.lines are essentially sequential — each element depends on the previous, so trySplit can barely decompose them, and parallelism gives little or no benefit. Spliterator characteristics like SIZED, SUBSIZED, and ORDERED also tell the framework whether it can pre-allocate and balance splits. Bottom line: prefer well-splittable sources for parallel streams.
go deeper
Aware that parallel streams split the data into chunks for different threads.
Knows arrays/ArrayList parallelize better than LinkedList and that some sources (iterate) barely split.
Explains the Spliterator/trySplit mechanism, why index-addressable SIZED sources split cheaply and evenly, and why sequential sources are effectively unsplittable.
Reasons about Spliterator characteristics (SIZED/SUBSIZED/ORDERED) when designing custom data sources, and decides when converting an ill-splittable source into an array is worth the copy.
## The Spliterator Every Java stream is backed by a **Spliterator** — literally a *splittable iterator*. An ordinary `Iterator` only goes forward one element at a time. A `Spliterator` adds the crucial ability to **split**: its `trySplit()` method tries to hand off a *prefix* of its remaining elements as a brand-new Spliterator, leaving itself the rest. (`trySplit()` returns `null` when it cannot or will not split further.) ## How splitting drives parallelism Parallel streams are built on fork/join divide-and-conquer. The framework starts with the source's Spliterator and repeatedly calls `trySplit()`, producing a *tree* of sub-spliterators, each covering a slice of the data. Each leaf slice becomes a fork/join task that processes its elements; the partial results join back up the tree. Good parallelism therefore requires splits that are **cheap** (fast to perform) and **balanced** (roughly equal-sized halves), so every worker thread gets comparable work and no overhead dominates. ## Why the data structure matters Whether `trySplit()` is cheap and balanced depends entirely on the source: - **Arrays, `ArrayList`, `IntStream.range(...)`** — backed by a contiguous, index-addressable block of known size. Splitting is just *"you take indices 0..n/2, I keep n/2..n"* — O(1), perfectly balanced, and the framework knows the exact sizes up front. These parallelize **excellently**. - **`LinkedList`, most `Set`/`Map` implementations** — no random access. To split, the Spliterator must *walk* the structure, which is slow and tends to produce **unbalanced** chunks. Parallel gains are modest at best. - **`Stream.iterate(seed, f)`, `BufferedReader.lines()`, generators** — fundamentally *sequential*: element *n* can only be produced after element *n−1*. They are effectively **unsplittable** — `trySplit()` can hand off almost nothing — so going parallel adds overhead with little or no speedup. (`Stream.generate` is similarly poor.) Prefer `IntStream.range` over `Stream.iterate` when you need a parallel numeric range. ## Spliterator characteristics A Spliterator advertises **characteristic flags** that let the framework optimise: - `SIZED` — the exact element count is known (enables balanced pre-sizing). - `SUBSIZED` — every child produced by `trySplit` is also SIZED (enables clean recursive balancing). - `ORDERED` — elements have a defined encounter order (affects whether order-sensitive ops add cost). - `IMMUTABLE`/`CONCURRENT` — whether the source can be safely traversed without interference. Sized, subsized sources (arrays, `ArrayList`) give the framework everything it needs to balance well; sources lacking these characteristics force conservative, less efficient splitting. ## Practical rule For parallel streams, **choose a well-splittable source**: arrays, `ArrayList`, or primitive ranges. Avoid `LinkedList`, `Stream.iterate`, and stream sources that are inherently sequential — if the data only exists in such a form, consider copying it into an array/`ArrayList` first when the per-element work justifies it.
- Why does Stream.iterate(0, n -> n + 1).parallel() barely benefit from parallelism, while IntStream.range(0, n).parallel() does?Stream.iterate is inherently sequential — each value depends on the previous, so its Spliterator cannot meaningfully split. IntStream.range is index-based and SIZED, so trySplit halves the index space in O(1) into balanced chunks that distribute cleanly across workers.
- What do the SIZED and SUBSIZED Spliterator characteristics let the framework do?SIZED means the exact element count is known, so the framework can pre-size buffers and balance splits; SUBSIZED guarantees every split child is also exactly sized, enabling clean recursive balancing all the way down the split tree.
saying these in an interview costs you the question
- Assuming any source parallelizes equally well — splittability varies hugely by data structure.
- Using Stream.iterate for a parallel numeric range instead of IntStream.range.
- Thinking trySplit splits one element at a time — it hands off a whole prefix and recurses.
- Ignoring that splitting a LinkedList in parallel can cost more than the sequential traversal it replaces.