Сергей Васильев

20 Сен 2022

Теги:

#CSharp

Сортировки в C#: OrderBy.OrderBy или OrderBy.ThenBy? Разбираемся, что эффективнее и почему

20 Сен 2022

Автор: Сергей Васильев

Предыстория
Сравнение эффективности
- Производительность
- Использование памяти
Отличия в поведении
Разница в двух словах
Выводы

Предположим, есть задача: нужно отсортировать коллекцию по нескольким ключам. В C# это можно сделать с помощью вызовов OrderBy().OrderBy() или OrderBy().ThenBy(). Но в чём разница между этими вызовами? Чтобы ответить на этот вопрос, придётся покопаться в исходниках.

Статья состоит из трёх основных разделов:

Предыстория. Для тех, кто любит затравки. История о том, откуда вообще возникла идея провести исследование и изучить, в чём разница между OrderBy().OrderBy() и OrderBy().ThenBy().
Сравнение эффективности. Изучаем отличия типов сортировок с точки зрения производительности и потребления памяти.
Отличия в поведении. Погружаемся в исходники .NET и разбираемся, из-за чего возникают отличия в эффективности работы рассматриваемых способов сортировки.

Предыстория

Всё началось со статьи "Подозрительные сортировки в Unity, ASP.NET Core и не только". В ней рассматривались случаи, когда последовательность вызовов OrderBy().OrderBy() могла приводить к ошибкам. Однако оказалось, что порой разработчики намеренно сортируют с помощью OrderBy().OrderBy(), а не OrderBy().ThenBy().

Рассмотрим пример. Допустим, есть класс Wrapper и массив экземпляров этого типа:

class Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

var arr = new Wrapper[]
{
  new() { Primary = 1, Secondary = 2 },
  new() { Primary = 0, Secondary = 1 },
  new() { Primary = 2, Secondary = 1 },
  new() { Primary = 2, Secondary = 0 },
  new() { Primary = 0, Secondary = 2 },
  new() { Primary = 0, Secondary = 3 },
};

Мы хотим отсортировать этот массив: сначала по значению Primary, затем – по Secondary.

По ошибке сортировку можно выполнить так:

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);
....

Результат:

Primary: 2 Secondary: 0
Primary: 0 Secondary: 1
Primary: 2 Secondary: 1
Primary: 0 Secondary: 2
Primary: 1 Secondary: 2
Primary: 0 Secondary: 3

Из-за ошибки мы получили не тот результат, который был нужен. Правильно отсортировать коллекцию можно через последовательность вызовов OrderBy().ThenBy():

var sorted = arr.OrderBy(p => p.Primary)
                .ThenBy(p => p.Secondary);
....

Результат:

Primary: 0 Secondary: 1
Primary: 0 Secondary: 2
Primary: 0 Secondary: 3
Primary: 1 Secondary: 2
Primary: 2 Secondary: 0
Primary: 2 Secondary: 1

Однако получить правильный результат можно и через последовательность вызовов OrderBy().OrderBy(), нужно только поменять вызовы местами.

Так неправильно:

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);

Так правильно:

var sorted = arr.OrderBy(p => p.Secondary)
                .OrderBy(p => p.Primary);

Выходит, чтобы получить нужный результат, можно использовать оба способа:

// #1
var sorted1 = arr.OrderBy(p => p.Secondary)
                 .OrderBy(p => p.Primary);

// #2
var sorted2 = arr.OrderBy(p => p.Primary)
                 .ThenBy(p => p.Secondary);

Как по мне, второй вариант читается лучше.

Когда встречаешь вызов OrderBy().OrderBy(), задаёшься вопросом: нет ли в нём ошибки? С OrderBy().ThenBy() иначе: код читается легче, замысел разработчика понятен.

Однако эти способы сортировки отличаются не только внешне: у них разная скорость работы и потребление памяти.

Сравнение эффективности

Для экспериментов возьмём такой код:

struct Wrapper
{
  public int Primary { get; init; }
  public int Secondary { get; init; }
}

Wrapper[] arr = ....;

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

Зафиксируем основные моменты:

Wrapper – структура с двумя целочисленными свойствами. Они будут использоваться в качестве ключей для сортировок;
arr – массив экземпляров Wrapper, который нужно отсортировать. Как он получается – для тестов неважно. Измерять будем только скорость сортировки и получения итогового массива;
два способа сортировки: первый – через вызовы OrderBy().OrderBy(), второй – OrderBy().ThenBy();
вызов ToArray() нужен, чтобы инициировать выполнение сортировки.

Для тестов я взял два набора сгенерированных тестовых данных (экземпляры типа Wrapper). В первом наборе разброс значений Primary и Secondary больше, во втором – меньше. В arr записывал от 10 до 1 000 000 объектов Wrapper и сортировал их.

Тестовый проект работает на .NET 6.

Производительность

Время работы измерял с помощью BenchmarkDotNet.

Ниже привожу результаты времени выполнения сортировки и получения массива. Абсолютные значения не так интересны – важна разница между способами сортировок.

Набор данных #1:

arr.Length	10	100	1 000	10 000	100 000	1 000 000
OrderBy().OrderBy()	619 ns	9 us	170 us	2 ms	25.8 ms	315 ms
OrderBy().ThenBy()	285 ns	4.5 us	100 us	1.4 ms	20.4 ms	271 ms
Соотношение	2.17	2	1.7	1.43	1.26	1.16

Набор данных #2:

arr.Length	10	100	1 000	10 000	100 000	1 000 000
OrderBy().OrderBy()	553.3 ns	8.7 us	154 us	2.1 ms	29.5 ms	364 ms
OrderBy().ThenBy()	316.4 ns	4.2 us	80 us	1.1 ms	16.9 ms	240 ms
Соотношение	1.75	2.07	1.93	1.91	1.75	1.52

Можно пойти дальше и посмотреть разницу во времени, если выполнять не одну операцию сортировки, а несколько. Для этого воспользуемся циклом for:

for (int i = 0; i < iterNum; ++i)
{
  // Perform sorting
}

Время сортировки (в секундах) 1 000 000 экземпляров типа Wrapper:

Количество итераций	1	10	100
OrderBy().OrderBy()	0.819	6.52	65.15
OrderBy().ThenBy()	0.571	5.21	42.94
Соотношение	1.43	1.25	1.30

Согласитесь, разница в 20 секунд – повод призадуматься.

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

С памятью похожая история – OrderBy().OrderBy() потребляет больше. Сильнее заметно на больших объёмах данных и нескольких итерациях.

Разница в количестве создаваемых объектов на одной итерации:

Тип	OrderBy().OrderBy()	OrderBy().ThenBy()
Int32[]	4	3
Comparison<Int32>	2	1
Wrapper[]	3	2

Из таблицы видно, что вызовы OrderBy().OrderBy() генерируют на два массива больше. На тесте, где было 100 операций сортировки, это привело к разнице в 1Гб выделенной памяти.

Важно отметить, что чем больше размер сортируемой коллекции, тем больше размер "лишних" массивов. Как следствие, увеличивается и размер потребляемой памяти.

Отличия в поведении

Пришло время заглянуть "под капот". Напомню, что мы рассматриваем два способа сортировки:

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();

// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

Чтобы понять разницу, нужно проанализировать:

методы, которые вызываются;
состояние объектов, для которых вызываются методы;
ход потока исполнения.

Исходники .NET 6 возьмём с GitHub.

Методы верхнего уровня

Нам нужно разобрать три метода верхнего уровня: OrderBy, ThenBy и ToArray. Рассмотрим каждый из них.

OrderBy

OrderBy – метод расширения, который возвращает экземпляр типа OrderedEnumerable<TElement, TKey>:

public static IOrderedEnumerable<TSource> 
OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
                       Func<TSource, TKey> keySelector)
  => new OrderedEnumerable<TSource, 
                           TKey>(source, keySelector, null, false, null);

Опускаемся в конструктор OrderedEnumerable<TElement, TKey>:

internal OrderedEnumerable( IEnumerable<TElement> source, 
                            Func<TElement, TKey> keySelector, 
                            IComparer<TKey>? comparer, 
                            bool descending, 
                            OrderedEnumerable<TElement>? parent
                           ) : base(source)
{
  ....
  _parent = parent;
  _keySelector = keySelector;
  _comparer = comparer ?? Comparer<TKey>.Default;
  _descending = descending;
}

Здесь интересен вызов конструктора базового типа – base(source). Базовый тип – OrderedEnumerable<TElement>. Конструктор выглядит так:

protected OrderedEnumerable(IEnumerable<TElement> source) 
  => _source = source;

Зафиксируем: в результате вызова OrderBy создаётся экземпляр OrderedEnumerable<TElement, TKey>. Его состояние определяется полями:

_source;
_parent;
_keySelector;
_comparer;
_descending.

ThenBy

ThenBy - метод расширения:

public static IOrderedEnumerable<TSource> 
ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, 
                      Func<TSource, TKey> keySelector)
{
  ....
  return source.CreateOrderedEnumerable(keySelector, null, false);
}

В нашем случае тип переменной source – OrderedEnumerable<TElement, TKey>. Посмотрим на реализацию метода CreateOrderedEnumerable:

IOrderedEnumerable<TElement> 
IOrderedEnumerable<TElement>
 .CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, 
                                IComparer<TKey>? comparer, 
                                bool descending) 
  => new OrderedEnumerable<TElement, 
                           TKey>(_source, 
                                 keySelector, 
                                 comparer, 
                                 @descending, 
                                 this);

Видно, что вызывается уже знакомый нам конструктор типа OrderedEnumerable<TElement, TKey> (мы рассмотрели его в разделе про OrderBy). Отличаются аргументы вызова, и, как следствие, состояние созданного объекта.

Зафиксируем: ThenBy, как и OrderBy, в нашем случае возвращает экземпляр типа OrderedEnumerable<TElement, TKey>.

ToArray

ToArray – метод расширения:

public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source)
{
  ....
  return source is IIListProvider<TSource> arrayProvider
    ? arrayProvider.ToArray()
    : EnumerableHelpers.ToArray(source);
}

В обоих рассматриваемых случаях сортировки source – экземпляры типа OrderedEnumerable<TElement, TKey>. Этот тип реализует интерфейс IIlistProvider<TSource>, значит исполнение пойдёт через вызов arrayProvider.ToArray(). По факту будет вызван метод OrderedEnumerable<TElement>.ToArray:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

И здесь начнутся ключевые различия. Прежде чем мы продолжим погружение, нужно узнать состояние объектов, с которыми мы будем работать.

Состояния объектов OrderedEnumerable

Возвращаемся к исходным примерам:

// #1
_ = arr.OrderBy(p => p.Secondary) // Wrapper[] -> #1.1
       .OrderBy(p => p.Primary)   // #1.1 -> #1.2
       .ToArray();                // #1.2 -> Wrapper[]

// #2
_ = arr.OrderBy(p => p.Primary)  // Wrapper[] -> #2.1
       .ThenBy(p => p.Secondary) // #2.1 -> #2.2
       .ToArray();               // #2.2 -> Wrapper[]

Нужно сравнить попарно четыре объекта:

#1.1 и #2.1 – объекты, порождённые первыми вызовами OrderBy в обоих примерах;
#1.2 и #2.2 – объекты, порождённые вторым вызовом OrderBy в первом примере и ThenBy во втором.

В результате получаем 2 таблицы для сравнения состояний объектов.

Состояния объектов, порождённых первыми вызовами OrderBy:

Поле	Object #1.1	Object #2.1
_source	arr	arr
_comparer	Comparer<Int32>.Default	Comparer<Int32>.Default
_descending	false	false
_keySelector	p => p.Secondary	p => p.Primary
_parent	null	null

Эта пара одинакова. Исключение – селекторы.

Состояния объектов, порождённых вторым вызовом OrderBy (#1.2) и ThenBy (#2.2):

Поле	Object #1.2	Object #2.2
_source	Object #1.1	arr
_comparer	Comparer<Int32>.Default	Comparer<Int32>.Default
_descending	false	false
_keySelector	p => p.Primary	p => p.Secondary
_parent	null	Object #2.1

Селекторы тоже различаются, это ожидаемо. Что более интересно – отличаются поля _source и _parent. Состояние объекта выглядит более правильным в случае с вызовом ThenBy (#2.2): ссылка на исходную коллекцию сохраняется, при этом есть "родитель" – результат предыдущей сортировки.

Поток исполнения

Теперь разберём, как состояние объектов влияет на поток исполнения.

Вернёмся к методу ToArray:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

Помним, что поле _source отличается у объектов, полученных разными вызовами:

OrderBy().OrderBy(): ссылается на экземпляр OrderedEnumerable<TElement, TKey>;
OrderBy().ThenBy(): ссылается на экземпляр Wrapper[].

Посмотрим на определение типа Buffer<TElement>:

internal readonly struct Buffer<TElement>
{
  internal readonly TElement[] _items;
  internal readonly int _count;

  internal Buffer(IEnumerable<TElement> source)
  {
    if (source is IIListProvider<TElement> iterator)
    {
      TElement[] array = iterator.ToArray();
      _items = array;
      _count = array.Length;
    }
    else
    {
      _items = EnumerableHelpers.ToArray(source, out _count);
    }
  }
}

Здесь начинается расхождение в поведении:

для вызовов OrderBy().OrderBy() исполнение идёт по then-ветви, так как OrderedEnumerable реализует интерфейс IIListProvider<TElement>;
для вызовов OrderBy().ThenBy() исполнение идёт по else-ветви, так как массивы (Wrapper[] в нашем случае) этот интерфейс не реализуют.

В первом случае мы возвращаемся в метод ToArray, который был приведён выше. Из него опять попадаем в конструктор Buffer, но исполнение уже пойдёт по else-ветке, т.к. _source у объекта #1.1 – Wrapper[].

EnumerableHelpers.ToArray просто создаёт копию массива:

internal static T[] ToArray<T>(IEnumerable<T> source, out int length)
{
  if (source is ICollection<T> ic)
  {
    int count = ic.Count;
    if (count != 0)
    {        
      T[] arr = new T[count];
      ic.CopyTo(arr, 0);
      length = count;
      return arr;
    }
  }
  else
    ....

  ....
}

Исполнение идёт по then-ветке. Остальной код я опустил, т.к. в нашем случае он неважен.

Более наглядно разницу видно по стекам вызовов. Обратите внимание на выделенные "лишние" вызовы:

Call stack для OrderBy().OrderBy()	Call stack для OrderBy().ThenBy()

EnumerableHelpers.ToArray	EnumerableHelpers.ToArray
Buffer.ctor	Buffer.ctor
OrderedEnumerable.ToArray	OrderedEnumerable.ToArray
Buffer.ctor	Enumerable.ToArray
OrderedEnumerable.ToArray	Main
Enumerable.ToArray
Main

Отсюда, кстати, и отличие в количестве создаваемых объектов. Выше мы рассматривали таблицу с ними:

Тип	OrderBy().OrderBy()	OrderBy().ThenBy()
Int32[]	4	3
Comparison<Int32>	2	1
Wrapper[]	3	2

Наиболее интересными здесь выглядят массивы: Int32[] и Wrapper[]. Они возникают из-за того, что поток исполнения лишний раз проходит через метод OrderedEnumerable<TElement>.ToArray:

public TElement[] ToArray()
{
  ....
  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  ....
}

Ещё раз отмечу, что размеры массивов array и map зависят от размера сортируемой коллекции: чем она больше, тем больше будет оверхед из-за лишнего вызова OrderedEnumerable<TElement>.ToArray.

Та же история с производительностью. Ещё раз посмотрим на код метода OrderedEnumerable<TElement>.ToArray:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_source);

  int count = buffer._count;
  if (count == 0)
  {
    return buffer._items;
  }

  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  for (int i = 0; i != array.Length; i++)
  {
    array[i] = buffer._items[map[i]];
  }

  return array;
}

Нас интересует массив map. Он описывает отношения между позициями элементов в массивах:

индекс – позиция элемента в результирующем массиве;
значение по индексу – позиция в исходном массиве.

Допустим, map[5] == 62. Это значит, что в исходном массиве элемент находится на 62 позиции, а в результирующем будет на 5.

Чтобы получить такую "карту отношений", используется метод SortedMap:

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

Метод GetEnumerableSorter:

private EnumerableSorter<TElement> GetEnumerableSorter() 
  => GetEnumerableSorter(null);

Опускаемся в перегрузку метода:

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}

Здесь всплывает ещё одно различие между способами сортировки, которые мы рассматриваем:

OrderBy().OrderBy(): _parent у объекта #1.2 – null. В результате создаётся один экземпляр EnumerableSorter.
OrderBy().ThenBy(): _parent у объекта #2.2 указывает на объект #2.1. Это значит, что будут созданы два экземпляра EnumerableSorter, связанные друг с другом. Это происходит за счёт повторного вызова метода – _parent.GetEnumerableSorter(sorter).

Вызываемый конструктор EnumerableSorter:

internal EnumerableSorter(
  Func<TElement, TKey> keySelector, 
  IComparer<TKey> comparer, 
  bool descending, 
  EnumerableSorter<TElement>? next)
{
  _keySelector = keySelector;
  _comparer = comparer;
  _descending = descending;
  _next = next;
}

Всё, что делает конструктор – инициализирует поля объекта. Есть ещё одно поле, которое не используется в конструкторе – _keys. Оно будет проинициализировано позже, в методе ComputeKeys.

Рассмотрим, за что отвечают поля. Для этого обратимся к одному из рассматриваемых способов сортировки:

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

Для сортировки с помощью OrderBy будет создан экземпляр EnumerableSorter. Его поля:

_keySelector: делегат, отвечающий за маппинг исходного объекта на ключ. В нашем случае: Wrapper -> int. Делегат: p => p.Primary;
_comparer: компаратор, используемый для сравнения ключей. Comparer<T>.Default, если не задан явно;
_descenging: флаг того, что коллекция сортируется по убыванию;
_next: ссылка на объект EnumerableSorter, отвечающий за следующий критерий сортировки. В примере выше – ссылка на объект, который создан для сортировки по критерию из ThenBy.

После того, как экземпляр EnumerableSorter был создан и инициализирован, у него вызывается метод Sort:

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

Тело метода Sort:

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

Метод ComputeMap:

private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}

Посмотрим на метод ComputeKeys:

internal override void ComputeKeys(TElement[] elements, int count)
{
  _keys = new TKey[count];
  for (int i = 0; i < count; i++)
  {
    _keys[i] = _keySelector(elements[i]);
  }

  _next?.ComputeKeys(elements, count);
}

В этом методе инициализируется массив _keys экземпляра EnumerableSorter. Вызов _next?.ComputeKeys(elements, count) позволяет проинициализировать всю цепочку связанных объектов EnumerableSorter.

Для чего нужно поле _keys? Этот массив хранит результаты вызова селектора на каждом элементе оригинального массива. Получается массив ключей, по которым и будет выполняться сортировка.

Пример:

var arr = new Wrapper[]
{
  new() { Primary = 3, Secondary = 2 },
  new() { Primary = 3, Secondary = 1 },
  new() { Primary = 1, Secondary = 0 }
};

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

В этом примере будут созданы два связанных между собой экземпляра EnumerableSorter.

Поле	EnumerableSorter #1	EnumerableSorter #2
_keySelector	p => p.Primary	p => p.Secondary
_keys	[3, 3, 1]	[2, 1, 0]

Таким образом, _keys хранит ключи сортировки для каждого элемента исходного массива.

Возвращаемся в метод ComputeMap:

private int[] ComputeMap(TElement[] elements, int count)
{
  ComputeKeys(elements, count);
  int[] map = new int[count];
  for (int i = 0; i < map.Length; i++)
  {
    map[i] = i;
  }

  return map;
}

После вызова метода ComputeKeys создаётся и инициализируется массив map. Это тот самый массив, который описывает отношения между позициями в исходном и результирующем массивах. В этом методе он пока описывает отношения как i -> i, то есть позиции в исходном и результирующем массивах совпадают.

Возвращаемся ещё выше – в метод Sort:

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

Нас интересует метод QuickSort, в результате которого массив map примет нужный вид. Именно после этой операции мы получим правильные отношения между позициями элементов в исходном массиве и в результирующем.

Тело метода QuickSort:

protected override void QuickSort(int[] keys, int lo, int hi) 
  => new Span<int>(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);

В детали Span и его метода Sort погружаться не будем. Остановимся на том, что он выполняет сортировку массива с учётом делегата Comparison:

public delegate int Comparison<in T>(T x, T y);

Классический делегат для сравнения. Принимает два элемента, сравнивает их и возвращает значение:

< 0, если x меньше y;
0, если x равен y;
> 0, если x больше y.

В нашем случае для сравнения используется метод CompareAnyKeys:

internal override int CompareAnyKeys(int index1, int index2)
{
  Debug.Assert(_keys != null);

  int c = _comparer.Compare(_keys[index1], _keys[index2]);
  if (c == 0)
  {
    if (_next == null)
    {
      return index1 - index2; // ensure stability of sort
    }

    return _next.CompareAnyKeys(index1, index2);
  }

  // ....
  return (_descending != (c > 0)) ? 1 : -1;
}

Разберём его по кусочкам:

int c = _comparer.Compare(_keys[index1], _keys[index2]);
if (c == 0)
  ....

return (_descending != (c > 0)) ? 1 : -1;

Два элемента сравниваются через компаратор, записанный в _comparer. Так как мы явно никакого компаратора не задавали, используется Comparer<T>.Default, в нашем случае – Comparer<Int32>.Default.

Если элементы не равны, условие c == 0 не выполняется, и поток исполнения идёт в return. Поле _descending хранит информацию о том, как проходит сортировка: по убыванию или возрастанию. Если нужно, за счёт него корректируется возвращаемое методом значение.

А что, если элементы равны?

if (c == 0)
{
  if (_next == null)
  {
    return index1 - index2; // ensure stability of sort
  }

  return _next.CompareAnyKeys(index1, index2);
}

Здесь вступают в игру цепочки экземпляров EnumerableSorter, связанных друг с другом. Если сравниваемые ключи равны, выполняется проверка – а нет ли других критериев сортировки? Если есть (_next != null), сравнение уже происходит по ним.

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

Что происходит в случае с OrderBy().OrderBy()? Для этого вернёмся назад, к созданию экземпляра EnumerableSorter:

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....

  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }

  return sorter;
}

Значение _parent у объекта, полученного в результате второго вызова метода OrderBy, – null. Значит, создаётся один экземпляр EnumerableSorter. Он ни с чем не связан, значение _next – null.

Получается, все описанные выше действия нужно провести два раза. Как это сказывается на производительности, мы уже разобрали. Чтобы напомнить, продублирую одну из таблиц, приведённых выше.

Время сортировки (в секундах) 1 000 000 экземпляров типа Wrapper:

Количество итераций	1	10	100
OrderBy().OrderBy()	0.819	6.52	65.15
OrderBy().ThenBy()	0.571	5.21	42.94

Разница в двух словах

Методы OrderBy и ThenBy создают экземпляры OrderedEnumerable, которые используются для выполнения сортировки. Помогают выполнять сортировку экземпляры типа EnumerableSorter. Именно они влияют на алгоритм, используют заданные селекторы и компаратор.

Основное различие между вызовами OrderBy().OrderBy() и OrderBy().ThenBy() – связи между объектами.

OrderBy().OrderBy(). Связей нет ни между OrderedEnumerable, ни между EnumerableSorter. Из-за этого создаются "лишние" объекты, проводится две сортировки, а не одна. Расходуется больше памяти, код работает медленнее.

OrderBy().ThenBy(). И экземпляры OrderedEnumerable, и EnumerableSorter связаны. Из-за этого выполняется одна операция сортировки сразу по нескольким критериям. Лишние объекты не создаются. Памяти потребляется меньше, код работает быстрее.