Spliterator

[Doug Lea]

On 12/20/12 04:14, Paul Sandoz wrote:
> On Dec 19, 2012, at 3:38 PM, Doug Lea <dl at cs.oswego.edu> wrote:
>>
>> Do you have any existing examples of Spliterators that return values other
>> than 1/0? That might help.
>>
>
> In the source code there is something called a SpinedBuffer that has better
> resizing characteristics than ArrayList but only supports addition of
> elements (no removal of).
>
> SpinedBuffer holds an array of arrays (the spine), the size of individual
> arrays increases by some power of 2 as one goes down the spine.
>
> A Spliterator, that has not been split, of SpinedBuffer returns N - 1 for the
> natural splits when N > 1, where N is the number of arrays in the spine.
>

This is a good illustration the kind of Spliterator
that supporting getNaturalSplits encourages.

The best performing spliterator for such a class would
keep dividing the range of spines by two, and then
if asked, divide each array within sub-splits.
Doing this allows good scale-free performance.
That is, it has a chance of working well no
matter haw many cores you have. (This is why
recursion and FJ are so heavily linked.)

But the way it is now, given how this is supported in
stream pipelines, it will blindly either over- or under- partition;
possibly by enough to eliminate parallel speedups.

If people want to write highly unbalanced spliterators,
we cannot stop them. And in fact for hopelessly listy
things like most Queues, the only plausible default is
to split in the most imbalanced way possible,  head::tail.

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.

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

-Doug