Почему List <T>.Sort использует Comparer <int>.Default более чем в два раза быстрее, чем эквивалентный пользовательский сопоставитель?

Результаты

Используя список из 10 миллионов случайных int (одно и то же семя каждый раз, в среднем 10 повторений):

listCopy.Sort(Comparer<int>.Default) принимает 314ms.

Использование

sealed class IntComparer : IComparer<int>
{
  public int Compare(int x, int y)
  {
    return x < y ? -1 : (x == y ? 0 : 1);
  }
}

listCopy.Sort(new IntComparer()) принимает 716ms.

Некоторые варианты:

Использование struct IntComparer вместо sealed class: 771ms
Использование public int Compare(int x, int y) { return x.CompareTo(y); }: 809ms

internal class GenericComparer<T> : Comparer<T> where T : IComparable<T>
{
  public override int Compare(T x, T y)
  {
    if ((object) x != null)
    {
      if ((object) y != null)
        return x.CompareTo(y);
      else
        return 1;
    }
    else
      return (object) y != null ? -1 : 0;
  }

...
}

Очевидно, что это не должно быть быстрее моего варианта IntComparer, используя CompareTo.

Я не нашел ничего подходящего в ArraySortHelper<T>, который кажется ядром List<T>.Sort.

Я могу только догадываться, что JIT делает какую-то магическую специальную оболочку здесь (замените сортировки, которые используют Comparer<int>.Default с помощью специальной реализации сортировки, которая не выполняет никаких вызовов IComparer<T>.Compare или что-то подобное)?

EDIT: приведенные выше тайминги слишком малы в 5.9214729782462845 (Stopwatch и TimeSpan имеют другое определение "Tick" ). Однако это не влияет на точку.

Ответы

Ответ 1

Причина легко видна в Справочном источнике, файле исходного кода system/array.cs:

   [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
   public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) {
       // Argument checking code omitted
       //...

       if (length > 1) {
           // <STRIP>
           // TrySZSort is still faster than the generic implementation.
           // The reason is Int32.CompareTo is still expensive than just using "<" or ">".
           // </STRIP>
           if ( comparer == null || comparer == Comparer<T>.Default ) {
               if(TrySZSort(array, null, index, index + length - 1)) {
                   return;
               }
           }

           ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
       }
   }

Комментарий, отмеченный <STRIP>, объясняет это, несмотря на его сломанный английский:) Путь кода для сравнения по умолчанию проходит через TrySZSort(), функцию, реализованную в CLR и написанную на С++. Вы можете получить его исходный код SSCLI20, он реализован в clr/src/vm/comarrayhelpers.cpp. Он использует метод класса шаблона с именем ArrayHelpers<T>::QuickSort().

Он получает преимущество в скорости от возможности использовать оператор <, одну команду cpu вместо 10, требуемую Int32.CompareTo(). Или, другими словами, IComparable < > . CompareTo переопределен для простой сортировки.

Это микро-оптимизация, в .NET Framework много и много. Неизбежная судьба кода, который находится в самом низу цепи зависимостей, Microsoft никогда не может предположить, что их код не будет критичным для скорости в клиентском приложении.

Ответ 2

ILSpy декомпилирует таким образом:

    public override int Compare(T x, T y)
    {
        if (x != null)
        {
            if (y != null)
            {
                return x.CompareTo(y);
            }
            return 1;
        }
        else
        {
            if (y != null)
            {
                return -1;
            }
            return 0;
        }
    }

Нулевые проверки всегда будут оцениваться как true для типа значения, поэтому они будут оптимизированы; конечный результат будет

public override int Compare(T x, T y)
{
    return x.CompareTo(y);
}

Ответ 3

По умолчанию для Int32 используется метод CompareTo (int, int). Ваше предположение о сравнении по умолчанию неверно.

Интерфейс IComparable обеспечивает строго типизированное сравнение метод упорядочения элементов общего объекта коллекции. Из-за это, как правило, не вызывается непосредственно из кода разработчика. Вместо, он вызывается автоматически такими методами, как List.Sort() и Add.

http://msdn.microsoft.com/en-us/library/4d7sx9hd.aspx. Указанный интерфейс IComparable определяет метод CompareTo.

Поэтому мы должны ожидать, что ваш компаратор будет иметь одинаковую скорость. Так почему это может быть медленнее? Если мы перейдем к методу Сортировка в .Net, мы, в конце концов, перейдем к этой строке:

if ((length > 1) && (((comparer != null) && (comparer != Comparer<T>.Default)) || !TrySZSort(array, null, index, (index + length) - 1)))
{
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}