Spliterator

[Brian Goetz]

> But if the idea behind getNaturalSplits is to make it
> easier to implement a crummy Spliterator than a good one,
> then this adds to the reasons not to support this
> method.

I think the idea is more oriented around allowing people other than Doug 
to write (admittedly suboptimal) spliterators for data structures for 
which the optimal binary split is not obvious.

Case in point: TreeMap.  A while back (when all we had was binary 
splits), there was a conversation that went something like this:

Brian: TreeMap should fit nicely into a binary split model.

Doug: Not so fast!  There's data in the nodes.  Which means you have to 
play a game where you decide which subtree gets the node data, and 
encode the path from the root as a bitmap indicating left-vs-right 
(which falls over completely on unbalanced trees.)  Blech.

Brian: Aw, crap.

... time passes ...

Brian: Well, now that we have n-way splits, you can represent this 
trivially (though suboptimally) as (left node, my data, right node).

Doug: Wait, I figured out a way to do it as binary splits.


The moral of the story is: it took Doug+sidekick more than a a few days 
to come up with a clean binary splitting solution.  Which means for many 
developers, they would never get there, and they're locked out of the 
parallelism game for want of a Spliterator.

Stepping back, why do we have Spliterator at all?  Using Spliterator at 
all has a cost -- it is a tradeoff of less efficient element access for 
abstraction.  Highly tuned implementations like CHM do not benefit from 
Spliterator; the abstraction benefit is aimed at allowing arbitrary data 
structures (even non-thread-safe ones, assuming non-interference) to get 
the benefit of all these parallel algorithms at low entry cost.  One 
goal here is to maximize the data structures that can get into the game 
relatively cheaply just by writing a Spliterator.

> As I keep saying though, the main reason to prefer
> isSplittable is that you can write a a simple
> unambiguous spec for it.

Will try to write something simpler and unambiguous, and Doug can poke 
holes in it.  Maybe with a few iterations I can have my feature and Doug 
can have his simple spec, and everyone wins.