Бенчмаркая FrozenDictionary: заменил Dictionary — получил от ×0,76 до ×1,9

Уважаемые читатели, в этой статье я хочу рассказать о том, насколько FrozenDictionary на деле быстрее обычного Dictionary — и представить свои выводы.

FrozenDictionary появился в .NET 8 для словарей, которые собирают один раз при старте приложения, а дальше только читают: конфигурации, таблицы маршрутизации, соответствия строк. Устроен он так: при создании анализирует набор ключей и подбирает под него внутреннюю реализацию, поэтому чтение получается быстрее, чем у обычного Dictionary.

Замеры на четырёх машинах и трёх рантаймах показали, что выигрыш есть, но он сильно зависит от размера набора и от того, как устроены ключи. У обычного Dictionary версия рантайма на результат почти не влияет: между .NET 8 и .NET 10 разница держится в пределах 9% и на части замеров идёт в минус. А вот Frozen за те же версии заметно ускорился, и разрыв между двумя словарями вырос именно поэтому.

Сравниваются пять способов найти значение по строковому ключу:

• Dictionary;

• FrozenDictionary — неизменяемая копия словаря, которую рантайм при создании подгоняет под конкретный набор ключей;

• ImmutableDictionary — неизменяемый словарь, устроенный как дерево, а не как хэш-таблица;

• ReadOnlyDictionary — обёртка без методов записи; исходный Dictionary при этом остаётся изменяемым;

• switch по строковым константам, если ключи известны при компиляции.

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

• сколько на самом деле выигрывает Frozen — и почему на пяти ключах он проиграл;

• почему он выигрывает — и куда на самом деле уходит время в поиске по строке;

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

Замеры сделаны на четырёх машинах:

BenchmarkDotNet 0.15.8, сборка Release. Патч-версии рантайма на машинах разные: .NET 10.0.5, 10.0.10, 10.0.1 и 10.0.1, у .NET 9 и .NET 8 они тоже не совпадают. На одной машине все три рантайма работают в одинаковых условиях, поэтому сравнивать имеет смысл столбцы внутри машины, а не числа разных машин между собой.

Соседний сюжет про ключи словарей — в статье «Бенчмаркая ключи Dictionary: забыл IEquatable — получил ×5 и 96 байт на каждый поиск».

История 1. Сколько на самом деле выигрывает Frozen

Бенчмарк устроен так: словари со строковыми ключами на 5, 50 и 500 записей, каждый вызов выполняет 256 поисков через TryGetValue. Ключи для поиска выбираются заранее генератором случайных чисел с фиксированным начальным значением, порядок обхода перемешан, чтобы у ветвлений не было искусственно предсказуемого шаблона.

Ключи в двух форматах: короткие вроде k7 и длинные с общим префиксом вида /api/v2/orders/handler_7, как в веб-приложении. Компаратор нигде не задаётся: для строковых ключей Dictionary подставляет свой, об этом во второй истории. GlobalSetup сверяет суммы всех способов между собой и падает при расхождении.

Начнём с главного: 500 коротких ключей, только попадания, все три рантайма (наносекунды на 256 поисков).

500 коротких ключей, попадания: у Dictionary между .NET 8 и .NET 10 разница в пределах 9%, у Frozen — до 24%, но по версиям она раскладывается на каждой машине по-своему

У Dictionary единого направления по рантаймам не видно:

• №1 — .NET 10 быстрее .NET 9 на 9%;

• №2 — медленнее на 5%;

• №3 — медленнее на 4%;

• №4 — медленнее на 7%.

Где-то плюс, где-то минус. За три версии рантайма поиск по строковому ключу у Dictionary остался прежним, и обновление .NET само по себе его не ускорит.

А вот Frozen за те же три версии ускорился, и заметно: с .NET 8 на .NET 9 он выиграл от 6 до 24% в зависимости от машины, с .NET 9 на .NET 10 добавил ещё от 1 до 9%. Так что разрыв между двумя словарями растёт не потому, что Dictionary сдал, а потому, что Frozen подтянулся.

Frozen на 500 ключах быстрее почти везде. Исключение одно: на №1 на .NET 8 разница 24 нс при погрешности замера в 47 нс, то есть там два словаря неразличимы.

Теперь как это выглядит на разных размерах и форматах ключей на .NET 10, во сколько раз Frozen быстрее Dictionary.

 Во сколько раз Frozen быстрее Dictionary на .NET 10: от ×0,76 на пяти ключах маршрутов до ×1,90 на пятидесяти

Итог первой истории:

• на 5 ключах брать Frozen незачем: на коротких ключах он идёт вровень с Dictionary на трёх машинах из четырёх, на ключах маршрутов проигрывает до ×0,76;

• на 50 и 500 ключах Frozen быстрее в 1,06–1,61 раза на коротких ключах;

• на ключах маршрутов с общим префиксом — в 1,47–1,90 раза, и это лучший результат из всех замеренных.

Разброс выигрыша между машинами больше, чем между размерами набора: на 500 коротких ключах Frozen выигрывает ×1,18 на №1 и ×1,61 на №4. Поэтому по одной машине судить нельзя, смотреть надо всю таблицу.

История 2. Почему Frozen быстрее: куда уходит время в поиске по строке

Чтобы понять, откуда берётся разница, я разложил поиск на части. Профиль тот же: 256 поисков, 500 ключей, .NET 10. Меняется только способ:

• Dictionary с компаратором по умолчанию;

• Dictionary с явным StringComparer.Ordinal;

• Dictionary со своим компаратором;

• Dictionary с ключом int;

• HashSet;

• хэширование строки без словаря.

500 ключей, .NET 10: поиск по ключу int в 2,8–4,3 раза быстрее, чем по строковому, а на одно хэширование строки уходит 25–44% времени поиска

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

• строковый ключ отнимает в 2,8–4,3 раза больше времени, чем целочисленный: сам поиск по хэш-таблице не долгий, всё уходит на операции со строкой;

• хэширование строки забирает 25–44% всего поиска, и там, где получается, Frozen хэширует не всю строку, а короткий срез из неё;

• свой компаратор вместо встроенного отнимает ещё 12–46%.

Последние две строки требуют оговорки. Строка «только хэш строки» считает StringComparer.Ordinal.GetHashCode, а это рандомизированный хэш Marvin.

Dictionary с компаратором по умолчанию берёт не его, а внутренний NonRandomizedStringEqualityComparer, и считается он быстрее. Так что 25–44% — это оценка сверху, реальная доля хэша меньше. И 12–46% на своём компараторе объясняются тем же: он считает хэш другим алгоритмом.

Сам быстрый путь виден в машинном коде Dictionary.TryGetValue на .NET 10:

; System.Collections.Generic.Dictionary`2[__Canon,int]:TryGetValue(__Canon,byref):bool (Tier1); Disasm/Listings_Comp_2/disasm_net10.txt     mov      rbp, gword ptr [rbx+0x18]   ; поле _comparer    mov      rcx, 0x7FF9C6484E50         ; адрес таблицы методов ожидаемого типа    cmp      qword ptr [rbp], rcx        ; тот ли это компаратор    jne      G_M000_IG22                 ; нет - уходим на общий путь через вызов    lea      rcx, bword ptr [rsi+0x0C]   ; да - берём символы строки напрямую ; Total bytes of code 760

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

Разница появляется раньше, в конструкторе Dictionary. Три компаратора — дефолтный, StringComparer.Ordinal и StringComparer.OrdinalIgnoreCase — он меняет на свой нерандомизированный, а тот считает хэш быстрее. Поэтому в таблице выше явный Ordinal идёт наравне с дефолтным. Любой другой компаратор остаётся как есть, и хэш считается тем, что написано в нём: у моего это Marvin. Отсюда и потерянные 12–46%.

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

Dictionary это отслеживает: как только в одной цепочке набирается больше ста коллизий (HashHelpers.HashCollisionThreshold), он переключается на рандомизированный компаратор и пересчитывает хэши всей таблицы — в исходниках это видно по комментарию «If we hit the collision threshold we’ll need to switch to the comparer which is using randomized string hashing» в методе вставки Dictionary.cs.

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

Теперь то же самое у Frozen:

; System.Collections.Frozen.FrozenDictionary`2[__Canon,int]:TryGetValue(__Canon,byref):bool (Tier1); Disasm/Listings_Comp_2/disasm_net10.txt     mov      r14d, dword ptr [rbx+0x08]  ; длина строки (поле _stringLength)    mov      ecx, r14d    sub      ecx, dword ptr [rbp+0x20]   ; смещение среза, выбранное при создании    cmp      ecx, dword ptr [rbp+0x24]    ja       G_M000_IG11                 ; длина не подходит - выход без сравнения     lea      rcx, bword ptr [rbx+2*rcx+0x0C] ; адрес среза внутри строки    mov      dword ptr [rsp+0x28], eax       ; длина среза    call     [System.Collections.Frozen.Hashing:GetHashCodeOrdinal(ReadOnlySpan<char>)]

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

Для ключа /api/v2/orders/handler_7 это означает, что из 24 символов в хэш идут единицы — отсюда и ×1,8 на ключах маршрутов, где общий префикс занимает больше половины строки.

Логика подбора среза лежит в KeyAnalyzer.cs в исходниках рантайма, сокращённый фрагмент:

// dotnet/runtime, KeyAnalyzer.cs - TryUseSubstring (сокращено) // срез длиннее 8 символов не берём - анализ перестаёт окупатьсяconst int MaxSubstringLengthLimit = 8; // перебираем длину среза и его позицию в строкеint maxSubstringLength = Math.Min(minLength, MaxSubstringLengthLimit);for (int count = 1; count <= maxSubstringLength; count++){    for (int index = 0; index <= minLength - count; index++)    {        // первый срез, который развёл ключи, становится ключом хэширования    }}

Здесь важно не ошибиться в том, что именно делает срез. Он используется только для вычисления хэша. Само равенство проверяется по всей строке целиком — в том же листинге Frozen дальше идёт вызов SpanHelpers.SequenceEqual, и точно такой же вызов есть у Dictionary.

Frozen не сравнивает ключи по нескольким символам, он только быстрее находит нужную ячейку.

Какую реализацию рантайм выбрал под конкретный набор, можно не угадывать по исходникам, а спросить у него самого:

Console.WriteLine(dict.ToFrozenDictionary().GetType().Name);

.NET 10, компаратор по умолчанию: срез достаётся только трём наборам из шести

На пяти ключах выбирается LengthBucketsFrozenDictionary — он раскладывает ключи по длине строки и хэш не считает. Но у всех пяти ключей длина одинаковая, поэтому раскладывать их не по чему: они оказываются в одной корзине, и поиск сводится к перебору. Обогнать этим хэш-таблицу нечем — на коротких ключах Frozen и Dictionary идут вровень на трёх машинах из четырёх, а на маршрутах Frozen проигрывает.

На 500 коротких ключах выбирается OrdinalStringFrozenDictionary_Full, то есть хэш по всей строке, ровно как у Dictionary. Срез не подобрался: у k0…k499 самая короткая строка в два символа, а двумя символами 500 ключей не развести. Frozen всё равно быстрее в 1,18–1,61 раза, но уже не за счёт хэша: ключи и значения лежат в двух плоских массивах, без цепочек и без двойной адресации через buckets и entries, как в Dictionary.

Срез подобрался для обоих наборов на 50 ключей и для маршрутов на 500, причём везде RightJustified — выровненный по концу строки. Для маршрутов это логично: начало у них общее, различаются только хвостом.

История 3. Промахи, switch по строкам и во сколько обходится создание

Промахи меряются отдельно, и здесь важно, как устроен ключ, которого в наборе нет.

Замеряются два варианта:

• ключ той же формы: набор k0…k499, а ищем k500…k999;

• ключ другой формы: к существующему дописано _miss, то есть он на пять символов длиннее любого из набора.

500 ключей, .NET 10: на промахе той же формы Frozen быстрее Dictionary в 1,2–2,0 раза, на ключе другой длины — в 2,7–5,6 раза

У Frozen два вида промаха различаются в 2,1–2,8 раза, у Dictionary почти не различаются. Причина в листинге из второй истории: первой идёт проверка длины, и ключ, не попавший в диапазон длин набора, отбрасывается до вычисления хэша. Ключ подходящей длины проходит дальше — считается хэш и идёт обращение к таблице.

На промахах Frozen быстрее Dictionary:

• ключ той же формы — в 1,2–2,0 раза;

• ключ другой длины — в 2,7–5,6 раза.

Вторая цифра выше, но в кэше, где промахи выглядят как попадания, работает первая.

Теперь switch. Если набор ключей известен на этапе компиляции, все словари проигрывают обычному switch по строковым константам. Словари в таблице ниже построены на ключах маршрутов, поэтому сравнивать их надо со второй строкой; первая приведена, чтобы видеть switch на коротких ключах.

50 ключей, .NET 10: switch обгоняет Frozen в 2,9–3,6 раза и Dictionary в 4,8–6,7 раза, а длина ключа замедляет его не больше, чем на 29%

Switch обгоняет Frozen в 2,9–3,6 раза, а Dictionary в 4,8–6,7 раза. Длина ключа на это почти не влияет: на маршрутах по 24 символа switch отстаёт от трёхсимвольных не больше, чем на 29%, а на №3 разницы между ними нет.

Компилятор не строит хэш-таблицу: Roslyn разворачивает switch в проверку длины и сравнение символов (изменение вошло в компилятор в PR dotnet/roslyn#66081).

Замеряемый метод выглядит так:

// FrozenProof, Subjects.cs [MethodImpl(MethodImplOptions.NoInlining)]public static int LookupSwitch50(string[] keys){    int sum = 0;    for (int i = 0; i < keys.Length; i++)    {        sum += keys[i] switch        {            "k0" => 0, "k1" => 1, "k2" => 2, "k3" => 3, "k4" => 4,            // ... всего 50 констант            "k49" => 49,            _ => 0,        };    }     return sum;}

В его Tier1-листинге 66 инструкций cmp, 2611 байт кода и ни одного вызова метода. Ни одного вызова — не потому, что компилятор обошёлся без string.Equals, а потому что JIT встроил все пятьдесят сравнений в тело метода: это написано в шапке того же листинга — «50 single block inlinees».

Сам фрагмент сравнения выглядит так:

; FrozenProof.Subjects:LookupSwitch50(System.String[]):int (Tier1); Disasm/Listings_Comp_2/disasm_net10.txt G_M000_IG08:    mov      r10d, dword ptr [r8+0x0C]  ; первые два символа одним словом    mov      r9d, r10d                  ; (поле _firstChar, а не длина)    xor      r9d, 0x31006B              ; сравниваем с символами 'k' и '1'    movzx    r11, word  ptr [r8+0x10]   ; третий символ    xor      r11d, 56                   ; сравниваем с символом '8'    or       r9d, r11d                  ; объединяем оба сравнения    je       G_M000_IG159               ; переход на ветку ключа "k18" ; Total bytes of code 2611

Раскладка полей System.String на x64: по смещению 0x08 лежит длина, по 0x0C — первый символ. Поэтому чтение четырёх байт по 0x0C даёт сразу два символа, а 0x31006B — это ‘k’ (0x006B) и ‘1’ (0x0031). Дальше читается третий символ и сравнивается с ‘8’. Оба сравнения объединяются через or, и вместо двух условных переходов остаётся один.

У подхода есть ограничение: все ключи должны быть записаны в коде строковыми константами. Под 500 ключей пришлось бы писать сотни строк с case, так что на практике switch подходит только небольшим фиксированным наборам.

Теперь создание. Сколько занимает сборка словаря на 500 ключей на .NET 10:

Сборка словаря на 500 ключей, .NET 10: Frozen строится в 5,0–5,8 раза дольше Dictionary, и на сборку уходит 97 КБ против 14,7

Frozen строится в 5,0–5,8 раза дольше Dictionary на 500 ключах и в 6,1–6,9 раза на 50 — это перебор срезов из второй истории. В колонке Allocated у него 97 КБ против 14,7 у Dictionary, но это аллокации за одну сборку, а не размер готового словаря: туда попадают и временные структуры, которые нужны только на время анализа ключей.

Остальные два:

• ImmutableDictionary — медленнее остальных и на сборке, в 13–15 раз, и на чтении, в 2,0–2,3 раза. Внутри AVL-дерево, поиск идёт спуском по узлам со сравнением на каждом. Оттуда же и 32 КБ: каждая пара ключ-значение лежит в отдельном узле со ссылками на потомков. Взамен Add возвращает новый словарь, переиспользуя неизменённые узлы;

• ReadOnlyDictionary — чтение и создание как у Dictionary в пределах 6%, память отличается на 40 байт, размер самой обёртки.

Выводы

По цифрам:

• у Dictionary между .NET 8, 9 и 10 единого направления нет: разница в пределах 9% и на части машин в минус. Frozen за те же версии ускорился на 9–24%, но на какую версию пришёлся прирост — зависит от машины: на №1 и №3 почти весь дала девятка, на №2 десятка дала больше девятки;

• Frozen быстрее Dictionary в 1,06–1,61 раза на 50–500 коротких ключах и в 1,47–1,90 раза на ключах маршрутов с общим префиксом. На 5 коротких ключах выигрыша нет, на 5 маршрутах — проигрыш до ×0,76;

• хэширование строки занимает 25–44% времени поиска — это оценка сверху, снятая на более медленном хэше, чем берёт сам Dictionary. На ключах маршрутов Frozen выигрывает именно на хэше: считается срез до 8 символов, а не вся строка. На коротких ключах срез не подбирается, и выигрыш идёт за счёт внутренней раскладки Frozen;

• компаратор, которого Dictionary не знает, отнимает 12–46%: три известных ему — дефолтный, StringComparer.Ordinal и StringComparer.OrdinalIgnoreCase — он меняет на свой нерандомизированный, а любой другой оставляет как есть, вместе с его хэшем;

• у Dictionary быстрый путь может пропасть во время работы: после сотни коллизий в одной цепочке он сам переключается на рандомизированный хэш и пересчитывает таблицу, что снаружи не видно. У Frozen такого переключения нет, но и цепочки в нём короткие — набор ключей известен при создании;

• на промахах Frozen быстрее в 1,2–2,0 раза, если промах той же формы, и в 2,7–5,6 раза, если ключ не подходит по длине;

• switch по строковым константам быстрее Frozen в 2,9–3,6 раза и Dictionary в 4,8–6,7 раза;

• сборка словаря: Frozen в 5,0–6,9 раза дольше Dictionary, Immutable — в 13–15 раз; ReadOnlyDictionary равен Dictionary.

Что делать на практике:

• набор до десятка ключей — оставить Dictionary, Frozen там ничего не даёт;

• набор от полусотни ключей, собираемый при старте, — Frozen оправдан, и тем сильнее, чем длиннее ключи и чем больше у них общего префикса;

• словарь, который пересоздаётся в горячем коде: Frozen тут не подходит, его сборка занимает в 5–7 раз больше времени, чем у Dictionary;

• небольшой фиксированный набор строковых констант: тут switch быстрее любого словаря;

• без замера свой компаратор для строкового ключа писать не стоит, встроенный быстрее на 12–46%;

• ImmutableDictionary стоит брать там, где словарь читают из нескольких потоков и при этом меняют: Add, SetItem и Remove не трогают исходный словарь, а возвращают новый, и большая часть узлов у них общая. Если нужно только быстрое чтение, он проигрывает всем остальным;

• ReadOnlyDictionary почти не влияет ни на скорость, ни на память. Только это не иммутабельность — у самой обёртки методов записи нет, а исходный Dictionary по своей ссылке меняется как обычно.

Код из статьи

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

Ссылки

• FrozenDictionary — документация

• Разбор Frozen-коллекций в блоге .NET 8

• Исходники System.Collections.Frozen в dotnet/runtime

• Dictionary.cs в dotnet/runtime

• PR dotnet/roslyn#66081 — проверка длины и символов для switch по строкам

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