Замеры к статье «А чё, так можно было? Dictionary == List» — что происходит со словарём, когда ключ-структура содержит ссылку внутри.
BenchmarkDotNet 0.15.8, Release, .NET 8, .NET 9 и .NET 10 в одном запуске, со снятием машинного кода.
Статья: «А чё, так можно было? Dictionary == List»
| Раздел | Что смотрим | Что сравнивается |
|---|---|---|
| 1 | поиск по словарю | шесть видов ключа на одних и тех же данных, два размера словаря |
| 2 | построение словаря | те же шесть ключей, размеры меньше: время растёт как квадрат |
| отчёт | причина | сколько различных хешей, сколько занято бакетов, сколько записей в самом заполненном |
Все шесть построены из одних и тех же данных: число во всех ключах одно и то же, строка у каждого своя. Так выглядит составной ключ вида «тип записи и её имя» или «категория и код».
| Ключ | Объявление | Что с хешем |
|---|---|---|
| число, строка | struct { int A; string B; } |
считается по первому полю |
| сравнение без хеша | то же плюс IEquatable, GetHashCode не переопределён |
считается по первому полю |
| строка, число | struct { string B; int A; } |
считается по строке |
| свой хеш | то же плюс IEquatable и GetHashCode |
по обоим полям |
| запись | readonly record struct(int A, string B) |
по обоим полям, пишет компилятор |
| без ссылок | struct { int A; int B; } |
по всем байтам структуры |
Вариант «сравнение без хеша» — контрольный. У него нет упаковки при сравнении,
потому что реализован IEquatable, а хеш всё равно считается по первому полю.
Он отделяет причину, разобранную в статье про IEquatable, от той, что
разбирается здесь.
| Машина | Процессор | Система |
|---|---|---|
| Комп 1 | Intel Core i9-10900KF 3.70GHz, 10 ядер | Windows 10 22H2 |
| Комп 2 | AMD Ryzen 9 5950X 3.39GHz, 16 ядер | Windows 10 1809 |
| Комп 3 | Intel Xeon W-2255 3.70GHz, 10 ядер | Windows Server 2022 |
| Комп 4 | Intel Xeon Silver 4314 2.40GHz, 2 CPU, 32 ядра | Windows Server 2022 |
Все машины x64. Выгрузки лежат в Results: Comp_1 — i9-10900KF, Comp_2 —
Ryzen 9 5950X, Comp_3 — Xeon W-2255, Comp_4 — Xeon Silver 4314.
256 обращений за вызов.
| Ключ | Комп 1 | Комп 2 | Комп 3 | Комп 4 |
|---|---|---|---|---|
| число, строка | 69 430,125 | 74 974,622 | 91 522,879 | 115 766,058 |
| сравнение без хеша | 4 035,570 | 4 019,258 | 6 848,745 | 6 602,455 |
| строка, число | 30,151 | 30,119 | 34,575 | 44,964 |
| без ссылок внутри | 8,774 | 10,474 | 11,729 | 12,300 |
| свой хеш | 6,143 | 4,592 | 5,908 | 6,483 |
| запись | 4,866 | 3,354 | 4,586 | 4,879 |
Микросекунды, .NET 10. Первая строка медленнее последней в 14 268–23 727 раз.
| Рантайм | Комп 1 | Комп 2 | Комп 3 | Комп 4 |
|---|---|---|---|---|
| .NET 8 | 205 263,676 | 366 908,497 | 275 283,953 | 309 657,300 |
| .NET 9 | 128 643,347 | 178 689,332 | 178 409,297 | 207 162,240 |
| .NET 10 | 69 430,125 | 74 974,622 | 91 522,879 | 115 766,058 |
Микросекунды, ключ «число, строка». Отставание от ключа-записи составляло 105 737 раз на .NET 8 и 56 086 на .NET 9.
| Ключ | Комп 1 | Комп 2 | Комп 3 | Комп 4 |
|---|---|---|---|---|
| число, строка | 793 643,66 | 959 232,75 | 1 161 838,32 | 1 239 249,33 |
| сравнение без хеша | 35 885,39 | 36 388,74 | 66 057,18 | 60 668,67 |
| строка, число | 293,53 | 300,52 | 354,86 | 487,71 |
| свой хеш | 152,21 | 140,60 | 205,36 | 242,26 |
| запись | 127,78 | 119,17 | 171,35 | 193,09 |
Микросекунды, .NET 10. От 0,79 до 1,24 секунды против ста двадцати микросекунд, разница от 6211 до 8049 раз.
| Ключ | Выделено |
|---|---|
| число, строка | 195 638 375 байт |
| строка, число | 47 104 байта |
| без ссылок внутри | 18 432 байта |
| сравнение без хеша | 8 192 байта |
| свой хеш | 0 |
| запись | 0 |
Столбец Allocated, .NET 10, одинаково на четырёх машинах.
ключ различных хешей занято бакетов самая длинная связка
число, строка 1 1 из 1103 1000
сравнение без хеша 1 1 из 1103 1000
строка, число 1000 671 из 1103 5
свой хеш 1000 656 из 1103 5
запись 1000 669 из 1103 5
без ссылок 1000 661 из 1103 6
Нужны SDK .NET 8, 9 и 10: BenchmarkDotNet поднимает по процессу на рантайм.
dotnet --list-sdks
В пути к проекту не должно быть запятых и точек с запятой. BenchmarkDotNet собирает вспомогательный проект и передаёт путь в MSBuild без кавычек, тот разбирает эти знаки как разделители списка свойств и падает с MSB1006. Батник проверяет путь и останавливается сразу.
Весь прогон одной командой:
all.bat
Вручную, без скрипта:
dotnet run -c Release -f net10.0 -- checks
dotnet run -c Release -f net10.0 -- hashes
dotnet run -c Release -f net10.0 -- --filter *
dotnet run -c Release -f net10.0 -- --filter *LookupBench*
Аргумент noasm выключает снятие машинного кода.
Причина любого сбоя записывается в Bdn\KeyHashProof.log.
Все словари строятся из одного массива строк. Строки готовятся в GlobalSetup
и хранятся в массиве: иначе в замер попала бы стоимость их создания.
Словарям задаётся вместимость по числу записей, чтобы в замер не попадали увеличения массива.
За один вызов замера поиска идёт 256 обращений, номера ключей взяты равномерно по всему набору. Все 256 обязаны найтись — это проверяет сверка.
Размеры для построения меньше, чем для поиска. Когда хеш у всех ключей одинаковый, каждая новая вставка сравнивается со всеми предыдущими, и на 10 000 записей такой замер идёт минутами.
Отчёт hashes читает внутренности словаря отражением и выводит число занятых
бакетов и число записей в самом заполненном. Это и есть причина разницы
во времени, а не следствие.
| Что проверялось | Чем |
|---|---|
| Во всех словарях одинаковое число записей | отчёт checks сравнивает Count у шести словарей |
| Поиск находит все ключи | отчёт checks требует ровно 256 попаданий в каждом |
| Хеш совпадает именно у ключей со ссылкой после первого поля | отчёт checks считает число различных хешей на наборе |
| Дело не в упаковке при сравнении | контрольный ключ с IEquatable, но без своего хеша |
| Дело не в строке как таковой | ключ с той же строкой, но объявленной первым полем |
| Причина видна не только по времени | отчёт hashes: занятые бакеты и самый заполненный |
| Результат не зависит от размера | два размера в поиске, два в построении |
| Дело не в сборщике мусора | режим DOTNET_gcServer=1 |
| Дело не в конкретной машине | четыре машины, выгрузки всех четырёх в Results |
| Дело не в конкретной версии | .NET 8, 9 и 10 в одном запуске |
Все замеры сняты на x64 под Windows.
Bdn\results\ отчёты BenchmarkDotNet: csv, md, html, машинный код
Bdn\KeyHashProof.log журнал прогона: причины сбоев только здесь
Results\Comp_N\
checks_netN.0.txt сверка, код возврата
checks_netN.0_servergc.txt то же на серверном сборщике
hashes_netN.0.txt хеши, занятые бакеты и самый заполненный
probe_noasm.txt проба на одном классе без дизассемблера
probe_asm.txt та же проба с дизассемблером
bench\ отчёты BenchmarkDotNet
KeyHashProof.csproj многоцелевой: net8.0, net9.0, net10.0
KeyHashProof.slnx
Program.cs точка входа, разбор аргументов
Subjects.cs построение словарей и поиск по ним
README.md
all.bat весь прогон одной командой
Benchmarks\
LookupBench.cs раздел 1, поиск
BuildBench.cs раздел 2, построение
Types\
BenchmarkConfig.cs три рантайма, дизассемблер, колонки и журнал
Keys.cs шесть видов ключа
Payloads.cs наборы данных и чтение внутренностей словаря
Diagnostics\
Checks.cs сверка, код возврата
Hashes.cs хеши и заполнение словаря
Results\
Comp_1 .. Comp_4\ выгрузки прогона, по папке на машину
- ValueType.GetHashCode: хеш берётся с первого поля
- Проверка, можно ли считать хеш по всем байтам
- Поиск первого поля в нативном коде рантайма
- Dictionary.FindValue, из которого идёт поиск
- Прошлая статья: та же структура, но про упаковку
- HashCode.Combine
- Record types
Числа в этом файле взяты только из отчётов. Отношения посчитаны из исходных значений, а не из округлённых.
Число в ключе одинаково у всех записей набора: так выглядит составной ключ, где первое поле — категория или тип. Если первое поле уникально, все хеши будут разными, но останется обход полей в нативном коде при каждом вычислении хеша.
Ссылки на исходники .NET даны на тег v10.0.0, коммит зафиксирован: main
уедет, и номера строк перестанут совпадать.