А чё, так можно было? Dictionary == List

Ключ-структура из числа и строки. Поиск по словарю на 10 000 таких ключей занимает 74 975 микросекунд. Тот же ключ, объявленный record struct, — 3,354 микросекунды.

Разница в 22 354 раза, и берётся она не из сравнения ключей. Все 10 000 записей попали в один бакет: у них одинаковый хеш. Словарь превратился в список, по которому идёт перебор. 

Все машины x64

Рантаймы .NET 8, 9 и 10 — все три в одном запуске BenchmarkDotNet 0.15.8. Числа в тексте с AMD Ryzen 9 5950X, таблицы по всем четырём машинам.

1. Ключ, после которого словарь перестаёт быть словарём

Исходник

Составной ключ вида «тип записи и её имя». Число повторяется, строка у каждой записи своя:

internal struct NumberFirst{    internal int A;      // одно и то же значение    internal string B;   // у каждого ключа своё}

Такой ключ добавляется в обычный словарь:

Dictionary<NumberFirst, int> map = new(count); for (int i = 0; i < count; i++){    map[new NumberFirst { A = 1, B = texts[i] }] = i;}

Что показывает замер

Поиск по словарю из 10 000 записей, 256 обращений за вызов. Все шесть словарей построены из одних и тех же данных, различаются только объявления ключей. 

Микросекунды, .NET 10 

Первая строка медленнее последней в 14 268–23 727 раз в зависимости от машины.

На .NET 8 и .NET 9 разрыв ещё больше: 

Микросекунды, ключ «число, строка»

Отставание от ключа-записи 105 737 раз на .NET 8 и 56 086 на .NET 9. Поиск ускорили втрое от версии к версии, но разрыв остался в тысячи раз.

Причина

Хеш структуры считает ValueType.GetHashCode. В комментарии к методу написано: берётся первое нестатическое поле и его хеш.

// Our algorithm for returning the hashcode is a little bit complex.// We look for the first non-static field and get its hashcode.// If the type has no non-static fields, we return the hashcode of the type.

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

Поле типа string — ссылка. Проверка не проходит, и хеш считается по первому полю. Первое поле у всех ключей набора одинаковое, значит одинаков и хеш.

Отчёт из проекта на наборе из 1000 ключей показывает результат:

  ключ                различных хешей   занято бакетов   самая длинная связка   число, строка                   1          1 из 1103                 1000  сравнение без хеша              1          1 из 1103                 1000  строка, число                1000        671 из 1103                    5  свой хеш                     1000        656 из 1103                    5  запись                       1000        669 из 1103                    5  без ссылок                   1000        661 из 1103                    6

Один занятый бакет из 1103, и в нём все 1000 записей. Поиск перебирает их подряд, как список.

Где легко ошибиться

Решить, что виновата строка. У того же ключа с полями в обратном порядке получается 1000 различных хешей: хеш считается по строке, и он у каждого свой.

Решить, что дело в размере набора. На 1000 ключей разрыв меньше, но он там же: 12 744 микросекунды против 2,792.

2. Дело не в упаковке

Исходник

Первое, о чём думают в такой ситуации, — что структура сравнивается через Equals(object) и упаковывается. Про это уже была отдельная статья, там разница выходила в 5 раз.

Чтобы отделить одно от другого, в замере есть контрольный ключ: сравнение написано вручную, поэтому упаковки нет, а GetHashCode остался базовым.

internal struct EquatableOnly : IEquatable<EquatableOnly>{    internal int A;    internal string B;     public bool Equals(EquatableOnly other) => A == other.A && B == other.B;    public override bool Equals(object? other) => other is EquatableOnly key && Equals(key);     // GetHashCode намеренно не переопределён}

Что показывает замер

Микросекунды, .NET 10

Своё сравнение убирает упаковку и ускоряет поиск в 17,2 раза. До ключа-записи остаётся ещё 1198 раз: записи так и остались в одном бакете, и приходится проходить по каждой.

Причина

Упаковка и хеш друг с другом не связаны. IEquatable отвечает за то, как сравниваются два ключа. GetHashCode отвечает за то, сколько ключей придётся сравнить.

При одном хеше на весь набор второе перевешивает первое на три порядка.

Где легко ошибиться

Реализовать IEquatable и посчитать задачу закрытой. Компилятор предупреждает про несогласованный Equals, но про GetHashCode у структуры не скажет ничего: базовая реализация есть, и формально всё в порядке.

3. Хеши разные, а поиск всё равно медленный

Исходник

Ключ с полями в обратном порядке. Хеш считается по строке, все 1000 значений разные, записи разошлись по 671 бакету:

internal struct TextFirst{    internal string B;    internal int A;}

Что показывает замер

Микросекунды, .NET 10 

Записи разложены по бакетам, а поиск всё равно медленнее в 6,2–9,2 раза.

Причина

Когда проверка не проходит, GetHashCode не просто берёт первое поле. Он уходит в нативный код рантайма, где поля типа перебираются заново, пока не найдётся первое подходящее. Результат этого поиска нигде не сохраняется, поэтому обход повторяется при каждом вызове. Это и есть разница между 30 и 3,4 микросекунды.

У ключа без ссылок внутри проверка проходит, и хеш считается по всем байтам структуры. Всё равно медленнее своего: 10,474 против 4,592.

Где легко ошибиться

Решить, что базовой реализации хватит, раз хеши получаются разными. Разные хеши убирают разницу в тысячи раз, но рефлексия при каждом вычислении хеша остаётся.

4. Как писать ключ-структуру

Исходник

Два рабочих варианта. Первый — объявить ключ записью, тогда сравнение и хеш напишет компилятор:

internal readonly record struct RecordKey(int A, string B);

Второй — переопределить GetHashCode:

public override int GetHashCode() => HashCode.Combine(A, B);

Что показывает замер

Построение словаря из 5000 записей. Тут набор меньше, чем в поиске, и вот почему: когда хеш у всех ключей одинаковый, каждая новая вставка сравнивается со всеми предыдущими. На 10 000 записей такой замер идёт минутами.

Микросекунды, .NET 10 

От 0,79 до 1,24 секунды против ста двадцати микросекунд. Разница от 6211 до 8049 раз.

С памятью картина такая же. За 256 поисков по словарю на 10 000 записей: 

Столбец Allocated, .NET 10, одинаково на четырёх машинах

Причина

Базовое сравнение работает через рефлексию и упаковывает поля. Умножьте на 10 000 записей в бакете — получите 195 миллионов байт на 256 поисков.

У ключа со своим хешем и своим сравнением в куче не появляется ничего.

Где легко ошибиться

Взять record struct и не заметить, что он readonly. Изменяемый ключ в словаре опасен сам по себе: после изменения запись больше не находится.

Границы замеров

Все словари построены из одного массива строк, строки готовятся заранее и в замер не входят. Словарям задана вместимость по числу записей, чтобы увеличения массива не попали в результат.

За один вызов замера поиска идёт 256 обращений, номера ключей взяты равномерно по всему набору. Все 256 обязаны найтись — это проверяет сверка.

Число в ключе одинаково у всех записей набора: так выглядит составной ключ, где первое поле — категория или тип. Если первое поле уникально, все хеши будут разными, но останется рефлексия из третьего раздела.

Все замеры сняты на x64 под Windows, на .NET 8, 9 и 10.

Код из статьи

• KeyHashProof — замеры, отчёты и выгрузки с четырёх машин

Ссылки

• ValueType.GetHashCode: хеш берётся с первого поля

• Проверка, можно ли считать хеш по всем байтам

• Dictionary.FindValue, из которого идёт поиск

• Прошлая статья: та же структура, но про упаковку

• HashCode.Combine

• Record types

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