Замеры к статье «А чё, так можно было? +1 ключ = ×12 к скорости» —
как Dictionary защищается от подобранных ключей, почему считает остаток двумя
умножениями и зачем ему число 101.
BenchmarkDotNet 0.15.8, Release, .NET 8, .NET 9 и .NET 10 в одном запуске, со снятием машинного кода.
| Раздел | Место в исходниках | Что сравнивается |
|---|---|---|
| 1 | HashCollisionThreshold и Resize(entries.Length, true) |
поиск в словаре, где 50, 101, 102 и 200 ключей дают один номер бакета |
| 2 | HashHelpers.FastMod в GetBucket |
оператор % против двух умножений со сдвигом |
| 3 | HashHelpers.HashPrime и выбор размера таблицы |
отчёт по исходнику, замер не требуется |
| Машина | Процессор | Система |
|---|---|---|
| Комп 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. Рантаймы 8.0.29, 9.0.18 и 10.0.5, SDK 11 в предварительной
сборке. Выгрузки лежат в Results: Comp_1 — i9-10900KF, Comp_2 — Ryzen
9 5950X, Comp_3 — Xeon W-2255, Comp_4 — Xeon Silver 4314. Журналы прогона
в репозиторий не вошли: они по мегабайту и нужны только при разборе сбоя.
Все ключи набора дают один номер бакета. Словарь создан с вместимостью 1024 — это 1103 бакета, и за время замера массив ни разу не увеличивается.
| Ключей в бакете | Комп 1 | Комп 2 | Комп 3 | Комп 4 |
|---|---|---|---|---|
| 50 | 2 848,3 ± 6,4 | 1 919,9 ± 3,5 | 3 034,1 ± 44,9 | 3 225,3 ± 39,4 |
| 101 | 10 634,3 ± 42,3 | 8 763,5 ± 28,2 | 12 521,8 ± 65,2 | 14 917,5 ± 147,7 |
| 102 | 730,8 ± 1,8 | 718,0 ± 9,3 | 944,2 ± 47,4 | 1 180,5 ± 18,2 |
| 200 | 1 479,5 ± 11,7 | 1 478,2 ± 5,2 | 1 866,2 ± 81,9 | 2 306,4 ± 24,3 |
Наносекунды, среднее и стандартное отклонение, .NET 10. Между 101 и 102 ключами время меняется в 12,21–14,55 раза в зависимости от машины.
То же на трёх рантаймах, Комп 2:
| Ключей в бакете | .NET 8 | .NET 9 | .NET 10 |
|---|---|---|---|
| 101 | 8 725,3 ± 157,7 | 8 609,5 ± 84,7 | 8 763,5 ± 28,2 |
| 102 | 1 066,0 ± 11,4 | 1 056,6 ± 23,2 | 718,0 ± 9,3 |
Отчёт switch выводит имя типа компаратора после каждой вставки. Результат
одинаков на всех четырёх машинах:
компаратор не задан
до вставок NonRandomizedStringEqualityComparer.OrdinalComparer
после 101 вставок NonRandomizedStringEqualityComparer.OrdinalComparer
после 102 вставок RandomizedStringEqualityComparer.OrdinalComparer
замена на вставке 102
занятых бакетов 189 из 1103
С посторонним компаратором строк замена не выполняется, и все 200 ключей остаются в одном бакете:
свой компаратор
до вставок Switch.OwnComparer
после 101 вставок Switch.OwnComparer
после 102 вставок Switch.OwnComparer
замена на вставке не выполнена
занятых бакетов 1 из 1103
Миллион хеш-кодов, делитель 1103, .NET 10.
| Способ | Комп 1 | Комп 2 | Комп 3 | Комп 4 |
|---|---|---|---|---|
оператор % |
1 582,374 ± 1,569 | 1 359,454 ± 2,042 | 1 908,304 ± 19,045 | 2 158,578 ± 23,292 |
| два умножения | 525,076 ± 2,151 | 574,721 ± 2,470 | 622,783 ± 10,758 | 1 006,177 ± 11,437 |
Микросекунды, среднее и стандартное отклонение. Машинного кода на два байта больше — 73 против 71, — а разница во времени в 2,15–3,06 раза.
Размер таблицы — всегда простое число, но подходит не любое: пропускаются те,
у которых p - 1 делится на 101. Отчёт primes:
Простые числа, отброшенные при подборе размера таблицы:
607 (p - 1) / 101 = 6
809 (p - 1) / 101 = 8
1213 (p - 1) / 101 = 12
3637 (p - 1) / 101 = 36
4243 (p - 1) / 101 = 42
Размеры, которые словарь берёт при росте вместимости:
заказано 100 выбрано 101
заказано 1000 выбрано 1009
заказано 10000 выбрано 10007
заказано 100000 выбрано 100003
Отчёт entries выводит содержимое бакетов и поле next у занятых записей
и у тех, что остались после удаления ключа:
после удаления двух ключей
бакеты: 1 3 0 4 6 0 0
запись 0 next -1 живая ключ key0
запись 1 next -2 удалённая ключ нет
запись 2 next -1 живая ключ key2
запись 3 next -1 живая ключ key3
запись 4 next -4 удалённая ключ нет
запись 5 next -1 живая ключ key5
Нужны 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 -- switch
dotnet run -c Release -f net10.0 -- entries
dotnet run -c Release -f net10.0 -- primes
dotnet run -c Release -f net10.0 -- timing
dotnet run -c Release -f net10.0 -- --filter *
dotnet run -c Release -f net10.0 -- --filter *CollisionBench*
Аргумент noasm выключает снятие машинного кода. Батник им пользуется сам,
руками он нужен, только если разбираешь конкретный класс:
dotnet run -c Release -f net10.0 -- --filter *CollisionBench* noasm
Причина любого сбоя лежит в Bdn\DictResizeProof.log: он пишется всегда
и содержит вывод дочернего процесса целиком.
Все измеряемые методы лежат в Subjects.cs, у каждого NoInlining: иначе
компилятор встроит метод в тело замера и удалит как ненужную работу.
Подготовка вынесена в GlobalSetup. В теле замера только то, что измеряется.
Ключи для раздела 1 подобраны так, что все дают один номер бакета. Для этого проект повторяет два внутренних вычисления словаря: нерандомизированный хеш строки и остаток двумя умножениями. Правильность повтора проверяет сверка: она сравнивает вычисленный хеш с тем, который словарь сохранил в записи, и останавливает прогон при расхождении.
Замена компаратора выполняется при вставке 102-го ключа, а не 101-го. Счётчик
коллизий учитывает записи, уже занимающие бакет, поэтому условие «больше 100»
выполняется, когда их 101. Номер вставки выводит отчёт switch.
Компаратор, массив бакетов и поле next приватные, публичного доступа к ним
нет — проект читает их через рефлексию. Если реализацию словаря изменят,
чтение перестанет работать: проект остановится и выведет имя поля, которое
не нашёл.
| Что проверялось | Чем |
|---|---|
| Повтор хеша даёт тот же результат, что рантайм | отчёт checks сравнивает вычисленный хеш с полем записи словаря |
| Ключи получили один номер бакета | отчёт checks считает занятые бакеты: на 101 ключе занят один |
| Замена компаратора выполняется | отчёт switch выводит имя типа компаратора до и после порога |
| Посторонний компаратор снимает защиту | отчёт switch повторяет то же с компаратором, написанным в проекте |
Отрицательные значения в next именно такие |
отчёт entries выводит next у занятых записей и у освободившихся |
| Результат не зависит от размера | замеры раздела 2 на трёх размерах |
| Варианты считают одно и то же | отчёт checks, останавливает прогон при расхождении |
| Результат не зависит от инструмента | отчёт timing работает без BenchmarkDotNet, три прохода |
| Дело не в динамическом профиле | режим DOTNET_TieredPGO=0 |
| Дело не в многоуровневой компиляции | режимы DOTNET_TieredCompilation=0 и DOTNET_ReadyToRun=0 |
| Дело не в сборщике мусора | режим DOTNET_gcServer=1 |
| Дело не в конкретной машине | четыре машины, выгрузки всех четырёх в Results |
| Дело не в конкретной версии | .NET 8, 9 и 10 в одном запуске |
Замеры раздела 2 сняты только на x64. В 32-битной сборке словарь использует
оператор %, и сравнивать там нечего. Разделы 1 и 3 от разрядности
не зависят.
Дизассемблер на Linux требует установленного perf. Выключается аргументом
noasm.
Выгрузки в Results сняты версией проекта, где был ещё один замер — две свои
хеш-таблицы, отличавшиеся только тем, чем обозначен пустой бакет. Выигрыш там
составил 24–31 % на трёх машинах и не появился на четвёртой, поэтому в статью
замер не вошёл, а из проекта убран. В файлах timing_*.txt две его строки
остались.
Bdn\results\ отчёты BenchmarkDotNet: csv, md, html, машинный код
Bdn\DictResizeProof.log журнал прогона: причины сбоев только здесь
Results\Comp_N\
checks_netN.0.txt сверка, роняет прогон при расхождении
switch_netN.0.txt замена компаратора по ходу вставок
entries_netN.0.txt бакеты и поле next
primes_netN.0.txt пропущенные простые числа и выбранные размеры
timing_netN.0.txt замер на секундомере, три прохода
timing_netN.0_nopgo.txt то же без динамического профиля
timing_netN.0_notiered.txt то же без многоуровневой компиляции
timing_netN.0_nor2r.txt то же без готового машинного кода
timing_netN.0_servergc.txt то же на серверном сборщике
probe_noasm.txt проба на одном классе без дизассемблера
probe_asm.txt та же проба с дизассемблером
bench\ отчёты BenchmarkDotNet
DictResizeProof.csproj многоцелевой: net8.0, net9.0, net10.0
DictResizeProof.slnx
Program.cs точка входа, разбор аргументов
Subjects.cs все измеряемые методы
README.md
all.bat весь прогон одной командой
Benchmarks\
CollisionBench.cs раздел 1, поиск среди ключей одного бакета
FastModBench.cs раздел 2, остаток двумя умножениями
Types\
BenchmarkConfig.cs три рантайма, дизассемблер, колонки и журнал
Payloads.cs наборы ключей и повтор внутренних вычислений
Innards.cs чтение внутренних полей словаря
Diagnostics\
Checks.cs сверка, код возврата
Switch.cs замена компаратора
Entries.cs бакеты и поле next
Primes.cs простые числа и число 101
Timing.cs секундомер, три прохода
Results\
Comp_1 .. Comp_4\ выгрузки прогона, по папке на машину
- Порог коллизий в HashHelpers
- Условие замены компаратора в Dictionary
- Какие компараторы включают защиту
- Нерандомизированный хеш строки
- Остаток двумя умножениями
- Обращение, которым его добавили
- Разбор способа у Даниэля Лемира
- Настройки рантайма
Числа в этом файле взяты только из отчётов. Отношения посчитаны из исходных значений, а не из округлённых.
Ссылки на исходники .NET даны на тег v10.0.0, коммит зафиксирован: main
уедет, и номера строк перестанут совпадать.