Почему метод Enumerable.OrderBy<TSource, TKey> работает быстрее, когда он не использует Comparer

Question

Я написал код тестирования скорости сортировки методов. Он генерирует коллекцию и сортирует ее различными способами.

public void TestMethod1()
    {
        var unsortedCollection = GenerateCollection();

        var toSort = unsortedCollection.ToList();
        Console.WriteLine("OrderBy x.A: " + Measure(() => toSort.OrderBy(x => x.A).ToArray()) + "ms");
        toSort = unsortedCollection.ToList();
        Console.WriteLine("OrderBy x: " + Measure(() => toSort.OrderBy(x => x).ToArray()) + "ms");
        toSort = unsortedCollection.ToList();
        Console.WriteLine("OrderBy x using Comparer: " + Measure(() => toSort.OrderBy(x => x, new Comparer()).ToArray()) + "ms");
        toSort = unsortedCollection.ToList();
        Console.WriteLine("OrderBy x using Comparer<int>.Default: " + Measure(() => toSort.OrderBy(x => x.A, Comparer<int>.Default).ToArray()) + "ms");
        toSort = unsortedCollection.ToList();
        Console.WriteLine("OrderBy x using Comparer<SimpleObject>.Default: " + Measure(() => toSort.OrderBy(x => x, Comparer<SimpleObject>.Default).ToArray()) + "ms");

        toSort = unsortedCollection.ToList();
        Console.WriteLine("Sort: " + Measure(() =>
                                                 {
                                                     toSort.Sort();
                                                     toSort.ToArray();
                                                 }) + "ms"); 
        toSort = unsortedCollection.ToList();
        Console.WriteLine("Sort using Comparison: " + Measure(() =>
                                                                  {
                                                                      toSort.Sort((x, y) => x.A.CompareTo(y.A));
                                                                      toSort.ToArray();
                                                                  }) + "ms");
        toSort = unsortedCollection.ToList();
        Console.WriteLine("Sort using Comparer: " + Measure(() =>
                                                                {
                                                                    toSort.Sort(new Comparer());
                                                                    toSort.ToArray();
                                                                }) + "ms");

    }

   private List<SimpleObject> GenerateCollection()
   {
       int length = 10000000;
       var list = new List<SimpleObject>();
       for (int i=0; i<length; i++)
       {
           list.Add(new SimpleObject());
       }
       return list;
   }

    private long Measure(Action method)
    {
        Stopwatch sw = new Stopwatch();
        sw.Reset();
        sw.Start();
        method();
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    public class Comparer: IComparer<SimpleObject>
    {
        public int Compare(SimpleObject x, SimpleObject y)
        {
            return x.A.CompareTo(y.A);
        }
    }
    public class SimpleObject: IComparable<SimpleObject>
    {
    public int A;
    private static Random rand = new Random();
    private const int maxValue = 1000000;

    public SimpleObject()
    {
        A = rand.Next(maxValue);
    }

    public int CompareTo(SimpleObject other)
    {
        return A.CompareTo(other.A);
    }
}

Вот результаты:

OrderBy x.A: 8732ms
OrderBy x: 19136ms
OrderBy x using Comparer: 17054ms
OrderBy x using Comparer<int>.Default: 8758ms
OrderBy x using Comparer<SimpleObject>.Default: 19817ms
Sort: 8000ms
Sort using Comparison: 9515ms
Sort using Comparer: 8990ms

Интересно, почему OrderBy с использованием Comparer работает дольше, чем без Comparer, и почему Sort with Comparison работает дольше с использованием Comparer.

Answer 1

Кажется, проблема в сравнении объектов. Метод OrderBy кэширует ключи. Ключи int сравниваются быстро, а ключи объектов сравниваются долго.