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

В этой статье я хочу рассказать, сколько памяти и времени уходит на один вызов Span.Sort с компаратором. У сортировки есть перегрузка, где тип компаратора задан обобщённым параметром, а не интерфейсом. Её сделали ради компаратора-структуры: она не попадает в кучу, а её сравнение компилятор подставляет в код сортировки.

На .NET 8, 9 и 10 каждый вызов берёт из кучи 88 байт — больше любого другого варианта. Такая сортировка работает на массиве в 4096 элементов в 1,22–1,75 раза дольше, чем с обычным компаратором-классом, а на массивах меньшего размера разрыв доходит до 3,83 раза. Увы, но проблема в .NET 11 не полностью решена.

Порядок сортировки задают по-разному. В замер попали такие варианты:

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

• через Comparer<int>.Default;

• через кешированный делегат Comparison<int> и через лямбду, написанную при вызове;

• через компаратор-класс — с модификатором sealed и без него;

• через компаратор-структуру по значению и через неё же, заранее записанную в переменную типа IComparer<int>;

• тот же компаратор-класс через Array.Sort и List.Sort.

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

• сколько памяти уходит на один вызов сортировки;

• почему быстрый путь оказался самым медленным;

• что из этого исправили в .NET 11.

Рантаймы: 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 — предварительная сборка, а не выпуск. Всё, что сказано про него дальше, снято на preview 5 и 6, и к выпуску числа могут измениться.

История 1. Сортировка с компаратором расходует память

Компараторов два: один объявлен классом, другой структурой. Код сравнения у них одинаковый.

public sealed class IntClassComparer : IComparer<int>{    public static readonly IntClassComparer Instance = new();    public int Compare(int x, int y) => x.CompareTo(y);}public readonly struct IntStructComparer : IComparer<int>{    public int Compare(int x, int y) => x.CompareTo(y);}

Память считает счётчик рантайма GC.GetAllocatedBytesForCurrentThread. Он суммирует всё, что поток запросил у кучи, и не важно, освободил сборщик мусора эту память или ещё нет. Замер идёт на массивах из 16, 256 и 4096 элементов.

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

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

• копированию массива, сортировке без компаратора, Comparer<int>.Default и делегату память не нужна;

• компаратору-классу нужно 64 байта на каждый вызов, и модификатор sealed на это не влияет;

• компаратору-структуре нужно 88 байт;

• через Array.Sort и List.Sort у этого компаратора те же 64 байта;

• ни одно число не зависит от размера массива: на 16 и на 4096 элементах результат одинаковый.

Раз число не меняется вместе с размером массива, память уходит на сам вызов, а не на элементы и не на сравнения.

Тут два неожиданных результата. Структуре куча не нужна, а памяти на неё уходит больше, чем на класс. И лямбде, написанной при вызове, память не нужна — значит, дело не в том, каким способом задано сравнение.

work.AsSpan().Sort(IntClassComparer.Instance);   // 64 байта на вызовwork.AsSpan().Sort(default(IntStructComparer));  // 88 байт на вызов

Чтобы понять, откуда берутся 64 и 88 байт, отдельный отчёт создаёт каждый объект по одному и делает замеры тем же счётчиком.

Арифметика сходится: 64 + 24 = 88. На каждый вызов создаётся делегат Comparison<T>, а у структуры к нему добавляется приведение к интерфейсу. Третья строка отчёта подтверждает это без вычислений: делегат, взятый от метода структуры, занимает ровно 88 байт — столько же, сколько весь вызов сортировки с этой структурой.

Разделить эти две части помогает четвёртый способ: структуру заранее записывают в поле типа IComparer<int>. Тогда приведение к интерфейсу делается один раз, а не на каждом вызове.

public static readonly IComparer<int> BoxedStructComparer = default(IntStructComparer);work.AsSpan().Sort(BoxedStructComparer);         // 64 байта на вызов

Получается 64 байта — на 24 меньше, ровно столько занимает приведение к интерфейсу. Значит, эти 24 байта уходят на приведение при вызове, а 64 остаются делегатом. Убрать делегат не выйдет: он появляется всегда, когда компаратор передают объектом.

Эта память освобождается быстро, но за неё приходится расплачиваться сборками мусора. Их BenchmarkDotNet считает отдельной колонкой — на массиве в 16 элементов выходит так.

Если отсортировать миллион небольших массивов, с компаратором-структурой сборщик мусора отработает 5,2–8,6 раза, с компаратором-классом — 3,8–6,3 раза. С кешированным делегатом и без компаратора он не сработает ни разу. На .NET 11 с компаратором-структурой сборок тоже нет, у остальных ничего не изменилось.

История 2. Самый быстрый способ оказался самым медленным

Перегрузка, ради которой и берут структуру, объявлена так: тип компаратора задан обобщённым параметром, а не интерфейсом.

// dotnet/runtime, MemoryExtensions.cspublic static void Sort<T, TComparer>(this Span<T> span, TComparer comparer)    where TComparer : IComparer<T>?

Такую перегрузку одобрили ещё в январе 2017 года — dotnet/runtime#19969. В предложении сказано, зачем она нужна: рантайм сможет встроить в сортировку компаратор-структуру. Взамен машинного кода становится больше, а у тех, кто структуры не использует, ничего не меняется.

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

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

• копирование массива занимает 241–4363 наносекунды — на фоне самой сортировки величина незначительная;

• сортировка без компаратора укладывается в 90 508–168 007 наносекунд;

• у делегата и компаратора-класса 128 218–211 004 наносекунды, разница между ними не больше 1,05 раза;

• у компаратора-структуры 183 999–362 117 наносекунд: он медленнее класса в 1,44–1,72 раза, а сортировки без компаратора — в 1,73–2,16 раза на .NET 10;

• у структуры, заранее записанной в переменную типа IComparer<int>, то же самое: 185 760–371 886 наносекунд.

Выделяется Ryzen 9 5950X: копирование того же массива у него занимает 4363 наносекунды против 241–273 на остальных трёх машинах. От рантайма это не зависит — на всех четырёх результат одинаковый. На фоне сортировки 4363 наносекунды составляют 2,37 процента, поэтому на сравнение способов между собой они не влияют. Причину замер не показывает.

Главное — в последних двух строках. Если убрать приведение к интерфейсу из вызова, память уменьшается на 24 байта, а время не меняется. Значит, дело не в приведении. Медленнее работает сама перегрузка с обобщённым параметром — та, которая должна была быть самой быстрой.

Что происходит на самом деле, видно в машинном коде. Вот что вызывается на .NET 10, когда компаратор передан структурой:

; SortComparerProof.Subjects:SortIntsByStructComparer(int[],int[]) (FullOpts)       call     [System.Array:Copy(System.Array,System.Array,int)]       add      rbx, 16       cmp      esi, 1       jle      SHORT G_M000_IG04       mov      rcx, 0xD1FFAB1E       call     CORINFO_HELP_NEWSFAST       mov      rdx, 0xD1FFAB1E       mov      rcx, gword ptr [rdx]       mov      byte  ptr [rax+0x08], 0       mov      bword ptr [rsp+0x28], rbx       mov      dword ptr [rsp+0x30], esi       lea      rdx, [rsp+0x28]       mov      r8, rax       call     [System.Collections.Generic.GenericArraySortHelper`1[int]:                 Sort(System.Span`1[int],                      System.Collections.Generic.IComparer`1[int]):this]; Total bytes of code 111

Вызов CORINFO_HELP_NEWSFAST — это и есть запрос памяти у кучи. А в сигнатуре вызываемого метода написан интерфейс IComparer<int>, а не тип IntStructComparer. Внутри сортировки обобщённого параметра уже нет — вместо него интерфейс, а значит, структуру нужно к этому интерфейсу привести.

Остаётся проверить, что дело не в целых числах и не в Span:

• на элементе без IComparable рантайм использует другой вспомогательный класс сортировки, и там структура медленнее класса в 1,17–1,42 раза — результат тот же;

• у этого же компаратора через Array.Sort и List.Sort всё те же 64 байта;

• у компаратора-класса без модификатора sealed тоже 64 байта.

Об этом в трекере .NET есть открытая задача с июля 2020 года — dotnet/runtime#39466. Написано там ровно то, что показал замер: перегрузка не использует известный тип компаратора и работает хуже остальных. Срок исправления не назначен.

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

Тот же замер на четырёх рантаймах. Строка одна — компаратор-структура, массив в 4096 элементов.

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

• на .NET 8, 9 и 10 время держится в пределах 183 999–373 379 наносекунд, а память — 88 байт;

• на .NET 11 время сокращается до 80 922–166 851, а память — до нуля;

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

На маленьких массивах выигрыш больше: на 16 элементах .NET 11 тратит 0,19–0,32 от времени .NET 10, на 256 — 0,16–0,22, на 4096 — 0,44–0,57. Закономерности тут не видно: сильнее всего выигрыш не на самом маленьком массиве, а на среднем. Ясно одно — чем меньше массив, тем большую долю в вызове занимает подготовка, которую и убрали.

Сравнение с компаратором-классом меняется на противоположное:

В .NET 8, 9 и 10 перегрузка работала медленнее обычного компаратора-класса, который должна была заменить, и только в .NET 11 стала быстрее. Там она сравнялась с сортировкой без компаратора: отношение 0,93–1,05.

Причина видна в машинном коде. Тот же метод, что и в прошлой истории, собранный под .NET 11:

; SortComparerProof.Subjects:SortIntsByStructComparer(int[],int[]) (FullOpts)       call     [System.Array:Copy(System.Array,System.Array,int)]       add      rbx, 16       cmp      esi, 1       jle      SHORT G_M000_IG04       mov      bword ptr [rsp+0x28], rbx       mov      dword ptr [rsp+0x30], esi       lea      rcx, [rsp+0x28]       xor      edx, edx       call     [System.Collections.Generic.ArraySortHelperForTComparer`2[int,                 SortComparerProof.Comparers.IntStructComparer]:                 Sort(System.Span`1[int],                      SortComparerProof.Comparers.IntStructComparer)]; Total bytes of code 78

Вызова CORINFO_HELP_NEWSFAST больше нет, метод стал на 33 байта меньше, а в сигнатуре вызываемого метода вместо интерфейса написан сам тип IntStructComparer. Внутри сортировки обобщённый параметр сохранился, и приводить к интерфейсу стало нечего. 

Но не всё было исправлено. Те же три способа на .NET 10 и .NET 11:

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

• компаратор-класс показывает 0,95–1,00 от времени на .NET 10 и те же 64 байта;

• структура, заранее записанная в переменную типа IComparer<int>, показывает 0,94–1,06 и те же 64 байта;

• и только структура, переданная по значению, показывает 0,44–0,57 и ноль байт.

Разница между второй и третьей строкой показывает, что именно исправили. Компаратор один и тот же, тип один и тот же. Если компаратор передают по значению и компилятор знает точный тип, .NET 11 сохраняет этот тип внутри сортировки. Если тот же компаратор записан в переменную типа интерфейса, всё остаётся как было. Исправили не приведение к интерфейсу и не сам компаратор, а то, доживает ли обобщённый параметр до места, где им можно воспользоваться.

Структура, записанная в переменную типа IComparer<int>, не просто осталась как была — она всё это время медленнее обычного компаратора-класса: в 1,45–1,76 раза на .NET 10 и в 1,49–1,75 раза на .NET 11. Смысл брать структуру появляется только при передаче по значению, иначе память та же, а времени уходит больше.

Остался один вопрос: не касается ли это всех перегрузок с такой же сигнатурой. У двоичного поиска сигнатура такая же — тип компаратора задан обобщённым параметром.

sorted.AsSpan().BinarySearch(value, IntClassComparer.Instance);sorted.AsSpan().BinarySearch(value, default(IntStructComparer));

Память здесь не расходуется, и .NET 11 ничего не меняет: 8,9–20,3 наносекунды на .NET 10 против 8,6–20,4 на .NET 11. Значит, сама сигнатура ни при чём, и вывод про сортировку не распространяется на другие методы с таким же объявлением.

Выводы

По цифрам

• Компаратор-класс забирает 64 байта на вызов сортировки, компаратор-структура — 88. Числа не зависят от размера массива и одинаковы на всех четырёх машинах.

• 64 байта — делегат Comparison<T>, 24 — приведение структуры к интерфейсу. Сумма сходится с памятью на вызов.

• На .NET 8, 9 и 10 компаратор-структура медленнее компаратора-класса в 1,22–1,75 раза на массиве в 4096 элементов, в 2,19–3,83 раза на массиве в 256 и в 1,89–3,00 раза на массиве в 16, а сортировки без компаратора — в 1,73–2,39 раза на 4096, в 3,98–7,53 раза на 256 и в 2,82–4,85 раза на 16.

• На .NET 11 та же строка занимает 0,44–0,57 от времени .NET 10 на массиве в 4096 элементов и 0,16–0,22 на массиве в 256. Память не расходуется.

• Отношение структуры к классу меняется на противоположное: 1,44–1,72 на .NET 10 и 0,65–0,89 на .NET 11.

• Структура, заранее записанная в переменную типа IComparer<T>, на .NET 11 не изменилась: 0,94–1,06 от времени .NET 10 и те же 64 байта.

• Компаратор-класс на .NET 11 не изменился: 0,95–1,00 от времени .NET 10 и те же 64 байта.

• Двоичный поиск с теми же компараторами не расходует память ни на одном из четырёх рантаймов.

• Модификатор sealed у компаратора-класса на память и на время не влияет.

• Кешированный делегат и лямбда, написанная при вызове, память не расходуют.

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

• До .NET 11 компаратор в сортировке расходует память на каждом вызове. Это заметно там, где сортируют много небольших массивов.

• До .NET 11 компаратор-структура расходует больше всех памяти и работает медленнее, чем компаратор-класс или сортировка без компаратора, хотя по коду должен быть самым быстрым.

• Вместо него можно взять кешированный делегат Comparison<T>: памяти он не расходует, а по времени такой же, как компаратор-класс.

• На .NET 11 компаратор-структура обгоняет компаратор-класс и работает наравне с сортировкой без компаратора, но только если передавать его по значению. Если записать его в переменную типа IComparer<T>, всё остаётся как было.

• Записывать структуру в переменную типа IComparer<T> не стоит ни на одном рантайме: так она медленнее обычного компаратора-класса в 1,45–1,76 раза и расходует те же 64 байта.

• На другие перегрузки с такой же сигнатурой вывод не распространяется: у двоичного поиска тот же обобщённый параметр памяти не расходует.

Код из статьи

• SortComparerProof — бенчмарки, прогоны на четырёх машинах и листинги машинного кода

Ссылки

• dotnet/runtime#39466 — задача, с которой начался замер

• dotnet/runtime#19969 — предложение, которым перегрузку добавили

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

• MemoryExtensions.BinarySearch в документации

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

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