Бенчмаркая сортировку строк: подстава с дефолтным компаратором — ×5

В этой статье я хочу рассказать, сколько времени уходит на сортировку строк, когда компаратор не передан. Array.Sort(string[]) без компаратора сравнивает строки так, как они шли бы в словаре: с учётом языка, регистра и букв с надстрочными знаками. Это заметно дольше сравнения по кодам символов — на тысяче строк в 5,00–11,71 раза.

Будем замерять следующие варианты:

• без компаратора — Array.Sort(a);

• через StringComparer.CurrentCulture и StringComparer.InvariantCulture;

• через StringComparer.Ordinal и StringComparer.OrdinalIgnoreCase;

• сравнение по кодам символов через делегат — string.CompareOrdinal;

• те же варианты у List.Sort, Span.Sort и OrderBy;

• на 5-ти наборах строк: числа, слова из английских букв, строки с одинаковым началом, слова с надстрочными знаками и строки по 128 символов.

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

• сколько занимает одно сравнение и почему дело не в сортировке;

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

Рантаймы: 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. Куда уходит время

Две строки ниже сортируют один и тот же массив. Разница между ними — один аргумент.

// сравнение по правилам языка
Array.Sort(names);

// сравнение по кодам символов
Array.Sort(names, StringComparer.Ordinal);

Массив из 10 000 английских слов, .NET 10. Первая строка таблицы показывает, сколько занимает копия массива. Копию делает каждый вариант, поэтому это время учтено и в остальных строках.

Сортировка 10 000 строк, .NET 10. Без компаратора она занимает в 3,25–4,62 раза больше времени, чем с Ordinal

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

Делегат и StringComparer.Ordinal работают одинаково: отношение 0,86–1,12, а на одной машине из четырёх делегат даже медленнее. Как именно передан порядок — делегатом или объектом — на время не влияет.

Первое, что стоит проверить, — одинаково ли работает сортировка. Может оказаться, что с одним компаратором она сравнивает элементы чаще, чем с другим, и тогда дело не в сравнении.

Для проверки компаратор оборачивается в счётчик, который считает свои вызовы. В обоих случаях сортировка обращается к компаратору через интерфейс IComparer<string>, поэтому путь до сравнения одинаковый и числа можно сравнивать между собой.

public sealed class CountingComparer(IComparer<string> inner) : IComparer<string>
{
    public int Compare(string? x, string? y)
    {
        CallCounter.Count();

        return inner.Compare(x, y);
    }
}

Число сравнений на 10 000 строк, .NET 10.

Обращения к компаратору. Сортировка делает одну и ту же работу, различается только сравнение

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

Второе — сколько времени уходит на языковые правила. Для такого сравнения в .NET используется ICU, библиотека с таблицами языков. Её отключает переменная среды DOTNET_SYSTEM_GLOBALIZATION_INVARIANT: с ней строки сравниваются по кодам символов, а код остаётся прежним. Вместе со временем меняется и результат сортировки, поэтому в рабочем приложении такая переменная опасна — здесь она нужна только для замера.

Массив из 10 000 строк, .NET 10, замер на Stopwatch. Без ICU сортировка без компаратора занимает столько же, сколько сортировка по кодам символов

Сортировка с Ordinal без ICU не меняется — 0,99–1,06. А сортировка без компаратора ускоряется в 2,21–2,69 раза и даёт такие же числа. Значит, всё лишнее время уходило на языковые правила.

Третье. Те же языковые правила, записанные явно, работают быстрее:

// сравнение по правилам языка, компаратор не передан
Array.Sort(names);

// те же правила, но компаратор указан
Array.Sort(names, StringComparer.CurrentCulture);

Обе строки сравнивают по одним правилам и дают один результат, но вторая быстрее: 4034,92–5739,46 микросекунды против 4634,36–6731,95, то есть в 1,15–1,25 раза.

Причина в том, что путь до сравнения разный. Без компаратора это GenericComparer<string> → string.CompareTo → CultureInfo.CurrentCulture.CompareInfo.Compare: на каждом вызове читается текущая культура потока, и уже через неё берётся CompareInfo. У StringComparer.CurrentCulture это CultureAwareComparer, у которого CompareInfo и параметры сравнения лежат в полях с момента создания, поэтому вызов идёт сразу в CompareInfo.Compare.

История 2. Дело не в строках и не в способе сортировки

Возьмём пять разных наборов по 10 000 строк: строки-числа, английские слова, строки с одинаковыми первыми 14 символами, слова с надстрочными знаками и строки по 128 символов.

Пять наборов строк, .NET 10. Отношение держится в пределах 3,32–5,58

На всех пяти наборах сортировка без компаратора работает медленнее. Больше всего на строках с одинаковым началом — 3,88–5,58 раза: у них сравнение доходит до конца строки, а не заканчивается на первом символе.

Теперь четыре способа отсортировать массив.

Массив из 10 000 строк, .NET 10. Без компаратора медленнее работают все четыре, но у OrderBy разница меньше

У OrderBy отставание меньше — 2,21–2,92. Он копирует набор и создаёт массив индексов, отсюда и 273,77 килобайта против 78,15 у Array.Sort. Эти расходы одинаковы при любом компараторе, поэтому на их фоне разница между компараторами не так заметна.

Остался размер набора и версия рантайма.

Во сколько раз сортировка без компаратора медленнее сортировки по кодам символов. Отношение держится на всех четырёх рантаймах

На тысяче строк отставание больше, чем на ста тысячах: 5,00–11,71 против 2,99–4,61.

Выводы

По цифрам

• Сортировка без компаратора медленнее сортировки по кодам символов в 5,00–11,71 раза на тысяче строк, в 3,25–5,41 на десяти тысячах и в 2,99–4,61 на ста тысячах.

• На 10 000 строк это 4634,36–6731,95 микросекунды против 1003,47–2073,24.

• Число сравнений у сортировки без компаратора и с Ordinal совпадает на четырёх наборах из пяти: 142 759 на словах, 144 220 на строках с одинаковым началом. Значит, разница во времени приходится на само сравнение.

• Без ICU сортировка без компаратора ускоряется в 2,21–2,69 раза и даёт такие же числа, что и сортировка по кодам символов, а у самой сортировки по кодам символов без ICU ничего не меняется: 0,99–1,06.

• Те же языковые правила, записанные явно через StringComparer.CurrentCulture, работают быстрее, чем без компаратора, в 1,15–1,25 раза.

• На 5 наборах строк отставание держится в пределах 3,32–5,58, больше всего — на строках с одинаковым началом.

• У Array.Sort, List.Sort и Span.Sort отставание 3,12–4,68, у OrderBy — 2,21–2,92.

• Памяти на 10 000 строк уходит 78,15 килобайта у Array.Sort и Span.Sort, 156,33 у List.Sort и 273,77 у OrderBy.

• На .NET 8, 9, 10 и 11 отставание держится в тех же пределах.

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

• Без компаратора строки сравниваются по правилам языка, настроенного на машине, — отсюда и лишнее время.

• Если строки нужно сравнивать по правилам языка, стоит явно указать компаратор: StringComparer.CurrentCulture даёт тот же результат и работает быстрее, чем без него. Культура запоминается в момент создания компаратора, поэтому при смене культуры его нужно создавать заново.

• Переменная DOTNET_SYSTEM_GLOBALIZATION_INVARIANT меняет не только время, но и результат: с ней строки сравниваются по кодам символов.

• Любой способ сортировки без компаратора работает медленнее: у Array.Sort, List.Sort и Span.Sort в 3,12–4,68 раза, у OrderBy — в 2,21–2,92, потому что OrderBy копирует набор и создаёт массив индексов.

Код из статьи

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

Ссылки

• Array.Sort в документации

• Comparer<T>.Default в документации

• Как сравнивать строки в .NET

• Глобализация без ICU

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

• ICU в .NET

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