Encounter order

[Dan Smith]

On Oct 23, 2012, at 2:45 PM, Brian Goetz <brian.goetz at oracle.com> wrote:

> OK, let me try this a different way.
> 
> Let's separate *result* from *side effects*.  Parallelism can change the timing of side-effects, but (I argue) should not change the result of a computation (e.g., summing integers in parallel should yield the same result as summing them sequentially (modulo overflow.))

Sounds like this discussion is mixing two different kinds of parallel streams.

Parallel stream Kind A is a Stream that produces identical results to a serial stream, but is allowed have out-of-order and out-of-thread side effects.

Parallel stream Kind B is a different entity that makes no guarantees about iteration order.  This is not a Stream at all, and should be represented with a different interface; many operations in Stream should not exist in this interface, and those that remain will likely have different contracts (e.g., 'reduce' requires a commutative operator).

(Aside 1: Sorry I don't have better names. :-))
(Aside 2: I think the decision to merge serial and parallel streams under one interface was made with Kind A in mind.)

The question is, I think, which kind of parallel stream we're really talking about when we say we want "parallel collections."  It's possible the answer is "both," and if that's the case, I think they should be implemented separately, rather than trying to mesh the two into one.  It's also possible that the performance gains enabled by Kind B don't justify its existence.

>  [ 1, 2, 3 ].map( x -> x*2 )
> 
> Is there anyone claiming the answer is NOT required to be
> 
>  [ 2, 4, 6 ]

You mean '[ 1, 2, 3 ].parallel().map( x -> x*2 )'.  For Kind B, this means '{ 1, 2, 3 }.map( x -> x*2 )' (using braces to suggest a set).

> (Alternately, this claim amounts to saying that list.parallel().map() should return a multiset rather than a list.)

Even more fundamentally, a Kind B stream should be modeled so that 'list.parallel()' is already a multiset, before 'map' is called.

—Dan