Skip to content

README.md

Latest commit

 

History

History
164 lines (132 loc) · 9.84 KB

README.md

File metadata and controls

164 lines (132 loc) · 9.84 KB
Raw

SortComparerProof

Замер того, сколько памяти и времени забирает один вызов Span.Sort с компаратором.

У сортировки есть перегрузка, где тип компаратора задан обобщённым параметром, а не интерфейсом. Её сделали ради компаратора-структуры: такая структура не попадает в кучу, а её сравнение компилятор подставляет в код сортировки. На .NET 8, 9 и 10 каждый её вызов берёт из кучи 88 байт — больше, чем любой другой способ, — и работает она дольше перегрузки с обычным компаратором-классом. В .NET 11 исправлено не всё.

Проект к статье «Бенчмаркая Span.Sort: выбрал компаратор-структуру — и получил 88 байт на вызов».

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

Байты на один вызов, .NET 10, одинаково на всех четырёх машинах и на всех трёх размерах массива:

Способ Байт
без компаратора 0
Comparer<int>.Default 0
кешированный делегат Comparison<int> 0
лямбда, написанная при вызове 0
компаратор-класс 64
компаратор-класс без sealed 64
через Array.Sort и List.Sort 64
структура за переменной IComparer<int> 64
компаратор-структура 88

64 байта — делегат Comparison<T>, 24 — приведение структуры к интерфейсу. На .NET 11 у структуры, переданной по значению, остаётся 0; у остальных способов ничего не меняется.

Числа времени — в Results.

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

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

all.bat

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

dotnet run -c Release -f net10.0                   все замеры, четыре рантайма
dotnet run -c Release -f net10.0 -- allocations    байты на вызов
dotnet run -c Release -f net10.0 -- sizes          из чего они складываются
dotnet run -c Release -f net10.0 -- checks         сверка ответов
dotnet run -c Release -f net10.0 -- timing         замер без BenchmarkDotNet
dotnet run -c Release -f net10.0 -- warmup         прогрев под дизассемблер

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

Три класса замеров, массивы из 16, 256 и 4096 элементов.

  • SortIntBench — шесть способов отсортировать массив целых чисел;
  • SortItemBench — то же на элементе, который не реализует IComparable;
  • BinarySearchBench — двоичный поиск: у него такая же сигнатура с обобщённым параметром.

Замеры идут одним прогоном сразу на четырёх рантаймах. BenchmarkDotNet 0.15.8 не знает про net11.0: запуск под ним падает на проверке с NotImplementedException, а RuntimeMoniker для него не заведён. Поэтому BenchmarkConfig задаёт цели строками через CsProjCoreToolchain, а сам прогон запускается под net10.0. Опорное задание — .NET 10.0, столбец Ratio показывает отличие остальных рантаймов на том же методе.

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

  • Все способы возвращают один ответ. Сверяет отчёт checks: каждый массив проверяется на возрастание и сравнивается с эталоном поэлементно, каждый поиск — с номером, который вернул поиск без компаратора. При расхождении прогон останавливается.
  • Сортируется всегда одно и то же. Перед каждой сортировкой массив восстанавливается из эталонного, иначе второй замер получил бы на вход уже отсортированные данные. Копирование одинаковое у всех способов, а сколько занимает оно само, показывает Copy_Only.
  • Память уходит на вызов, а не на элементы. В отчёте allocations три размера массива подряд, и число байт от размера не зависит.
  • Число байт объясняется арифметикой. Отчёт sizes печатает, сколько занимают делегат Comparison<T> и приведение структуры к интерфейсу; сумма сходится с байтами на вызов.
  • Приведение к интерфейсу отделено от делегата. Sort_BoxedStructComparer передаёт ту же структуру, заранее записанную в переменную типа IComparer<int>. Разница с Sort_StructComparer и есть приведение при вызове.
  • Дело не в модификаторе sealed. Sort_UnsealedComparer передаёт такой же компаратор, но без него.
  • Дело не в лямбде. Sort_InlineComparison пишет лямбду при вызове, Sort_CachedComparison берёт готовый делегат из поля.
  • Дело не в Span. Тот же компаратор через Array.Sort и List.Sort.
  • Дело не в int. SortItemBench работает с типом без IComparable, для которого рантайм берёт другой вспомогательный класс сортировки.
  • Дело не в самой сигнатуре. BinarySearchBench вызывает перегрузку такого же вида с теми же компараторами.
  • Не артефакт BenchmarkDotNet. Байты снимает счётчик рантайма GC.GetAllocatedBytesForCurrentThread из отдельного процесса, время — отчёт timing на Stopwatch, тремя проходами с печатью разброса.
  • Не следствие динамического профиля. timing снимается ещё раз с DOTNET_TieredPGO=0.
  • Не следствие сборщика. timing снимается ещё раз на серверном сборщике.

Что где лежит

SortComparerProof.csproj     net8.0;net9.0;net10.0 (+net11.0 при SDK 11)
SortComparerProof.slnx
Program.cs                   точка входа и отчёты
BenchmarkConfig.cs           четыре рантайма одним прогоном
Subjects.cs                  все измеряемые методы
all.bat                      весь прогон
Comparers/                   компараторы и элемент без IComparable
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
allocations_netN.0.txt       байты на вызов
sizes_netN.0.txt             из чего они складываются
checks_netN.0.txt            сверка ответов
timing_netN.0.txt            замер на Stopwatch
timing_netN.0_nopgo.txt      то же без динамического профиля
timing_netN.0_servergc.txt   то же на серверном сборщике
disasm_netN.0.txt            машинный код измеряемых методов

Рантаймы в приложенных прогонах: 8.0.11–8.0.30, 9.0.4–9.0.19, 10.0.1–10.0.11, 11.0.0 preview 5 и 6. BenchmarkDotNet 0.15.8.

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

Ссылки