С релизом .NET 8 в арсенале C# разработчиков появился новый тип коллекций – FrozenDictionary. В серии статей рассмотрим, что представляет собой этот словарь и насколько он быстрее.
FrozenDictionary<TKey, TValue> – это абстрактный класс. У этого класса есть множество реализаций, зависящих от типа ключа, размера коллекции, компаратора. Создаются они при помощи extension-метода ToFrozenDictionary. Стратегия выбора подходящей реализации реализована в статическом классе FrozenDictionary, а именно в методе CreateFromDictionary.
В этой части рассмотрим реализации с ключом значимого типа и с компаратором по умолчанию. Для таких словарей предусмотрены 4 реализации FrozenDictionary:
1. Int32FrozenDictionary.
2. ValueTypeDefaultComparerFrozenDictionary.
3. SmallValueTypeComparableFrozenDictionary.
4. SmallValueTypeDefaultComparerFrozenDictionary.
Int32FrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом типа Int32 используется класс Int32FrozenDictionary. Эта, как и большинство других реализаций
FrozenDictionary, основаны на структуре FrozenHashTable. Это основа «замороженных» словарей. Подробнее о ней я расскажу в последней статье о FrozenDictionary. Пока же достаточно знать, что эта структура содержит в себе множество оптимизаций, которые позволяют быстро производить чтение.Особенность
Int32FrozenDictionary в том, что когда тип ключа – целое число, то его хэш равен его значению и коллизии в таком словаре не возможны в принципе. Нельзя, например, добавить 2 элемента с ключом 123 – будет выброшено исключение. Значит при чтении можно пропустить расчёт хэша и использовать значение ключа напрямую. А при создании словаря, например, пропустить удаление дублирующихся хэшей.Благодаря этому, чтение из
Int32FrozenDictionary быстрее на 36% – 42% (рис. 1).ValueTypeDefaultComparerFrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом любого другого значимого типа, кроме Int32 используется
ValueTypeDefaultComparerFrozenDictionary. В этом случае коллизии могут быть, поэтому при чтении необходим расчёт хэша ключа. Но реализация всё так же основана на FrozenHashTable.Чтение из ValueTypeDefaultComparerFrozenDictionary может быть до 80% быстрее (рис. 2).
Продолжение тут 👇