StringSortProof

Замер того, сколько времени уходит на сортировку строк, когда компаратор не передан.

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

---

Главный результат

Массив из 10 000 английских слов, .NET 10, микросекунды:

Чем задан порядок	Комп 1	Комп 2	Комп 3	Комп 4
без компаратора	4 788,84	4 634,36	6 607,53	6 731,95
StringComparer.CurrentCulture	4 070,42	4 034,92	5 545,05	5 739,46
StringComparer.InvariantCulture	4 102,68	3 884,93	5 569,20	5 803,89
StringComparer.Ordinal	1 214,38	1 003,47	1 673,43	2 073,24
StringComparer.OrdinalIgnoreCase	1 424,79	1 277,66	2 001,62	2 422,15
string.CompareOrdinal	1 147,50	1 171,55	1 496,15	1 938,42

Число сравнений при этом одинаковое: отчёт calls печатает его рядом. Сортировка делает одну и ту же работу, а разница приходится на само сравнение.

Отчёт timing снимает то же самое ещё раз с отключённым ICU: без него сортировка без компаратора ускоряется в 2,21–2,69 раза и даёт такие же числа, что и сортировка по кодам символов.

---

Как воспроизвести

Нужны рантаймы 8, 9, 10 и 11. Одиннадцатый обязателен: замеры идут сразу на четыре цели одним прогоном.

all.bat

Он снимает замеры BenchmarkDotNet и все четыре отчёта — calls, orders, checks и timing — на каждом из четырёх рантаймов, а timing ещё и в трёх дополнительных режимах.

Отдельные шаги:

dotnet run -c Release -f net10.0                все замеры, четыре рантайма
dotnet run -c Release -f net10.0 -- calls       сравнений на запись
dotnet run -c Release -f net10.0 -- orders      порядок при разных языках
dotnet run -c Release -f net10.0 -- checks      сверка ответов
dotnet run -c Release -f net10.0 -- timing      замер без BenchmarkDotNet

---

Как устроен замер

Три класса замеров.

• ComparerBench — чем задан порядок: без компаратора, CurrentCulture, InvariantCulture, Ordinal, OrdinalIgnoreCase и сравнение по кодам символов делегатом. Наборы из 1000, 10 000 и 100 000 строк;
• DatasetBench — тот же вопрос на пяти наборах строк;
• ContainerBench — тот же вопрос у Array.Sort, List.Sort, Span.Sort и OrderBy.

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

Что закрыто замером, а не словами:

• Дело не в алгоритме. Отчёт calls считает обращения к компаратору. Все варианты получают компаратор объектом и обращаются к нему через IComparer<string>, поэтому путь до сравнения у них одинаковый, а числа сравнимы между собой.
• Дело не в том, какие строки взяты. DatasetBench работает на пяти наборах: строки-числа, английские слова, строки с одинаковыми первыми 14 символами, слова с надстрочными знаками и строки по 128 символов.
• Дело не в длине строк. Набор long состоит из строк по 128 символов, набор words — из строк по 4–11.
• Дело не в одинаковом начале строк. Набор prefix целиком состоит из строк с одинаковыми первыми 14 символами.
• Дело не в Array.Sort. ContainerBench повторяет ту же пару у List.Sort, Span.Sort и OrderBy.
• Дело не в том, чем задан порядок. Сравнение по кодам символов снято и объектом-компаратором, и делегатом.
• Результаты у вариантов разные, и это видно. Отчёт calls печатает рядом с числом сравнений, совпал ли порядок с порядком по кодам символов. На наборе с надстрочными знаками не совпадает.
• Порядок зависит от языка. Отчёт orders сортирует один набор по правилам пяти языков и печатает строки целиком.
• Каждая запись возвращает отсортированный набор. Сверяет отчёт checks: результат проверяется по правилу того компаратора, которым сортировали. При расхождении прогон останавливается.
• Не артефакт BenchmarkDotNet. Отчёт timing меряет то же самое на Stopwatch из отдельного процесса, тремя проходами с печатью разброса.
• Не следствие динамического профиля. timing снимается ещё раз с DOTNET_TieredPGO=0.
• Не следствие сборщика. timing снимается ещё раз на серверном сборщике.
• Сколько из разницы приходится на правила языка. timing снимается ещё раз с DOTNET_SYSTEM_GLOBALIZATION_INVARIANT=1: без ICU строки сравниваются по кодам символов.

Замеры BenchmarkDotNet идут одним прогоном сразу на четырёх рантаймах. Версия 0.15.8 не знает про net11.0: запуск под ним падает на проверке с NotImplementedException. Поэтому BenchmarkConfig задаёт цели строками через CsProjCoreToolchain, а сам прогон запускается под net10.0.

---

Что где лежит

StringSortProof.csproj       net8.0;net9.0;net10.0 (+net11.0 при SDK 11)
StringSortProof.slnx
Program.cs                   точка входа и отчёты
BenchmarkConfig.cs           четыре рантайма одним прогоном
Subjects.cs                  все измеряемые записи
all.bat                      весь прогон
Counting/                    наборы строк, компараторы и счётчик обращений
Benchmarks/                  три класса замеров
Diagnostics/                 отчёты вне BenchmarkDotNet
Results/
    Comp_1  Intel Core i9-10900KF 3.70GHz, 10 ядер, Windows 10 22H2
    Comp_2  AMD Ryzen 9 5950X 3.39GHz, 16 ядер, Windows 10 1809
    Comp_3  Intel Xeon W-2255 3.70GHz, 10 ядер, Windows Server 2022
    Comp_4  Intel Xeon Silver 4314 2.40GHz, 2 CPU, 32 ядра, Windows Server 2022

В каждой папке машины:

Bdn/results/                 отчёты BenchmarkDotNet: csv, md, html
calls_netN.0.txt             сравнений на запись и совпадение порядка
orders_netN.0.txt            порядок при разных языках
checks_netN.0.txt            сверка ответов
timing_netN.0.txt            замер на Stopwatch
timing_netN.0_nopgo.txt      то же без динамического профиля
timing_netN.0_servergc.txt   то же на серверном сборщике
timing_netN.0_noicu.txt      то же без ICU

Рантаймы в приложенных прогонах: 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 здесь — предварительная сборка. К релизу числа могут измениться.

---

Ссылки

• Array.Sort в документации
• Comparer<T>.Default в документации
• Как сравнивать строки в .NET
• ICU в .NET
• Глобализация без ICU
• dotnet/BenchmarkDotNet#3017 — поддержка .NET 11