Spliterator (original) (raw)

Doug Lea dl at cs.oswego.edu
Thu Dec 20 06:53:20 PST 2012

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

More information about the lambda-libs-spec-experts mailing list