unrdered()

[Paul Sandoz]

On Apr 4, 2013, at 5:00 AM, Brian Goetz <brian.goetz at Oracle.COM> wrote:

> At one point, we had an unordered() op.  I think it may be time to bring it back.
> 
> There are a growing number of ops that have optimized implementations for unordered streams:
> 
>  - distinct can be implemented with concurrent insertion into a CHS instead of merging if we don't care about order.  Not only is this less work (merging is expensive), but it makes distinct lazy (elements can flow through immediately once they've not been found in the CHS, instead of waiting for all the elements to be seen.)
> 
>  - sorted is non-stable in unordered streams.
> 
>  - limit/subsequence are far lighter for unordered streams (and can similarly be made lazy)
> 
> So a way of saying "I know you think this stream has ordering, but I don't care about it" is a way of opting into these optimizations.
> 

Right, we previously thought "well lets just go with what the two ends of the pipeline define in terms of having order and preserving order respectively".

AFAICT unordered() would be useful for parallel pipelines with:

1) a source that has order

2) stateful operations that can be optimize if order need not be preserved

3) an order preserving terminal operation

and implying unordered() should be declared close to the source.


> Implementation is trivial.
> 
> Adding .unordered() could also enable us to get rid of .collectUnordered(), and allow more of the reduce-like ops to benefit from the embrace of "disorder" without API explosion.
> 

Although collectUnordered also back propagates lack of order upstream (just like forEach, or findAny). To remove collectUnordered we would need collectors to define whether they preserve order or not (I see in a recent change set to lambda you started work on that).

So a collect(toConcurrentMap()) should back propagate lack of order since CHM is used, but for the supplier version we cannot guarantee that since ConcurrentSkipListMap might be used. Ugh is all a bit complex.

Paul.