Encounter order

[Joe Bowbeer]

I don't have any assumptions about ordering after .parallel().

list.parallel().toArray() is analogous to a parallel-ized for-loop.  (See
Parallel.ForEach in C#.)

If I wanted it to execute in order, I wouldn't parallel() it.

Or, if I wanted to "preserve" the order, I would zip-with-index before
parallel execution.

--Joe

On Mon, Oct 22, 2012 at 9:05 PM, Brian Goetz <brian.goetz at oracle.com> wrote:

> For parallel calculations, there are several different things we might
> mean by order.  In the context of bulk operations, I'll (try to) use these
> terms:
>
>  - Encounter order.  A source is said to have an encounter order when the
> order in which elements are yielded by iterator / forEach is predictable
> and meaningful.  (This is a generalization of spatial order, since some
> sources may be purely generative rather than representing data structures.)
>
> Sources such as arrays, lists, queues, sorted collections, and IO channels
> have an encounter order; sources like HashSets or the key set of a HashMap
> do not (though their implementation may have a predictable iteration order
> anyway.)
>
>  - Arrival order.  Arrival order (aka temporal order) is the time order in
> which elements may arrive at a stage of an operation pipeline.  In
> sequential calculations, the encounter order is generally the arrival
> order, but in parallel calculations may not be.  Sometimes this is good,
> sometimes not.
>
> It is easy to track (via the stream flags mechanism) whether a stream
> source has (or more precisely, supports) an encounter order, and similarly
> easy to track whether an operation preserves that order.  We also don't
> start any processing until we've seen the whole pipeline.
>
> Some operations have intrinsic semantic constraints that require us to
> produce a result that is consistent with processing the elements in
> encounter order.  For example, a fold/reduce operation across a list using
> an associative but not commutative operation.  (Though this can still be
> parallelized efficiently.)  Others should probably be constrained to
> preserve order just because this is consistent with user expectations
> (e.g., applying the map function x -> x*2 to [ 1, 2, 3 ] should probably
> yield [ 2, 4, 6 ], not [ 4, 6, 2 ].) Other operations, such as forEach, may
> have neither constraint.
>
> Like any other constraint, requiring processing to be done consistently
> with encounter order has a cost.
>
> Finally, some operations have targets (like into or toArray), which might
> themselves support or not support an encounter order.
>
> What I am trying to accomplish here is to identify reasonable user
> expectations about order preservation for the (source, operation, target)
> combinations we have, and whether we want to / need to add additional
> operations to give users more control over ordering.
>
> Here are some starter questions.  Let "list" contain the numbers 1..10.
>  What should the following expressions compute?
>
>   list.parallel().toArray()
>
>   list.parallel().filter(e -> e > 5).toArray();
>
>   list.parallel().into(new ArrayList<>());
>
>   List target = new ArrayList();
>   list.parallel().forEach(e -> target.add(e));
>
> I think the first one "obviously" should result in an array [ 1..10 ].
>  And the last should "obviously" not be constrained at all as to order,
> only that it print the numbers 1 through 10 in some order. The third one,
> though, isn't completely obvious what the right answer is.
>
> What about this:
>
>   Map m = list.parallel().groupBy(e -> e % 2 == 0);
>
> This partitions the list into two parts; should the elements in each part
> be in the encounter order from the original list?  (In other words, should
> this result in { 0 -> [ 2, 4, 6, 8, 10 ], 1 -> [ 1, 3, 5, 7, 9 ] } ?)
>
> The model I'm targeting is: IF the source has an encounter order AND the
> operation must preserve encounter order, then we need to be sensitive to
> encounter order, otherwise anything goes.  Is this the right model?  If so,
> what are the preservation settings for each operation?
>
> (A secondary consideration is that there are often situations where the
> computation structurally suggests an encounter order, but the user doesn't
> actually care, and then is paying for ordering he doesn't want.  But there
> are fixes for this.)
>
> Lots of more detailed questions but I'll let people respond to these.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/lambda-libs-spec-experts/attachments/20121022/fcf87943/attachment.html