How does Spliterator.trySplit() work, and what makes a good split for parallel streams?
answer
- ORDERED: new spliterator takes a strict prefix
- Balanced + cheap = good split (array index halving)
- null for any reason; pipeline also stops early
- Recursive split tree fed to common ForkJoinPool
- SUBSIZED lets leaves fill one shared array
basics
~20 strySplit() tries to hand off some of the remaining elements, ideally half, to a brand-new Spliterator and keeps the rest for itself, so two threads can work on the two parts at once. If it can't usefully split, it returns null.
solid answer
~50 strySplit() is how a parallel stream divides work. The returned new Spliterator covers part of the remaining elements (ideally about half, and a strict prefix if the source is ORDERED), and this Spliterator keeps the rest. The parallel pipeline calls it recursively, building a tree of chunks fed to workers in the common ForkJoinPool, then combines results. A good split is balanced, so no thread is starved, and cheap to compute. trySplit may return null for any reason, such as too few elements, and the pipeline also stops asking once a chunk falls below its own target size, running it sequentially. Array-backed sources (ArrayList, arrays) split beautifully because you just halve an index range; a LinkedList copies a batch from its head on each split, so parallelism helps it only when per-element work costs more than that copying. SIZED means the size is exact before splitting, and SUBSIZED keeps it exact in every child, which lets a parallel toArray fill one preallocated array.
go deeper
Can say trySplit divides the work into two parts so two threads can run, and returns null when it can't split.
Explains that on an ORDERED source trySplit returns a new Spliterator for a prefix while this keeps the rest, and that arrays split better than linked lists.
Describes the recursive split tree into the ForkJoinPool, what makes a split good (balanced + cheap, with SIZED/SUBSIZED for preallocation), and when trySplit returns null.
Reasons quantitatively about when parallelism pays off (split cost vs per-element cost vs N), what the SUBSIZED guarantee buys, and chooses or designs Spliterators accordingly for a given workload.
## What `trySplit` does, precisely The signature is: ```java Spliterator<T> trySplit(); ``` When called, it **attempts to partition** the elements this Spliterator would traverse into two groups: - It **returns a new Spliterator** covering some of the remaining elements, which must be a **strict prefix** if this Spliterator is `ORDERED`. - **`this`** Spliterator is left covering the **rest**. So after `Spliterator<T> a = original.trySplit();` on an `ORDERED` source, the elements have been divided: `a` will traverse the first part, and `original` will traverse the second part, with **no overlap and nothing lost**. If, instead, splitting is impossible or not worth it, it returns **`null`** and `original` is unchanged. Contract rules worth knowing: - The Javadoc calls an exact halving, without traversal, the **ideal**. It requires no ratio and says many departures stay effective, while large imbalance or an inefficient `trySplit` typically means poor parallel performance. - Unless the Spliterator covers an infinite number of elements, repeated calls must eventually return `null`. - For a `SUBSIZED` Spliterator, `estimateSize()` before the split must equal the sum of the two after it. For any other, neither may exceed the value before. ## Why splitting enables parallelism A parallel stream does **not** know about threads at the source level. Instead, the framework recursively splits the root Spliterator into a **tree** of chunks: ``` [0..1000) / \ [0..500) [500..1000) / \ / \ [0..250) [250..500) ... and so on ``` Each leaf chunk is submitted as a task to the **common ForkJoinPool** (a shared thread pool whose default parallelism is one less than the number of available processors, and at least 1). Workers process leaves in parallel via `forEachRemaining`/`tryAdvance`, then the partial results are **combined** back up the tree (this is the fork/join "divide and conquer" pattern). The Spliterator's job is purely **decomposition**; the pool does the execution. ## What makes a *good* split 1. **Balanced.** If `trySplit` always peeled off one element and kept the rest, one worker would do almost everything — no parallel speedup, just overhead. Halving gives every worker comparable work. 2. **Cheap.** The split itself should be fast. For an array-backed source, splitting is just arithmetic on an index range (`mid = (lo + hi) >>> 1`) — O(1). That is why `ArrayList`, arrays, and `IntStream.range` parallelize extremely well. 3. **Honest about size.** If the source reports the **`SIZED`** characteristic (exact remaining count) and **`SUBSIZED`** (the children of a split are *also* exactly sized), a parallel `toArray` can allocate one array up front and let every leaf write at its exact offset. The decision to split further rests on `estimateSize()` either way. ## When `trySplit` returns null, and when splitting stops anyway The Javadoc lets it return `null` 'for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations'. - **Too few elements** — `ArrayList`'s returns `null` only below 2 remaining elements. The earlier cut-off belongs to the framework: `AbstractTask` stops calling `trySplit` once `estimateSize()` is down to about the total divided by four times the pool's parallelism, and runs that chunk sequentially. - **Poor splitters that still split** — a `LinkedList` does not walk to a midpoint. Each `trySplit` copies a batch from its head into an array, 1024 elements, then 2048, then 3072, capped at what remains. The split costs O(batch) and a long list's chunks are unbalanced; at 1024 elements or fewer the first split takes everything, leaves `this` empty, and the array then halves evenly. An `Iterator`-wrapping Spliterator batches the same way. - **Exhausted** — nothing left to split. The practical lesson: `list.parallelStream()` needs non-trivial per-element work, and a batching source needs enough of it to outweigh the copying. With trivial work per element, split and merge overhead can make things *slower*. ## Mini example of a custom balanced split ```java class RangeSpliterator implements Spliterator.OfInt { private int cur; private final int end; RangeSpliterator(int start, int end) { this.cur = start; this.end = end; } public boolean tryAdvance(IntConsumer a) { if (cur < end) { a.accept(cur++); return true; } return false; } public OfInt trySplit() { int remaining = end - cur; if (remaining < 2) return null; // not worth splitting int mid = cur + remaining / 2; // balanced midpoint int lo = cur; cur = mid; // this keeps [mid, end) return new RangeSpliterator(lo, mid); // prefix [lo, mid) } public long estimateSize() { return end - cur; } public int characteristics() { return ORDERED | SIZED | SUBSIZED | NONNULL | IMMUTABLE; } } ``` Here splitting is O(1) arithmetic, balanced, and `SIZED|SUBSIZED`, so it parallelizes ideally.
- Why does an ArrayList parallelize better than a LinkedList?ArrayList is array-backed, so trySplit just halves an index range in O(1) and is balanced. A LinkedList has no random access, so each trySplit walks from the head and copies a batch of 1024, then 2048, elements into an array. That costs O(batch) and leaves a long list's chunks unbalanced, so parallelism helps it only when per-element work costs more than the copying.
- What does SUBSIZED add over SIZED?SIZED means estimateSize() is exact before any traversal or split. SUBSIZED adds that every Spliterator from trySplit is also SIZED and SUBSIZED, so sizes stay exact down the split tree, and a parallel toArray can preallocate one array and write at exact offsets. A HashSet reports SIZED, not SUBSIZED, and loses SIZED after a split.
- Saying an ORDERED Spliterator's trySplit returns the second half — it returns a strict prefix; this keeps the rest
- Assuming every source parallelizes well — LinkedList/I/O sources split poorly or return null
- Believing parallelStream is always faster — split/merge overhead can make it slower for trivial work or non-splittable sources
- Thinking a finite Spliterator's trySplit can keep returning non-null forever — it must eventually return null
- Spliterator
- Java 1.8
context
- Spliterator (Java SE 27 & JDK 27)docs.oracle.com
- AbstractTask.java at jdk-27-gagithub.com
- LinkedList.java at jdk-27-gagithub.com