![](https://habrastorage.org/getpro/habr/upload_files/390/2c2/5b7/3902c25b732abe4275757da548d5e9ca.png)
С релизом .NET 8 в арсенале C# разработчиков появилась новая коллекция – FrozenDictionary. Особенность этого словаря в том, что он неизменяемый, но при этом обеспечивает более быстрое чтение по сравнению с обычным Dictionary
. Я неспроста разбил результаты на обложке по типам – используемые во FrozenDictionary
алгоритмы сильно зависят от типа ключа, размера словаря или даже, например, количества строковых ключей одинаковой длины. В этой статье подробно разберем, насколько FrozenDictionary
быстрее и почему.
Dictionary, ты один приходи. Мы тоже один придём.
Прежде чем начать битву сравнение с Dictionary
, важно заметить, что FrozenDictionary<TKey, TValue>
– это абстрактный класс с множеством реализаций. Точнее, их 18. Вместо объяснений, когда какая реализация используется, проще показать на схеме, поэтому смотрим рисунок 1.
![Рисунок 1 – Выбор реализации FrozenDictionary Рисунок 1 – Выбор реализации FrozenDictionary](https://habrastorage.org/getpro/habr/upload_files/f44/1ab/950/f441ab9500544e3858fe4b9becb28140.png)
Пугаться не стоит, реализации можно разделить на 5 групп по принципу работы:
В DefaultFrozenDictionary и ValueTypeDefaultComparerFrozenDictionary используется структура FrozenHashTable.
В Int32FrozenDictionary тоже используется FrozenHashTable, но нет расчёта хэш-кода, поскольку значение ключа и есть хэш-код.
LengthBucketsFrozenDictionary использует алгоритм, похожий на блочную сортировку.
Реализации OrdinalStringFrozenDictionary тоже используют FrozenHashTable, но в них особенный алгоритм расчёт хэш-кода.
SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary и SmallFrozenDictionary используют линейный поиск, так как размер словарей не превышает 10 элементов.
Выбор подходящей реализации зависит от множества параметров и происходит в методе CreateFromDictionary статического класса FrozenDictionary. Теперь подробно рассмотрим каждую группу по отдельности, изучим их алгоритмы и сделаем замеры.
Дисклеймер
Результаты бенчмарков в этой статье очень условны и верны только при определённых условиях. Допускаю, что бенчмарк может показать другие результаты на другом ПК, с другим ЦП, с другим компилятором или при другом сценарии использования рассматриваемого функционала языка. Всегда проверяйте ваш код на конкретно вашем железе и не полагайтесь лишь на статьи из интернета.
Исходный код бенчмарков и сырые данные результатов можно найти в этом репозитории.
Группа 1. Словари по умолчанию
Как уже было сказано ранее, в DefaultFrozenDictionary
и ValueTypeDefaultComparerFrozenDictionary
используется структура FrozenHashTable
. Эта структура, как можно догадаться из названия, представляет собой реализацию хэш-таблицы. Чтобы лучше понять, чем алгоритм в FrozenHashTable
отличается от Dictionary
, кратко вспомним, как устроен поиск в Dictionary
. Если вы это помните, то можете пропустить объяснение.
Предположим, у нас есть следующий словарь:
var dictionary = new Dictionary<Fruit, string>()
{
[new("apple")] = "APPLE",
[new("grape")] = "GRAPE",
[new("lemon")] = "LEMON",
[new("fig")] = "FIG",
[new("lime")] = "LIME",
[new("kiwi")] = "KIWI",
};
public record Fruit(string Value);
Когда, например, мы ищем значение для ключа Fruit("fig")
, в Dictionary
происходит следующее (рисунок 2):
Вычисляется хэш код ключа
hashCode
.Рассчитывается индекса бакета
bucketIndex
.Если ключ в бакете равен искомому, то возвращается значение. Иначе переходим к следующему ключу с таким же хэш-кодом и повторяем п. 3.
![Рисунок 2 – Пример поиска в Dictionary Рисунок 2 – Пример поиска в Dictionary](https://habrastorage.org/getpro/habr/upload_files/534/4fa/649/5344fa64969890b65ef81a65281fa3bb.png)
Алгоритм поиска
Иммутабельность FrozenDictionary
позволяет иначе реализовать работу с бакетами в FrozenHashTable
. Поскольку количество пар ключ-значение не меняется, то можно:
Подобрать количество бакетов так, что количество коллизий будет не более 5% от количества уникальных хэшей.
Разместить ключи и значения последовательно в массивах
_keys
и_values
, вместо связного списка вDictionary
. Это сделает поиск более эффективным за счет более высокой локальности данных.
При использовании FrozenDictionary
поиск значения для ключа Fruit("fig")
выглядел бы следующим образом (рисунок 3):
Вычисляется хэш код ключа
hashCode
.Рассчитывается индекса бакета
bucketIndex
.В массиве bucket получаем значения
start
иend
, задающие границы в массивеHashCodes
.Итерируем массив
HashCodes
отstart
доend
, в поисках искомого ключа и возвращаем значение при нахождении.
![Рисунок 3 – Пример поиска в DefaultFrozenDictionary Рисунок 3 – Пример поиска в DefaultFrozenDictionary](https://habrastorage.org/getpro/habr/upload_files/7b1/335/a72/7b1335a7238148307ded550661177849.png)
Бенчмарк
Результаты бенчмарков для DefaultFrozenDictionary
и ValueTypeDefaultComparerFrozenDictionary
на рисунках 4 и 5.
![Рисунок 4 – Скорость чтения из ValueTypeDefaultComparerFrozenDictionary по сравнению с Dictionary Рисунок 4 – Скорость чтения из ValueTypeDefaultComparerFrozenDictionary по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/89d/c7d/fb7/89dc7dfb7778bb7ef17f15cd097a4704.png)
![Рисунок 5 – Скорость чтения из DefaultFrozenDictionary по сравнению с Dictionary Рисунок 5 – Скорость чтения из DefaultFrozenDictionary по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/e7a/896/b7f/e7a896b7f3fa9fb4cedb0db78ba4fecd.png)
Высокая скорость поиска в Dictionary
по сравнению с ValueTypeDefaultComparerFrozenDictionary
при размере словаря до 1000 элементов, вероятно, связана с агрессивным инлайном методов Dictionary
. Почему граница именно в 1000 элементов я понять не смог, т.к. в исходном коде ничего об этом нет. Возможно это детали реализации JIT-компилятора. Если у вас есть идеи на этот счет, поделитесь в комментариях.
В остальных случаях, FrozenDictionary
быстрее на 31-32% для значимых типов и 17-18% для ссылочных типов.
Группа 2. Словарь для ключей типа Int32
Int32FrozenDictionary
также использует FrozenHashTable
. Особенность этой реализации в том, что если тип ключа – целое число, то его хэш равен его значению и коллизии в таком словаре не возможны в принципе. Нельзя, например, добавить 2 элемента с ключом 123 – будет выброшено исключение.
var dict = new Dictionary<int, int>();
dict.Add(123, 1);
dict.Add(123, 2);
// System.ArgumentException: An item with the same key has already been added.
Алгоритм поиска
Такая особенность Int32FrozenDictionary
позволяет при чтении пропустить расчёт хэша и использовать значение ключа напрямую. В итоге, поиск значения выглядит так (рисунок 6):
Индекса бакета
bucketIndex
рассчитывается сразу по значению ключа.В массиве
bucket
получаем значенияstart
иend
, задающие границы в массивеHashCodes
.Итерируем массив
HashCodes
отstart
доend
, в поисках искомого ключа и возвращаем значение при нахождении.
![Рисунок 6 – Пример поиска в Int32FrozenDictionary Рисунок 6 – Пример поиска в Int32FrozenDictionary](https://habrastorage.org/getpro/habr/upload_files/27c/48f/412/27c48f412d8c473b5836d72f6866d5a8.png)
Бенчмарк
Благодаря оптимизациям, чтение из Int32FrozenDictionary
быстрее на 34-42% (рисунок 7).
![Рисунок 7 – Скорость чтения из Int32FrozenDictionary по сравнению с Dictionary Рисунок 7 – Скорость чтения из Int32FrozenDictionary по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/dd7/42a/3a7/dd742a3a712eb40b62ba4f35cf0d4509.png)
Группа 3. Словарь с алгоритмом распределения строк по длине
При создании «замороженных» словарей со строковым ключом, FrozenDictionary
в первую очередь попытается создать класс LengthBucketsFrozenDictionary
. Этот класс оптимизирован для ситуаций, когда ключи имеют разную длину. Достигается это распределением ключей по бакетам: для каждой уникальной длины ключа создаётся бакет вместимостью MaxPerLength = 5
элементов. По сути, это реализация блочной сортировки. Чтобы стало понятнее, рассмотрим пример:
var dictionary = new Dictionary<string, string>()
{
["apple"] = "APPLE",
["grape"] = "GRAPE",
["lemon"] = "LEMON",
["fig"] = "FIG",
["lime"] = "LIME",
["kiwi"] = "KIWI",
}
var frozenDictionary = dictionary.ToFrozenDictionary();
В словаре есть ключи длиной 3, 4 и 5 символов. Следовательно, их можно распределить в 3 бакета (рисунок 8):
Бакет для ключей длиной 3:
fig
.Бакет для ключей длиной 4:
lime
иkiwi
.Бакет для ключей длиной 5:
apple
,grape
иlemon
.
![Рисунок 8 – Распределение строк по бакетам на основе их длины Рисунок 8 – Распределение строк по бакетам на основе их длины](https://habrastorage.org/getpro/habr/upload_files/557/a74/b04/557a74b044bed1d94d8573fd49adf2d0.png)
Поскольку известна минимальная (3) и максимальная (5) длина ключей, нет смысла создавать 3 отдельных бакета. Можно всё хранить в одном массиве _lengthBuckets
. В таком случае индекс рассчитывается так: (key.Length - minLength) * MaxPerLength
.
Алгоритм поиска
Поиск осуществляется в 3 шага (рисунок 9):
Определяется бакет в массиве
_lengthBuckets
.Линейным поиском в бакете определяется индекс искомого ключа в
_keys
.Возвращается значение.
![Рисунок 9 – Пример поиска в LengthBucketsFrozenDictionary Рисунок 9 – Пример поиска в LengthBucketsFrozenDictionary](https://habrastorage.org/getpro/habr/upload_files/c56/32c/f86/c5632cf86cf42c118a5d6999d6710ffe.png)
У LengthBucketsFrozenDictionary
есть 2 ограничения:
Количество ключей с одинаковой длиной не должно превышать
MaxPerLength
(принцип Дирихле). Нельзя разместить 6 строк с одинаковой длиной в бакет вместимостью 5 элементов.Количество пустых бакетов должно быть < 20%. Иначе реализация становится неэффективна с точки зрения использования памяти.
Если одно из этих условий не выполняется, то будет выбрана одна из реализаций OrdinalStringFrozenDictionary (о ней далее).
Бенчмарк
Результаты бенчмарка показывают, что чтение из LengthBucketsFrozenDictionary
может быть до 99% быстрее обычного Dictionary
. Но если в словаре количество ключей с одинаковой длиной достигает 5, то производительность небольших словарей (до 100 элементов) может быть хуже (рисунок 10).
![Рисунок 10 – Скорость чтения из LengthBucketsFrozenDictionary по сравнению с Dictionary Рисунок 10 – Скорость чтения из LengthBucketsFrozenDictionary по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/75a/21d/df3/75a21ddf3b63452bd3aa4726b253c33e.png)
Группа 4. Словари с ключом типа string
Как мы уже знаем, у LengthBucketsFrozenDictionary
есть ограничения. Поэтому, если невозможно распределить ключи по бакетам, используется одна из 11 реализаций абстрактного класса OrdinalStringFrozenDictionary. Все они используют FrozenHashTable
, но отличаются алгоритмом расчёта хэш-кода строки.
Выбор оптимальной реализации OrdinalStringFrozenDictionary
зависит от результата анализа ключей классом KeyAnalyzer. На результат влияет длина ключей, наличие не-ASCII символов, заданные правила сравнения строк (StringComparison) и наличие в ключах уникальных подстрок.
Очевидно, что чем длиннее строка, тем медленнее выполняется расчёт хэш-кода. Поэтому KeyAnalyzer
пытается найти подстроки наименьшей длины, позволяющие однозначно идентифицировать ключ. Для лучшего понимания снова рассмотрим пример с фруктами: apple
, grape
, fig
, lime
, lemon
и kiwi
.
Сперва KeyAnalyzer
анализирует подстроки длиной в 1 символ при левостороннем выравнивании ключей (рисунок 11).
![Рисунок 11 – Подстроки длиной в 1 символ при левостороннем и правостороннем выравнивании ключей Рисунок 11 – Подстроки длиной в 1 символ при левостороннем и правостороннем выравнивании ключей](https://habrastorage.org/getpro/habr/upload_files/98c/a15/eb9/98ca15eb96b59ebd6619cfd435ee9721.png)
В нашем примере при левостороннем выравнивании есть повторяющиеся подстроки. Например, 0-й символ lime
и lemon
, 1-й символ fig
и lime
и 2-й символ в lime
и lemon
. То есть невозможно при таком выравнивании однозначно идентифицировать ключ по одному символу. Поэтому поиск подстроки продолжается при правостороннем выравнивании. В этом случае подстроки будут уникальны при использовании 2-го или 1-го символа с конца. Зная выравнивание, индекс начала и длину подстроки можно однозначно идентифицировать строку рассчитав хэш-код её подстроки.
Если уникальных подстрок длиной в 1 символ нет, то поиск продолжится для подстрок в 2 символа, 3 символа, вплоть до максимальной длины подстроки. Это значение рассчитывается как минимальное между minLength
(минимальная длина ключа) и MaxSubstringLengthLimit = 8
. Такое ограничение сделано специально, чтобы не анализировать слишком длинные подстроки, так как их использование не даёт прироста в производительности.
Если уникальных подстрок нет вообще, то расчёт хэш-кода будет производиться для всей строки.
Помимо наличия уникальных подстрок на реализацию также влияют заданные параметры сравнения строк (StringComparison) и наличие не-ASCII символов. В зависимости от этих параметров будет выбран более оптимальный компаратор.
Алгоритм поиска
Поиск в словарях, основанных на OrdinalStringFrozenDictionary
, происходит следующим образом:
Проверяется, находится ли длина ключа в пределах допустимого диапазона. Это нужно для быстрого определения ключей, которые явно не подходят по длине.
Далее, выполняются те же шаги, что мы ранее видели в других словарях с
FrozenHashTable
. Рассчитывается хэш-код подстроки и осуществляется поиск в хэш-таблице. В случае коллизии осуществляется линейный поиск.
Бенчмарк
По результатам бенчмарка, FrozenDictionary
размером до 75 тыс. элементов быстрее обычного Dictionary
. Однако при дальнейшем увеличении размера словаря скорость поиска снижается (рисунок 12).
![Рисунок 12 – Скорость чтения из OrdinalStringFrozenDictionary_LeftJustifiedSubstring по сравнению с Dictionary Рисунок 12 – Скорость чтения из OrdinalStringFrozenDictionary_LeftJustifiedSubstring по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/ab1/d6a/ed3/ab1d6aed3d300cbcead84f125c042bb4.png)
Высокая скорость FrozenDictionary
обусловлена быстрым расчётом хэш-кода ключей. Алгоритм, используемый в FrozenDictionary
, на 75% – 90% быстрее алгоритма обычного Dictionary
(рисунок 13).
![Рисунок 13 – Сравнение скорости расчёта хэша Рисунок 13 – Сравнение скорости расчёта хэша](https://habrastorage.org/getpro/habr/upload_files/3be/b41/f75/3beb41f75b640a1ceec754a014c7ef37.png)
Падение производительности в словарях размером 75 тыс. элементов и более вызвано возрастающим количеством коллизий хэша при увеличении размера словаря (рисунок 14).
![Рисунок 14 – Количество коллизий при расчёте хэшей Рисунок 14 – Количество коллизий при расчёте хэшей](https://habrastorage.org/getpro/habr/upload_files/9ca/fd1/1dc/9cafd11dc20095327a35d2d05599f2c2.png)
Как видно из графиков, алгоритм, используемый в FrozenDictionary
, позволяет ускорить расчёт хэш-кода строки, улучшая производительность до 70%. Однако такой подход негативно сказывается на производительности поиска в относительно больших словарях.
Группа 5. Небольшие словари
SmallValueTypeComparableFrozenDictionary
, SmallValueTypeDefaultComparerFrozenDictionary
используются, когда в исходном словаре не более 10 элементов, а SmallFrozenDictionary
– не более 4-х элементов. При этом, SmallValueTypeComparableFrozenDictionary
применяется, если тип ключа – это встроенный примитивный значимый тип (int
, long
, double
, enum
и т.д.). Если же тип ключа, к примеру, некоторая кастомная структура, то будет использован тип SmallValueTypeDefaultComparerFrozenDictionary
. Такое разделение разработчики .NET объясняют тем, что у встроенных типов 100% реализован интерфейс IComparable
и поэтому можно немного оптимизировать поиск, предварительно отсортировав массивы ключей и значений:
Алгоритм поиска
Строго говоря, классы SmallValueTypeComparableFrozenDictionary
, SmallValueTypeDefaultComparerFrozenDictionary
и SmallFrozenDictionary
– это не хэш-таблицы. Поиск значения в них осуществляется простым линейным поиском через for
(рисунок 15).
![Рисунок 15 – Пример поиска в SmallValueTypeComparableFrozenDictionary Рисунок 15 – Пример поиска в SmallValueTypeComparableFrozenDictionary](https://habrastorage.org/getpro/habr/upload_files/b6f/d31/197/b6fd311970ea3b6ffa5d7488c46491a2.png)
В SmallValueTypeComparableFrozenDictionary
, поскольку массивы _keys
и _value
отсортированы, можно осуществлять поиск пока искомое значение ключа больше текущего значения _keys[i]
.
Реализации SmallValueTypeDefaultComparerFrozenDictionary
и SmallFrozenDictionary
похожи на предыдущую, с тем лишь отличием, что в них не используется сортировка. Соответственно, линейный поиск по массиву ключей _keys
будет осуществлён всегда.
Бенчмарк
Несмотря на все оптимизации в этих классах, результаты бенчмарков не выглядят впечатляющими (рисунок 16). Даже то небольшое ускорение, которое могут дать эти классы, составляет всего лишь несколько десятков наносекунд.
![Рисунок 16 – Скорость чтения из SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary и SmallFrozenDictionary по сравнению с Dictionary Рисунок 16 – Скорость чтения из SmallValueTypeComparableFrozenDictionary, SmallValueTypeDefaultComparerFrozenDictionary и SmallFrozenDictionary по сравнению с Dictionary](https://habrastorage.org/getpro/habr/upload_files/4bf/312/bfc/4bf312bfccc0f1080b2f4239d9908c03.png)
Резюме
В этой статье я постарался разобрать основные моменты, связанные с FrozenDictionary
. Мы убедились, что FrozenDictionary
в большинстве случае действительно быстрее Dictionary
.
На самом деле, в FrozenDictionary
применяется ещё множество алгоритмов и оптимизаций. Например, использование пула массивов ArrayPool
, оптимизированный алгоритм расчёта остатка от деления, использование массива целых чисел с битовыми сдвигами, вместо массива bool
и т.д. Разбор всех деталей не получилось бы сделать в рамках одной статьи. Но я периодически делюсь подобными техническими тонкостями в коротких постах на своём Telegram-канале, поскольку формат Habr не всегда подходит для этого. Если вам интересно, буду рад видеть вас среди читателей.
Комментарии (9)
Furyohfury
23.08.2024 07:35+1Честно не сильно хотел подробно вникать в принципы работы алгоритмов поиска, но как результат, что и при каких условиях быстрее работает, было интересно почитать)
binom82
23.08.2024 07:35Подскажите, в какой программе сделаны иллюстрации схем к статье?
alexeyfv Автор
23.08.2024 07:35+1Диаграммы создаю в app.diagrams.net. Графики рисую в colab.research.google.com через matplotlib, либо через datawrapper.de.
1dNDN
23.08.2024 07:35Гм, а у меня на данных в полмиллиона ссылочных значений и с ключом в виде короткой (до 10 символов) строки изменяемой длины разницы по производительности между обычным словарем и замороженным не было, а вот immutable dictionary очень сильно медленнее был обоих. Проверял на .NET 8.0
mk2
23.08.2024 07:35+1Immutable Dictionary это вообще очень специфичная структура данных. Она не Frozen, есть операции изменения, но при этом каждое изменение создаёт новый Immutable Dictionary. А в старых обьектах остаются те же самые значения.
Чтобы такое было возможно, их сделали на базе деревьев, а не хеш-таблицы. Соответственно стоимость поиска ключа и стоимость изменения - O(logN), в отличие от O(1) у Dictionary и FrozenDictionary.
alexeyfv Автор
23.08.2024 07:35+1Для 500k элементов разницы действительно может не быть. В моём бенчмарке при 100k элементах и строке в виде GUID скорость поиска FrozenDictionary была хуже Dictionary. Чтобы понять, почему у вас именно так, нужно посмотреть какой тип словаря был выбран. Возможно OrdinalStringFrozenDictionary_Full. В нём расчёт хэша происходит по полной строке.
atomlib
На Хабре уже больше года как заведён раздел «Посты», который буквально для таких коротких (до 1500 символов) публикаций и предназначен.
А в «Телеграме» у меня чат с мамой. С моей точки зрения, «Телеграм» для чтения и ведения блогов абсолютно не предназначен. Публикация в «Телеграме» выглядит как сообщение, нет возможности чередовать текст и изображения, есть куча разных ограничений, отсутствует РСС.
Зачем заводить и вести айтишные блоги в мессенджере, который ещё непонятно как индексируется поисковиками — загадка. С таким же успехом можно пытаться делиться опытом в «Снэпчате» или просить подписаться на аккаунт в «ТикТоке». Для меня каналы в «Телеграме» выглядят как очередное коллективное помешательство.
alexeyfv Автор
Посмотрел функционал постов на Хабре. Не получается прикрепить больше одной картинки. Даже короткий пост про один простой бенчмарк требует поясняющих диаграмм, одного или нескольких графиков. В Telegram можно прикрепить до 10 картинок в сообщении. Но вы натолкнули на идею, что можно попробовать всё скомпоновать в одну картинку. Я попробую, спасибо.
fedorro
Статья хорошая, автору спасибо!
Посты на Хабре для этого ещё менее пригодны - монетизации нет или хромает, кол-во просмотров не очень, возможно реклама запрещена, ну и другие ограничения (возможно ошибаюсь по этим пунктам, может кто меня поправит - в Посты не вникал) - не очень удобно так блоггером работать. Сам не блоггер, посты не постил и в них не хожу могу ошибаться, просто пытаюсь смотреть на вещи непредвзято со стороны обоих сторон.
Навязчивая реклама блогов на Хабре с пустыми статьями от ИИ раздражает, а ненавязчивая ссылка под хорошей статьей - вполне себе приемлемо, как по мне.