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

Предположим, есть задача: нужно отсортировать коллекцию по нескольким ключам. В 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:

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

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

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

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

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

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

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

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

Из таблицы видно, что вызовы 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:

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

Опускаемся в конструктор OrderedEnumerable:

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

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

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

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

• _source;
• _parent;
• _keySelector;
• _comparer;
• _descending.

ThenBy

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

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

В нашем случае тип переменной source — OrderedEnumerable. Посмотрим на реализацию метода CreateOrderedEnumerable:

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

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

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

ToArray

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

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

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

public TElement[] ToArray()
{
  Buffer buffer = new Buffer(_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:

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

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

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

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

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

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

public TElement[] ToArray()
{
  Buffer buffer = new Buffer(_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;
• OrderBy ().ThenBy (): ссылается на экземпляр Wrapper[].

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

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

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

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

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

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

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

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

  ....
}

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

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

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

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

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

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

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

public TElement[] ToArray()
{
  Buffer buffer = new Buffer(_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 buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

Метод GetEnumerableSorter:

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

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

internal override EnumerableSorter 
GetEnumerableSorter(EnumerableSorter? next)
{
  ....

  EnumerableSorter sorter = 
    new EnumerableSorter(_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 keySelector, 
  IComparer comparer, 
  bool descending, 
  EnumerableSorter? 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.Default, если не задан явно;
• _descenging: флаг того, что коллекция сортируется по убыванию;
• _next: ссылка на объект EnumerableSorter, отвечающий за следующий критерий сортировки. В примере выше — ссылка на объект, который создан для сортировки по критерию из ThenBy.

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

private int[] SortedMap(Buffer 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.

Таким образом, _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(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);

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

public delegate int Comparison(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.Default, в нашем случае — Comparer.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 
GetEnumerableSorter(EnumerableSorter? next)
{
  ....

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

  return sorter;
}

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

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

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

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

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

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

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

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

Выводы

Код, в котором OrderBy ().ThenBy () используется вместо OrderBy ().OrderBy ():

• лучше читается;
• меньше подвержен ошибкам;
• работает быстрее;
• расходует меньше памяти.

Как обычно, приглашаю подписаться на Twitter, если интересны подобные публикации.

© Habrahabr.ru