System.Linq.Parallel Max/Min return unstable results.

[Clockwork-Muse]

When dealing with an ordered source, and the maximum or minimum has duplicates according to the comparator, the result returned isn't stable. The following test is failing (results non-deterministic):

[Theory]
[MemberData("Ranges", (object)(new int[] { 1, 2, 16 }), MemberType = typeof(Sources))]
public static void Max_Other_Duplicate(Labeled<ParallelQuery<int>> labeled, int count)
{
    ParallelQuery<int> query = labeled.Item;
    Assert.Equal(0, query.Select(x => DelgatedComparable.Delegate(x, new ModularCongruenceComparer(1))).Max().Value);
}

(this actual test hasn't been uploaded yet, but the rest of the types have been).
DelegateComparable returns a type that says "go use this other comparer instead".
ModularCongruenceComparer compares based on the mod of the input - using 1 means everything has a mod of 0.
I'm expecting the "first" item to be returned (not replaced) from ordered input, for Max and Min to behave the same way as OrderBy does - this may be unfounded. I do not care about unordered input, or the various versions that deal only with primitives; only when a types provides its own comparator is this a potential issue.
This may be important behavior to consider for #14753 .

@stephentoub

[JonHanna]

I don't see why you would expect stable results here. Stable results could be asked for if desired by combining with an index and making the index a secondary sort key. For most people this will add extra work to track indices (trivial to do relatively if you weren't parallel since everything will have a higher index than previous items, but you are parallel so that's no longer the case) and use them as tie-breakers if necessary.

I'm expecting the "first" item to be returned (not replaced) from ordered input, for Max and Min to behave the same way as OrderBy does.

But OrderBy is documented as not being stable at https://msdn.microsoft.com/en-us/library/dd383824.aspx:

In contrast to the sequential implementation, this is not a stable sort.

Indeed, your wording "first" points at why; you can't predict which element will be first to a parallel implementation.

[Clockwork-Muse]

@hackcraft - then I'll need to double check the tests that say otherwise (I only modified them). They might be executing sequentially or something.

[Clockwork-Muse]

@hackcraft - okay, what's actually going on is the tests are capturing the index via a Select, then using that as a sort key. I didn't question it much at the time, although I think it still seemed weird to me. So tests are more insuring that indices issued are stable, rather than that the sort is stable. Without that other key, the sort is indeed unstable.

@AlfredoMS - in light of this, I'm going to close this issue (and comment the tests a bit more).

[JonHanna]

@Clockwork-Muse that makes sense; capturing the index via a Select is exactly what I was talking about when I said "Stable results could be asked for if desired".