What is a Spliterator and why does it matter for parallelism?

Every stream is backed by a Spliterator. Sequentially it behaves like an iterator via tryAdvance/forEachRemaining; in parallel the framework calls trySplit recursively to build the task tree.

Its characteristics (SIZED, SUBSIZED, ORDERED, DISTINCT, SORTED, IMMUTABLE, NONNULL) are what the pipeline optimises against. An array spliterator is SIZED and SUBSIZED, so splits are exact and free. A linked list's reports the same flags, but its trySplit has to walk the nodes and copy a batch into an array, and the batches start small and grow, so every split costs a traversal and the halves are uneven.

If you write a custom data source and want parallel streams over it to be worth anything, implementing trySplit and reporting accurate characteristics is the work. The default from Spliterators.spliteratorUnknownSize splits poorly on purpose.