Предыдущий пост тут.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 3. Ещё строки.

Сегодня рассмотрим оставшиеся реализации FrozenDictionary с ключом типа string. Напомню, что у LengthBucketsFrozenDictionary есть ограничения: если невозможно распределить ключи по бакетам, будет использоваться одна из 11 реализаций абстрактного класса OrdinalStringFrozenDictionary.

Не стоит пугаться большого количества этих реализаций. Все они основаны на одном и том же принципе – расчёте хэш-кода строки. Отличия заключаются в выборе оптимального алгоритма в зависимости от наличия не-ASCII символов, заданных правил сравнения строк (StringComparison) и наличия в ключах уникальных подстрок. Что это всё значит рассмотрим далее.

💡Выбор оптимальной реализации OrdinalStringFrozenDictionary начинается с анализа ключей классом KeyAnalyzer. Очевидно, что чем длиннее строка, тем медленнее выполняется расчёт хэш-кода. Поэтому KeyAnalyzer пытается найти подстроки наименьшей длины, позволяющие однозначно идентифицировать ключ. Для лучшего понимания рассмотрим пример с фруктами: apple, grape, fig, lime, lemon и kiwi.

Сперва KeyAnalyzer анализирует подстроки длиной в 1 символ при левостороннем выравнивании ключей (рис. 1). В нашем примере есть повторяющиеся подстроки. Например, 0-й символ lime и lemon, 1-й символ fig и lime и 2-й символ в lime и lemon. То есть невозможно при левостороннем выравнивании однозначно идентифицировать ключ по одному символу. Поэтому поиск подстроки продолжается при правостороннем выравнивании. В этом случае при использовании 2-го или 1-го символа с конца подстроки будут уникальны. То есть, зная выравнивание, индекс начала и длину подстроки можно однозначно идентифицировать строку рассчитав хэш-код её подстроки.

Если уникальных подстрок длиной в 1 символ нет, то поиск продолжится для подстрок в 2 символа, 3 символа, вплоть до максимальной длины подстроки. Это значение рассчитывается как минимальное между minLength (минимальная длина ключа) и MaxSubstringLengthLimit = 8. Такое ограничение сделано специально, чтобы не анализировать слишком длинные подстроки, так как их использование не даёт прироста в производительности.

Если уникальных подстрок нет вообще, то расчёт хэш-кода будет производиться для всей строки.

🔍 Поиск в словарях, основанных на OrdinalStringFrozenDictionary, происходит следующим образом:

1. Проверяется, находится ли длина ключа в пределах допустимого диапазона. Это нужно для быстрого определения ключей, которые явно не подходят по длине.
2. Рассчитывается хэш-код подстроки и осуществляется поиск в хэш-таблице.
3. В случае коллизии, осуществляется линейный поиск.

📊 В качестве ключей для бенчмарка я использовал GUID. При инициализации FrozenDictionary, KeyAnalyzer выбрал класс OrdinalStringFrozenDictionary_LeftJustifiedSubstring.

По результатам бенчмарка, FrozenDictionary размером до 75 тыс. элементов быстрее обычного Dictionary. Однако при дальнейшем увеличении размера словаря скорость поиска снижается (рис. 2).

Высокая скорость FrozenDictionary обусловлена быстрым расчётом хэш-кода ключей (рис. 3). Алгоритм FrozenDictionary на 90% – 75% быстрее обычного Dictionary.

Падение производительности в словарях размером 75 тыс. элементов и более вызвано возрастающим количеством коллизий хэша при увеличении размера словаря (рис. 4).

Как видно из графиков, алгоритм, используемый в FrozenDictionary, позволяет ускорить расчёт хэш-кода строки, улучшая производительность до 70%. Но в то же время, такой подход негативно сказывается на производительности поиска в относительно больших словарях.

Со словарями с ключом типа string мы закончили. В FrozenDictionary осталось ещё 2 реализации, которые используются для всех остальных случаев, но в них нет ничего примечательного. Их рассмотрим в заключительном посте в серии про FrozenDictionary. Также, как и обещал, в заключительном посте рассмотрим класс FrozenHashTable – основу большинства «замороженных» словарей.