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

Результаты

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

listCopy.Sort(Comparer<int>.Default) занимает 314 мс.

С помощью

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

listCopy.Sort(new IntComparer()) занимает 716мс.

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

  • С помощью struct IntComparer вместо sealed class: 771мс
  • С помощью public int Compare(int x, int y) { return x.CompareTo(y); }: 809мс

Комментарии

Comparer<int>.Default возвращает GenericComparer<int>, Согласно dotPeek у нас есть:

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 звонки или что-то подобное)?

РЕДАКТИРОВАТЬ: сроки выше, слишком низок в 5.9214729782462845 (Stopwatch а также TimeSpan есть другое определение "Тик"). Не влияет на суть, хотя.

Источник

3 ответа

Решение

Причина хорошо видна в файле исходного кода Reference Source, 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 и написана на C++. Вы можете получить его исходный код из SSCLI20, он реализован в clr/src/vm/comarrayhelpers.cpp. Он использует метод класса шаблона с именем ArrayHelpers<T>::QuickSort(),

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

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

Источник

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);
}
Источник

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

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

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

Поэтому мы должны ожидать, что ваш компаратор будет примерно с той же скоростью. Так почему же это может быть медленнее? Если мы покопаемся в методе Sort в.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);
}

Если компаратор равен компаратору по умолчанию для этого типа, сортировка массива попытается использовать внутренний оптимизированный метод сортировки. Ваш компаратор не является компаратором по умолчанию, поэтому он пропускает оптимизированную сортировку.

Источник
Другие вопросы по тегам