В этой статье я хочу рассказать, какие вызовы после OrderBy проходят набор один раз, а какие приводят к полной сортировке. Ни по коду, ни по ответу разницу не увидеть: запись почти одинаковая, ответ везде верный.

Считаются не секунды, а обращения к компаратору и к селектору ключа. По ним всё видно сразу: один проход по тысяче элементов — 999 сравнений, полная сортировка того же набора — 11 081. Счётчики одинаковы на любой машине, поэтому выводы сделаны по ним, а время идёт как дополнение.

Замерялись такие вызовы:

• 12 способов получить результат: First, Last, те же два с условием, FirstOrDefault с условием, Min, Max, ElementAt по трём позициям, Take и ToArray

• 7 операторов, поставленных между OrderBy и First: ThenBy, OrderByDescending, Select, Distinct, Take, Skip, Reverse

• 4 записи одной задачи: найти наименьший элемент среди тех, что проходят условие

• всё то же самое, но элемент не число, а класс с ключом в свойстве

Будет 3 истории:

• как один аргумент в First меняет способ вычисления, и почему с Last этого не происходит;

• какие операторы между OrderBy и First оставляют один проход, а какие приводят к полной сортировке;

• что изменилось в .NET 9, 10 и 11.

Рантаймы: 8.0.11–8.0.30, 9.0.4–9.0.19, 10.0.1–10.0.11, 11.0.0 preview. BenchmarkDotNet 0.15.8, все четыре рантайма одним прогоном

.NET 11 — предварительная сборка. С новой версией числа могут измениться.

История 1. Один аргумент меняет способ вычисления

Две строки ниже различаются одним аргументом. Обе дают верный ответ.

// один проход по набору, сортировки нет
int lowest = numbers.OrderBy(x => x).First();

// полная сортировка всего набора
int lowest = numbers.OrderBy(x => x).First(x => x >= threshold);

По времени вывода не сделать. Поэтому считаются обращения к компаратору: он передаётся в OrderBy обычным аргументом и считает собственные вызовы.

public sealed class CountingComparer : IComparer<int>
{
    public static readonly CountingComparer Instance = new();

    public int Compare(int x, int y)
    {
        CallCounter.CountComparison();
        return x.CompareTo(y);
    }
}

Найти наименьший или наибольший элемент за один проход по тысяче чисел — это 999 сравнений. Набор везде один и тот же: тысяча псевдослучайных чисел, сгенерированных с постоянным начальным значением.

Формула N log₂ N даёт для тысячи около 9966, но это лишь оценка. Реальное число сравнений зависит от алгоритма сортировки, от данных и от выбора опорного элемента, и часто оказывается больше. На этом наборе компаратор был вызван 11 081 раз.

Числа в тексте округлены так же, как в таблицах: до двух знаков после запятой.

Из таблицы можно сделать выводы:

• у First, Last и ElementAt(0) 999 сравнений — сортировки не происходит;

• у Last с условием 500 сравнений и 501 вызов селектора вместо 1000. Условие проходит 501 элемент, и наибольший из них находится за 500 сравнений — на одно меньше, чем самих элементов;

• у ElementAt в середине 3334 сравнения, в конце 1610, у Take(10).Last() — 1748: больше одного прохода, но до полной сортировки далеко;

• у First с условием 11 081 сравнение — ровно столько же, сколько у ToArray в последней строке, хотя памяти уходит меньше: 1,15 мегабайта против 1,53. Одинаковое число сравнений говорит о том, что набор сортируется целиком.

Сравним две строки таблицы. У Last с условием 500 сравнений, у First с условием — 11 081. Задача одна: найти крайний элемент среди тех, что прошли условие. Для наибольшего хватает одного прохода, для наименьшего — нет, хотя работы столько же.

У этого есть причина. В .NET Core First с условием после OrderBy работал иначе: набор упорядочивался лениво, а условие проверялось на каждом элементе. В трекере на это появилась задача — предикат с побочными эффектами срабатывал на всех элементах, — и в .NET 5 такое поведение убрали. С тех пор First с условием выполняет полную сортировку.

У Last с условием ничего не поменялось: в OrderedEnumerable.cs есть TryGetLast с предикатом, который проходит источник один раз и запоминает наибольший из тех, что прошли условие.

Порогом взят элемент, делящий набор пополам, поэтому условие проходят 501 элемент в одном случае и 500 в другом. Значит, разница в 11 081 против 500 не от условий: в таблице проверок они поменяны местами, а числа остаются те же.

// один проход по всему набору, 500 сравнений между прошедшими условие
numbers.OrderBy(x => x).Last(x => x <= threshold);

// 11081 сравнение - полная сортировка
numbers.OrderBy(x => x).First(x => x >= threshold);

То же самое по времени, набор из 100 000 элементов.

Из таблицы можно сделать выводы:

• у First и Last 85,65–230,34 микросекунды и 88 байт кучи;

• у Last с условием 443,26–792,31 микросекунды и 152 байта — на 64 байта больше, чем без условия;

• у First с условием 8349,20–14 520,81 микросекунды и 1,15 мегабайта;

• у Min и ToArray то же самое: 8561,97–14 542,94 и 8421,92–15 816,03.

First с условием медленнее Last с условием в 17,49–19,91 раза, а памяти тратит 1,15 мегабайта против 152 байт.

Дальше три проверки, каждая отдельным замером.

Из таблицы можно сделать выводы:

• от перестановки условий ничего не меняется: у First те же 11 081 сравнение, у Last — 499 вместо 500, потому что условие теперь проходят 500 элементов, а не 501;

• на элементе-классе с ключом в свойстве числа те же: 11 081 и 500;

• без компаратора время такое же: отношение к записи с обычным компаратором 0,96–1,08, на одних машинах чуть меньше единицы, на других чуть больше.

Счётчик прибавляет ко времени 1,05–1,69 раза, но способ вычисления не меняет — иначе разница была бы в десятки раз.

OrderBy().First() попал в две таблицы: 85,65–221,83 микросекунды в первой и 91,21–226,66 во второй. Код один, классы замеров разные, расхождение до 6,49 процента. Это предел точности замера времени. На счётчик сравнений он не влияет.

История 2. Какие операторы оставляют один проход

Раз один аргумент внутри First меняет способ вычисления, стоит проверить и остальное. Между OrderBy и First по очереди ставится один оператор. Последний вызов везде одинаковый, а ответ у каждой записи свой: у OrderByDescending и Reverse — наибольший элемент, у Skip(1) — второй с начала, у остальных — наименьший. Каждый ответ сверен со своим эталоном.

Из таблицы можно сделать выводы:

• у ThenBy, OrderByDescending, Select, Distinct, Take и Reverse те же 999 сравнений. У ThenBy это число неполное: счётчик стоит на первом ключе, сравнения по второму в него не входят, так что строка ThenBy говорит только о первом ключе;

• по времени у них 80,97–312,44 микросекунды против 91,21–226,66 без оператора;

• дольше всех работает ThenBy — в 1,12–2,18 раза, но это второй ключ сортировки, а не полная сортировка;

• у Skip(1) 1743 сравнения и 1216,07–2132,21 микросекунды — в 9,41–13,53 раза больше, чем без промежуточного оператора.

До полной сортировки Skip не доводит: 1743 сравнения — это 15,73 процента от полной сортировки на этом же наборе, почти столько же, сколько у Take(10).Last() в первой таблице, где 1748.

На одном размере набора этого не видно: и частичная выборка, и полная сортировка дают больше одного прохода. Разницу показывает рост — те же вызовы на 1000, 10 000 и 100 000 элементов, .NET 10.

Из таблицы можно сделать выводы:

• у First без условия и у Last с условием число сравнений растёт ровно как размер набора: 999, 9999, 99 999 и 500, 5000, 50 000;

• у First с условием и у Min числа совпадают с ToArray на всех трёх размерах — 11 081, 143 011 и 1 846 608, то есть набор полностью сортируется;

• у Skip(1), Take(10).Last() и ElementAt на 100 000 элементов от 209 787 до 241 523 сравнений — это 11,36–13,08 процента от полной сортировки.

Skip и ElementAt не сортируют набор целиком ни на одном из трёх размеров, а First с условием сортирует на каждом.

На .NET 10 полной сортировки не даёт ни один из 7 операторов. В этой таблице проверялось только то, что стоит перед последним вызовом — условия внутри First тут нет.

Теперь про Min и Max из первой таблицы. OrderBy(...).Min() вернёт тот же элемент, что и OrderBy(...).First(), если селектор ключа отдаёт сам элемент, а OrderBy упорядочивает как Comparer<T>.Default — по возрастанию. Так здесь и сделано. Но сравнений у него 11 081 против 999, а времени больше в 65,56–102,10 раза. При другом порядке в OrderBy ответы будут разными: Min берёт элементы по их обычному порядку, а First — по тому, что задан в OrderBy.

Наименьший элемент из прошедших условие можно получить четырьмя способами.

Из таблицы можно сделать выводы:

• у условия внутри First и у условия в Where после OrderBy время одинаковое — 8343,44–14 835,49 микросекунды;

• у того же условия перед OrderBy — 438,08–788,97;

• у Where(условие).Min() — 410,25–761,32. Сортировки нет.

numbers.Where(x => x >= threshold).OrderBy(x => x).First();
numbers.Where(x => x >= threshold).Min();

История 3. Что изменилось в .NET 9, 10 и 11

В .NET 8 OrderBy(...).First() уже обрабатывал набор за один проход. В .NET 9 так же заработали Distinct и Reverse. Счётчик сравнений от машины не зависит — числа совпали на всех четырёх, поэтому таблицу можно строить по рантаймам.

Из таблицы можно сделать выводы:

• Distinct и Reverse на .NET 8 приводили к полной сортировке, с .NET 9 — нет;

• у условия внутри First 11 081 сравнение на всех четырёх рантаймах;

• у Min и Max — тоже 11 081 на всех четырёх.

То есть в .NET 9 два оператора перестали приводить к полной сортировке, а в .NET 10 и в предварительной сборке .NET 11 число сравнений осталось прежним. Три способа получить результат как сортировали набор полностью, так и сортируют.

При этом разница по времени растёт. Отношение кода с условием к коду без него на наборе в 100 000 элементов:

• .NET 8 — 35,66–49,00;

• .NET 9 — 60,78–99,30;

• .NET 10 — 65,46–97,48;

• .NET 11 — 65,08–174,67.

Верхняя граница на .NET 11 выше остальных, но это предварительная сборка — к релизу число может измениться.

Растёт она не потому, что код с условием замедлился, а потому что код без условия ускорился.

Попарно по машинам, .NET 11 против .NET 8:

• код с условием на двух машинах отработал быстрее на 4,29 и на 17,82 процента, на двух других медленнее на 1,13 и на 1,50 процента;

• код без условия отработал быстрее на всех четырёх: на 36,20, на 45,52, на 51,54 и на 83,22 процента.

То же самое у Min: 36,30–51,39 на .NET 8 и 65,14–203,39 на .NET 11.

Выводы

По цифрам

• у First с условием 11 081 сравнение на наборе в 1000 элементов — ровно столько же, сколько у полной сортировки через ToArray;

• у Last с условием 500 сравнений на том же наборе, у FirstOrDefault с условием — те же 11 081, что и у First;

• по времени разница между ними — 17,49–19,91 раза, по памяти — 1,15 мегабайта против 152 байт;

• First с условием работает дольше, чем First без условия, в 65,46–97,48 раза на .NET 10 и в 65,08–174,67 раза на .NET 11, где верхняя граница снята на предварительной сборке;

• OrderBy(...).Min() вернёт тот же элемент, что и OrderBy(...).First(), если селектор ключа отдаёт сам элемент, а OrderBy упорядочивает как Comparer<T>.Default — по возрастанию; времени при этом уходит больше в 65,56–102,10 раза;

• у ThenBy, OrderByDescending, Select, Distinct, Take и Reverse те же 999 сравнений по первому ключу;

• у Skip(1) 1743 сравнения на тысяче элементов и 241 523 на ста тысячах — 13,08 процента от полной сортировки, и в 9,41–13,53 раза больше времени, чем без промежуточного оператора;

• у ElementAt 999 сравнений на первой позиции, 3334 в середине и 1610 на последней — полной сортировки нет ни в одном случае. Разница между серединой и последней позицией заметна только на тысяче элементов, где она составляет 2,07 раза; на десяти тысячах остаётся 1,24, на ста тысячах — 1,04;

• условие, перенесённое из First в Where перед OrderBy, сокращает время в 18,80–22,00 раза при том же ответе;

• в .NET 9 перестали приводить к полной сортировке два оператора: Distinct и Reverse, а в .NET 10 и в предварительной сборке .NET 11 всё осталось как было;

• количество сравнений совпало на всех четырёх машинах.

Что стоит помнить

• Условие внутри First после OrderBy сортирует весь набор. Если предикат и селектор только считают значение и больше ничего не делают, тот же ответ даст фильтр перед сортировкой.

• У Last с условием такого нет, поэтому переносить вывод с одного метода на другие нельзя.

• Min и Max заданный порядок игнорируют, поэтому OrderBy перед ними — бесполезная работа: набор в такой записи всё равно сортируется целиком — 11 081 сравнение против 999. Наименьший или наибольший по этому порядку даст First или Last: если селектор ключа отдаёт сам элемент, а OrderBy упорядочивает как Comparer<T>.Default — по возрастанию, ответ будет тот же, а времени уйдёт в 66–102 раза меньше. Для минимума по обычному порядку хватит Min без OrderBy, что не приводит к сортировке.

• В записи OrderBy(...).Take(10).First() сохраняется один проход, а у OrderBy(...).Skip(1).First() сравнений становится больше — 1743 против 999, но до полной сортировки не доходит ни на одном из трёх размеров.

Код из статьи

• LinqOrderProof — бенчмарки, счётчик обращений к компаратору и прогоны на четырёх машинах

Ссылки

• Enumerable.OrderBy в документации

• Улучшения LINQ в .NET 9

• Улучшения в .NET 10

• dotnet/docs#19683 — сложность First с условием после OrderBy

• dotnet/runtime#31554 — условие после OrderBy вызывалось для каждого элемента

• dotnet/BenchmarkDotNet#3017 — поддержка .NET 11

Всем удачи и до новых встреч!