Is the IEnumerable.OrderBy().First() optimisation in .Net Core 3.1 documented anywhere?

user_106159 0
Viewed 288

One of the .Net Core versions (I'm not sure which) introduced an optimisation such that if you write code like this:

int smallest = new[]{ 7, 2, 4, 6, 0, 1, 6, 9, 8 }.OrderBy(i => i).First();

then its complexity is O(N) rather than O(N.Log(N)).

Is this documented anywhere? I don't want to rely on this optimisation if it isn't "official".

Sample code that shows the difference between .Net Core and .Net Framework:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        static void Main()
        {
            int[] test = { 7, 2, 4, 6, 0, 1, 6, 9, 8 };

            var comparer = new Comparer();
            var _ = test.OrderBy(i => i, comparer).First();
        }
    }

    class Comparer : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            Console.WriteLine($"Comparing {x} with {y}");
            return x.CompareTo(y);
        }
    }
}

Try it online with .Net Framework: https://dotnetfiddle.net/XItXYL

Try it online with .Net Core: https://dotnetfiddle.net/swlc0O

Output with .Net Framework 4.8:

Comparing 0 with 7
Comparing 0 with 8
Comparing 0 with 9
Comparing 0 with 6
Comparing 0 with 1
Comparing 0 with 0
Comparing 0 with 2
Comparing 0 with 6
Comparing 0 with 4
Comparing 0 with 2
Comparing 0 with 0
Comparing 7 with 2
Comparing 7 with 4
Comparing 7 with 6
Comparing 7 with 7
Comparing 7 with 8
Comparing 7 with 9
Comparing 7 with 6
Comparing 7 with 1
Comparing 7 with 7
Comparing 7 with 1
Comparing 9 with 7
Comparing 9 with 9
Comparing 9 with 8
Comparing 7 with 7
Comparing 7 with 8
Comparing 7 with 7
Comparing 6 with 2
Comparing 6 with 4
Comparing 6 with 6
Comparing 6 with 1
Comparing 6 with 6
Comparing 6 with 6
Comparing 6 with 1
Comparing 6 with 6
Comparing 6 with 6
Comparing 4 with 2
Comparing 4 with 4
Comparing 4 with 1
Comparing 2 with 2
Comparing 2 with 1

Output for .Net Core 3.1:

Comparing 2 with 7
Comparing 4 with 2
Comparing 6 with 2
Comparing 0 with 2
Comparing 1 with 0
Comparing 6 with 0
Comparing 9 with 0
Comparing 8 with 0
.net-core optimization linq c#
2 Answers
user_1061590

This isn't officially documented in the Microsoft documentation on those LINQ operators (OrderBy and First).

This is intentional. Once a behavior is officially documented this way, any change to that behavior becomes a breaking change, which may limit the developers' ability to make other optimizations which may be even more beneficial. If you are going to rely on specific implementation details, you should probably write your own method for this purpose.

That said, it's relatively rare for the O(n) versus O(n log(n)) complexity to make the difference between acceptable and unacceptable performance in an application. Consider carefully whether you're engaging in premature optimization.

user_1209550
Related