Encounter order

[David Holmes]

As I discussed on IM with Brian yesterday it doesn't make sense to ask 
what properties the parallel() stream has. parallel() in and of itself 
does not preserve or mutate order. The question is what does 
parallel().op() do - and that depends both on the op() and what entity 
you applied parallel() to.

For some ops like sum(), max() (the commutative ones) it doesn't matter 
how you implement them (serial, parallel) the result is always the same 
- given the input there is only one possible answer.

For other ops, like findAny, there may be multiple possible answers, so 
the result is a function of both the input data and the algorithm used 
to locate it - hence a parallel implementation may not only produce a 
different result to a serial implementation, it may produce a different 
result each time it is executed.

My concern with all this is that when writing the specification for 
SomeClass.op we have to understand what actions can precede it in the 
pipeline and how they affect the semantics that op provides.

David

On 25/10/2012 8:35 AM, Dan Smith wrote:
> On Oct 24, 2012, at 4:12 PM, Brian Goetz<brian.goetz at oracle.com>  wrote:
>
>>>> For example, one question we could ask is "what happens when you
>>>> call reduce on a stream without an encounter order."  One
>>>> possibility is "hope that the reducer is commutative"; another is
>>>> to treat reduction on a order-less stream as an error.
>>>> Unfortunately we don't have ways in the type system to tag lambdas
>>>> as commutative or associative, so the user is on their own to avoid
>>>> GIGO here.  This isn't great, as it requires some nonmodular
>>>> reasoning on the part of the user.  On the other hand, this isn't
>>>> all that different from having to know "is this collection
>>>> thread-safe or not."
>>>
>>> So this is a Kind B stream.  I'm saying an error would never be what
>>> we'd want -- since this is a new type unrelated to Stream, if we
>>> don't want to support an operation, it simply doesn't exist.
>>
>> I don't think so.  Stream sources are free to declare whether they have an encounter order or not.  We could of course decide all streams have an encounter order (imposed by their iterators).  But outlawing set.stream().reduce() seems pretty harsh.
>
> 'set.stream()', if it's parallel at all, is presumably a Kind A stream.  Kind A streams are inherently ordered -- even if the source had to make arbitrary decisions about how to order it -- and can have operations that depend on order.
>
> 'set.asKindBParallel()' has no concept of order, and it makes no sense to give it order-dependent operations.
>
> (And, again, quite possibly Kind B streams can't justify their existence, and what you're designing is just Kind A.)
>
> —Dan