В словарь со строковыми ключами добавляют 101 ключ, и поиск по всем ключам занимает 8 763 наносекунды. Добавляют 102-й — поиск занимает 718 наносекунд. Данных стало больше, времени ушло в 12 раз меньше.
Так работает защита Dictionary от ключей, подобранных под его хеш‑функцию. Ниже разобрано, что происходит на 102-й вставке, как словарь вычисляет номер бакета и при чём тут число 101.
Машина | Процессор | Система |
Комп 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 — все три в одном запуске BenchmarkDotNet 0.15.8 с DisassemblyDiagnoser. SDK 11 — предварительная сборка, к релизу числа могут измениться.
1. Что происходит на 102-м ключе
Исходник
Словарь считает, сколько записей он прошёл в одном бакете, пока искал место для нового ключа. Когда счётчик становится больше 100, выполняется это условие:
// Value types never rehash if (!typeof(TKey).IsValueType && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer) { // If we hit the collision threshold we'll need to switch to the comparer // which is using randomized string hashing Resize(entries.Length, true); }
HashCollisionThreshold равен 100. Первым аргументом в Resize передаётся entries.Length — текущая длина массива записей. Новый массив будет такого же размера, и вместимость словаря не изменится.
Второй аргумент Resize равен true. По нему словарь заменяет компаратор и заново вычисляет хеш‑коды всех записей.
IEqualityComparer<TKey> comparer = _comparer = (IEqualityComparer<TKey>)((NonRandomizedStringEqualityComparer)_comparer) .GetRandomizedEqualityComparer(); for (int i = 0; i < count; i++) { if (entries[i].next >= -1) { entries[i].hashCode = (uint)comparer.GetHashCode(entries[i].key); } }
Что показывает замер
Ключи подобраны так, что у всех получается один номер бакета. Словарь создан с вместимостью 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 раза в зависимости от машины.
То же самое на трёх рантаймах, AMD Ryzen 9 5950X:
Ключей в бакете | 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
До замены компаратора все 101 ключ размещены в одном бакете. После замены те же ключи распределены по 180–189 бакетам.
Причина
Пока счётчик коллизий не превысил 100, словарь вычисляет хеш строки нерандомизированной функцией. Она дешевле, но её результат воспроизводим: он зависит только от символов строки и не меняется от запуска к запуску. Зная эту функцию, можно составить набор строк с одним номером бакета. Поиск по такому словарю выполняется за O(n) вместо O(1).
Часто в веб‑приложении ключи берутся из данных запроса: параметров строки запроса, заголовков, полей JSON. Если такие данные попадают в словарь, подобранный набор ключей заставляет процессор перебирать записи одного бакета вместо полезной работы. Такая атака называется hash flooding.
100 коллизий — граница, после которой словарь переходит на компаратор с рандомизированным хешем. Тот добавляет к вычислению случайное число, своё при каждом запуске, поэтому заранее составить набор ключей нельзя. Хеш‑коды вычисляются заново, записи распределяются по бакетам, и поиск снова выполняется за O(1).
В цикле пересчёта видно, зачем в поле next записаны отрицательные значения: хеш заново вычисляется только у записей, где next >= -1. Так словарь отличает занятые записи от тех, что остались после удаления ключей.
Ошибки при замере
Свой компаратор строк полностью выключает эту защиту. Условие срабатывает только тогда, когда компаратор — NonRandomizedStringEqualityComparer, а словарь подставляет его в трёх случаях: компаратор не передан, передан StringComparer.Ordinal, передан StringComparer.OrdinalIgnoreCase. С любым другим компаратором строк замена не выполнится, сколько бы коллизий ни набралось:
свой компаратор до вставок Switch.OwnComparer после 101 вставок Switch.OwnComparer после 102 вставок Switch.OwnComparer замена на вставке не выполнена занятых бакетов 1 из 1103
Все 200 ключей остались в одном бакете. Это не особенность замера: защиту снимает любой компаратор строк, кроме трёх перечисленных выше, — в том числе стандартный StringComparer.InvariantCulture.
Замена выполняется при вставке 102-го ключа, а не 101-го. Счётчик коллизий учитывает записи, уже занимающие бакет, поэтому условие «больше 100» выполняется, когда их 101.
Ключи для замера нельзя брать произвольные, их нужно подобрать. Проект повторяет нерандомизированный хеш строки и вычисление номера бакета. Сверка сравнивает вычисленный хеш с тем, который словарь сохранил в записи, и останавливает прогон при расхождении.
2. Деление, которого нет
Исходник
Номер бакета — остаток от деления хеш‑кода на длину массива бакетов. Вот как он вычисляется:
private ref int GetBucket(uint hashCode) { int[] buckets = _buckets!; #if TARGET_64BIT return ref buckets[HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)]; #else return ref buckets[(uint)hashCode % buckets.Length]; #endif }
В 32-битной сборке применяется оператор%. В 64-битной — вот это:
public static uint FastMod(uint value, uint divisor, ulong multiplier) { uint highbits = (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32); Debug.Assert(highbits == value % divisor); return highbits; }
Множитель вычисляется один раз, когда создаётся массив бакетов: ulong.MaxValue / divisor + 1.
Что показывает замер
Миллион хеш‑кодов, делитель 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 раза.
Причина
Целочисленное деление — самая дорогая арифметическая операция на x86: она занимает десятки тактов и не выполняется конвейером. Когда делитель известен при компиляции, компилятор заменяет деление умножением. Здесь делитель — длина массива бакетов, она меняется каждый раз, когда словарь увеличивается, поэтому такая замена невозможна.
Словарь делает такую замену сам: множитель вычисляется один раз, а дальше остаток получается двумя умножениями и сдвигом. Способ описан Даниэлем Лемиром и добавлен в словарь этим обращением.
Ошибки при замере
Делитель нужно получать в рантайме. Если его записать числом, компилятор заменит деление умножением, и оператор% окажется не медленнее.
Способ работает только в 64-битной сборке: ему нужно умножение 64 на 64 бита. В 32-битной словарь использует оператор%.
3. 101 против 100
Исходник
Рядом с порогом коллизий 100 объявлена ещё одна константа — 101. Числа похожи, объявлены в одном файле, а связи между ними нет.
public const uint HashCollisionThreshold = 100; public const int MaxPrimeArrayLength = 0x7FFFFFC3; public const int HashPrime = 101;
101 используется при выборе размера таблицы, в GetPrime:
for (int i = min | 1; i < int.MaxValue; i += 2) { if (IsPrime(i) && ((i - 1) % HashPrime != 0)) { return i; } }
Что показывает отчёт
Размер таблицы — всегда простое число, но подходит не любое: пропускаются те, у которых p — 1 делится на 101.
Простые числа, отброшенные при подборе размера таблицы: 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
Причина
101 применяется в Hashtable, откуда этот код перешёл в HashHelpers. В Hashtable используется двойное хеширование: шаг перебора следующих ячеек вычисляется по модулю size — 1. Если size — 1 делится на 101, у части ключей шаг оказывается кратным 101, и перебор обходит не все ячейки. Такие размеры заранее исключаются. В комментарии к InitHash сказано, что 101 взяли просто как простое число и выбор был во многом произвольным.
В Dictionary двойного хеширования нет: записи с одинаковым номером бакета складываются в цепочку, и делимость размера на 101 ни на что не влияет. Ограничение осталось от Hashtable, потому что оба типа берут размер таблицы из одного метода.
Замером это не показать: размер выбирается один раз, когда словарь увеличивается, и на время поиска не влияет.
Что ещё есть в исходниках
Поле next хранит два разных значения. У занятой записи это номер следующей записи в том же бакете. У той, что осталась после удаления ключа, — номер следующей свободной, записанный как StartOfFreeList — index, где StartOfFreeList равен -3. Отсюда правило: у занятой записи next не меньше -1, у свободной меньше.
Бакет хранит номер записи, увеличенный на 1. Значение 0 означает, что бакет свободен, а новый массив сразу состоит из нулей. Проходить по нему и записывать -1 при каждом увеличении словаря не нужно.
Отчёт entries выводит и то, и другое. Записи, оставшиеся после удаления ключа, он помечает словом «удалённая»:
после удаления двух ключей бакеты: 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
Границы замеров
Замеры раздела 2 сняты только на x64. В 32-битной сборке словарь использует оператор%, и сравнивать там нечего. Разделы 1 и 3 от разрядности не зависят.
Компаратор, массив бакетов и поле next приватные, публичного доступа к ним нет — проект читает их через рефлексию. Если реализацию словаря изменят, чтение перестанет работать: проект остановится и выведет имя поля, которое не нашёл.
Код из статьи
DictResizeProof — замеры, отчёты и выгрузки с четырёх машин
Ссылки
Всем удачи и до новых встреч!
