Overload resolution uses quadratic algorithm to find the best candidate.

[gafter]

Overload resolution (unary operators, binary operators, and methods) uses a quadratic algorithm to select the best candidate, because it compares every candidate to every other candidate.

There is a simple linear algorithm that gives the same result: scan once to find a possibly best method, and then scan a second time to ensure that it is better than every other candidate.

[bbarry]

so here:

roslyn/src/Compilers/CSharp/Portable/Binder/Semantics/Operators/BinaryOperatorOverloadResolution.cs

Line 846 in f8bda45

for (int i = 0; i < candidates.Count; ++i)

could be:

var candidates = result.Results;
if (candidates.Count < 2) return;
var best = 0;
for (; best < candidates.Count; ++best)
{
    if (candidates[best].Kind == OperatorAnalysisResultKind.Applicable)
    {
        break;
    }
}
for (var i = best + 1; i < candidates.Count; ++i)
{
    if (candidates[i].Kind != OperatorAnalysisResultKind.Applicable)
    {
        continue;
    }

    var better = BetterOperator(candidates[best].Signature, candidates[i].Signature, left, right, ref useSiteDiagnostics);
    if (better == BetterResult.Left)
    {
        candidates[i] = candidates[i].Worse();
    }
    else if (better == BetterResult.Right)
    {
        candidates[best] = candidates[best].Worse();
        best = i;
    }
}
for (var i = 0; i < candidates.Count; ++i)
{
    if (i == best)
    {
        continue;
    }
    if (candidates[i].Kind != OperatorAnalysisResultKind.Applicable)
    {
        continue;
    }

    //is it safe to simply:
    //candidates[i] = candidates[i].Worse();
    //or should this be done:
    var better = BetterOperator(candidates[best].Signature, candidates[i].Signature, left, right, ref useSiteDiagnostics);
    if (better == BetterResult.Left)
    {
        candidates[i] = candidates[i].Worse();
    }
    else if (better == BetterResult.Right)
    {
        // panic?
    }
}

I think this is potentially going to provide a different result.

If you have 3 options, A, B and C and BetterOperator would provide the results:

op1 op2 better
A    B     neither
A    C     A
B    C     C

The current implementation would leave A as the best, but this linear one would never check B vs C so both A and B would still be Applicable.

Is such an event not possible based on the spec (if A vs B is undecided then A vs C and B vs C is either always C or never C or undecided, but never mixed)?

[gafter]

@bbarry Good questions.

The same (as existing) result can be produced with a linear algorithm. Just not the one you provided.

[bbarry]

I've created this console app tool to attempt to validate the algorithm to be used against the existing one (which in its current form demonstrates the above code is not a valid replacement):

https://gist.github.com/bbarry/e78dbfec6a9f71d428e92fc37f567572

[cston]

Fixed in #15839.