Exploiting concurrency with IteratorSpliterator of unknown size

[Brian Goetz]

“More control over splitting heuristics” has been a repeated request.   Our split heuristics are tuned for low-latency, low-Q.  Folks who are looking for IO parallelism rather than data parallelism, or have low-N high-Q problems, will find them ill-tuned.  

The obvious question is “why not just make it a pluggable API, then?”  In a perfect world, we would have.  But we felt it was more important to get a clean, simple API out the door so people had *something*, and delaying 8 further for this would have been a poor choice.  

Its on our list to explore what we can do to improve things for problems that don’t fit into the sweet spot of the current approach.  

On Mar 24, 2014, at 8:20 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:

> On Mar 24, 2014, at 3:12 PM, Marko Topolnik <marko.topolnik at gmail.com> wrote:
>>> The approach to extract parallelism from a sequential source was designed
>> to
>>> not particularly favour one scenario over another (cost per element, #
>> elements,
>>> reduction), and we did not want to expose any controls like the
>> arithmetic
>>> progression properties since most people won't know what to do with these
>>> (in hindsight this might have been OK on the
>> Spliterators.AbstractSpliterator
>>> implementation).
>> 
>> What I would generally like to find in the library is some sort of a
>> template
>> (abstract class) to make a custom spliterator policy easier to implement. I
>> realize it is not trivial to get such an API right, making it serve as many
>> needs
>> as possible without an explosion of complexity.
>> 
> 
> That is exactly what Spliterator is for; we cannot know all splitting policies and provide partial implementations.
> 
> 
>> In the specific example of BufferedReader.lines there is the additional
>> issue of
>> the anonymous Iterator implementation which is burried in the lib.
>> 
> 
> Note that we could (and probably should) also implement that Spliterator directly leveraging Spliterators.AbstractSpliterator to reduce the layering, but still if you look at the code you will notice some internal layering with respect to managing results from calling tryAdvance when splitting.
> 
> 
>> On a more general level, the problem may be with the way a Spliterator
>> couples
>> the concerns of splitting and iteration. A Spliterator based on the classic
>> Iterator
>> solves a part of this problem because iterating is delegated to a separate
>> object;
>> however the Iterator interface itself is quite cumbersome because it forces
>> us to
>> prefetch the next item and cache it when hasNext is called.
>> 
> 
> Yes, that is one reason why we did not base Spliterator on Iterator. We did not have a compelling use-case to separate out the iteration from splitting.
> 
> 
>> So if there was a partial Spliterator interface (which Spliterator itself
>> would then
>> extend) which had only tryAdvance and forEachRemaining,
> 
> I get what you are saying but that is just a Spliterator that does not split :-)
> 
> 
>> and if an
>> implementation of that could be directly obtained from BufferedReader and
>> other similar objects,
>> then perhaps providing our own Spliterator implementation in terms of that
>> would be
>> nicer.
>> 
> 
>>> Unfortunately in your case i am assuming the cost-per-line is a dominant
>>> factor over number lines to be processed.
>> 
>> Yes, that is what's happening. There is one other thing I'm wondering about:
>> couldn't the ArraySpliterator returned from IteratorSpliterator be further
>> split into
>> smaller chunks?
> 
> Yes, possibly (see below for why not for streams).
> 
> 
>> Generally, how do the "recursive decomposition" mechanics
>> play
>> out in our scenario here?
>> 
> 
> We are getting into gritty details of the implementation... 
> 
> If a size estimate of the root spliterator is known then a threshold is calculated so that a spliterator is no longer split if it's size estimate is below that threshold. For something like an ArrayList this will create a balanced tree where the leaf nodes are in proportion to the targeted parallelism level of the fork/join common pool.
> 
> In your situation it is a worst case scenario :-) a sequential source of unknown size, This will create a right balanced tree, each left leaf node is a prefix of elements copied into an array. Because the size is unknown the Spliterator wrapping that array will not be split. Splitting of the right tree nodes will occur until a null is returned (i.e. when there are no more elements). Reduction operations can perform poorly on such trees due to the imbalance.
> 
> Generally the technique of splitting from a sequential source is to try and ramp up quickly extracting out some work to warm things up while in parallel further splitting (safely) from the source. As you have found out YMMV.
> 
> Paul.
>