How does trySplit() work, and what makes a good split for parallel streams?

## 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 **prefix** of the remaining elements. - **`this`** Spliterator is left covering the **rest** (the suffix). So after `Spliterator<T> a = original.trySplit();`, 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: - After a successful split the prefix returned should ideally be **about half** the elements (balanced), but the contract only requires a *strict* subset. - Repeatedly calling `trySplit` must eventually return `null` (you can't split forever). - For a `SIZED` Spliterator, the sum of the two halves' sizes must equal the original size. ## 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 sized to the number of CPU cores). 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 must 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), the framework can size buffers and balance load precisely. ## When `trySplit` returns null (poor or no parallelism) - **Too few elements** — below a threshold, splitting overhead outweighs the benefit, so the chunk is processed sequentially. - **Inherently sequential sources** — a `LinkedList` would have to walk to the midpoint just to split (O(n)), so its Spliterator splits poorly; sources backed by I/O or a stateful generator may not split at all and return `null`. - **Exhausted** — nothing left to split. The practical lesson: `list.parallelStream()` is only a win when the source splits cheaply **and** the per-element work is non-trivial. Parallelizing a `LinkedList` or doing trivial work per element often makes things *slower* because of split/merge overhead. ## 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.