Collection method for associative, but not commutative, reductions

[mathstuf]

Not sure how possible this is, but I'd like to be able to use parallel iterators with non-commutative reduction functions (e.g., collecting error messages in a deterministic order).

Maybe best to use .enumerate() and .sort() a Vec populated by the parallel iterator?

[cuviper]

I don't know if it's promised, but the current implementation should actually preserve order in the reductions, just with associative differences as you note. This is a natural implication of the way the jobs are split recursively and then joined as it returns.

[nikomatsakis]

I believe that in https://github.com/nikomatsakis/rayon/pull/120 I went ahead and promised that the order would be deterministic when doing reduce or fold.

[cuviper]

Hmm, the new reduce says just associative, but reduce_with still says commutative too. Then sum, mul, min, and max all mention commutative operators.

[nikomatsakis]

@cuviper well-- consistency is a lot to ask =)

In any case, I feel all right about just requiring associativity.

[mathstuf]

Are there tests for just-associative reduction functions (String::push?) already?

[cuviper]

Using collect into any of the ordered collections will exercise associative non-commutative reduce. Look at their FromParallelIterator implementations.

Any further question about this? Otherwise, I think we can close this issue.

[mathstuf]

Yeah, the issue can likely be closed. I was more wondering whether there were tests to this effect rather than "well, the implementation works that way".

[cuviper]

Ok, I don't think we have any plain mathematical tests of this, but all of the collection and string stuff mandates that it works this way. Also, find_first et al. would make no sense if we didn't maintain order.