Бенчмаркая ключи Dictionary: забыл IEquatable — получил ×5 и 96 байт на каждый поиск

Дата публикации: 25-07-2026 06:14:02

Уважаемые читатели, в этой статье я хочу рассказать, что происходит с Dictionary, когда ключ-структура не реализует IEquatable, — и представить свои выводы.Структура в роли ключа Dictionary — частый случай: пара int-полей, составной идентификатор, координата. Такой ключ компилируется и работает — по коду проблемы не видно. Если же у структуры нет IEquatable, словарю остаётся сравнивать ключи через Equals(object) — а туда структуру можно передать только упаковав её в объект на куче, то есть через боксинг.Ни компилятор, ни анализаторы на это не указывают. В итоге каждый TryGetValue выполняется в несколько раз дольше, чем мог бы, и создаёт объекты, которые потом собирает GC.Будет 3 истории:ключ без IEquatable — поиск в 4,4–5,7 раза медленнее и 96 байт в куче на каждый TryGetValue;почему override Equals не спасает, что даёт IEquatable и почему record struct обогнал IEquatable — дело оказалось не в типе;боксится ли enum-ключ, что поменялось с .NET 8 по .NET 10 и почему сам рантайм этот разрыв закрыть не может.Весь код проверки — в репо BoxProof. Машины те же, что в статьях про Sum и регресс LINQ:№CPUЯдра/потокиЧастота.NET 8 / 9 / 10№1AMD Ryzen 9 5950X16 / 323,4 ГГц базовых и до 4,9 в турбода№2Intel Core i9-10900KF10 / 203,7 ГГц базовых и до 5,3 в турбода№32 × Intel Xeon Silver 4314 (Ice Lake)2×16 / 642,4 ГГц базовых и до 3,4 в турбода№4Intel Xeon W-2255 (Cascade Lake)10 / 203,7 ГГц базовых и до 4,5 в турбодаИстория 1. Ключ без IEquatableКлюч — структура из трёх int. Восемь вариантов на одном словаре из 1000 записей:просто struct;struct с override Equals/GetHashCode но без IEquatable;struct с IEquatable;record struct;enum;Guid;int;string.За один вызов бенчмарка — 256 поисков TryGetValue, ключи распределены по всему словарю, seed фиксирован (12345). GlobalSetup сверяет: hit-набор находит все 256, miss-набор — ноль, иначе падение.Сам ключ выглядит так:public struct PlainKey{ public int A; public int B; public int C;}Struct без IEquatable — 9,16 мкс против 1,68 с ним: разница ×5,4Причина — в выборе компаратора. Для типа без IEquatable EqualityComparer.Default берёт ObjectEqualityComparer: каждое сравнение идёт через Equals(object), хэш — через GetHashCode. У ключа без переопределений это методы базового ValueType; если Equals и GetHashCode переопределены — вызываются они, но сигнатура с object остаётся, а с ней и боксинг. Обе операции принимают object, значит, структуру надо упаковать.Вот это место в Tier1-листинге FindValue, машина №2, .NET 10:; Dictionary:FindValue, Tier1, .NET 10 call CORINFO_HELP_NEWSFAST ; боксинг: новый объект в куче mov dword ptr [rax+0x08], edi ; поле A mov dword ptr [rax+0x0C], ebp ; поле B mov dword ptr [rax+0x10], r14d ; поле C mov rcx, rax call [System.ValueType:GetHashCode():int:this] ; хэш через object; ... call [rax+0x10]System.Object:Equals(System.Object):bool:this; ... call System.ValueType:g____PInvoke|2_0(ptr):intВыделение объекта под боксинг, три mov, которые переносят в него поля A, B и C. Вызов базового GetHashCode, сравнение через Object.Equals — и внутренний хелпер рантайма CanCompareBits: рантайм проверяет, можно ли сравнить такую структуру побитово, не вызывая Equals по полям, и делает это при каждом сравнении — результат не кэшируется.В листинге FindValue три вызова CORINFO_HELP_NEWSFAST — отсюда и 96 байт на поиск: один бокс под GetHashCode и два на сравнение — Equals(object) пакует и сам ключ, на котором вызывается, и аргумент.Три упаковки по 32 байта на успешный поиск; на промахе сравнения нет — остаётся одна, под GetHashCode, те самые 32 байта на miss. И всё это выполняется при каждом обращении к словарю. У IEquatable-ключа в том же FindValue вызовов NEWSFAST ноль — сравнение полей заинлайнено, четыре cmp в теле метода.96 байт на успешный поиск — три упаковки по 32 байта; на промахе — одна: до Equals часто не доходитКаждая упаковка — 32 байта: 12 байт полей структуры плюс 16 байт заголовка объекта, с округлением кучи. Много это или мало: на миллионе поисков в секунду выходит 96 МБ/с аллокаций, и вся эта память проходит через GC. Колонка Allocated одинакова на всех четырёх машинах и всех трёх рантаймах.История 2. Override, IEquatable и recordВсе восемь ключей в одной таблице:Все ключи: hit, miss и аллокации на один поиск; красным — варианты без IEquatableВариант с override Equals и GetHashCode, но без IEquatable, встречается часто: кажется, что раз сравнение переопределено — всё в порядке.Но это не так! Сигнатура Equals(object) никуда не делась, аргумент боксится на каждом сравнении. Итог — 32 байта на поиск (одна упаковка аргумента Equals(object)) и отставание от IEquatable-варианта в 1,4–2,4 раза. Лучше, чем совсем без переопределений, но проблему не решает.Для решения вопроса есть несколько вариантов:реализовать IEquatable: типизированный Equals без боксов, компаратор вызывается напрямую, без виртуального вызова, сравнение инлайнится;record struct. Компилятор сам генерит IEquatable, Equals и GetHashCode.И тут самое интересное: record (1126 нс) оказался быстрее варианта с IEquatable (1681 нс) — на 33–42% на всех четырёх машинах. Разница не в типе, а в хэш-функции.Вариант с IEquatable:public struct EquatableKey : IEquatable{ public int A; public int B; public int C; public bool Equals(EquatableKey o) => A == o.A && B == o.B && C == o.C; public override int GetHashCode() => HashCode.Combine(A, B, C);}И то, что компилятор генерит для record struct:public override int GetHashCode(){ int num = EqualityComparer.Default.GetHashCode(A); num = num * -1521134295 + EqualityComparer.Default.GetHashCode(B); num = num * -1521134295 + EqualityComparer.Default.GetHashCode(C); return num;}Equals в обоих случаях одинаковый — сравнение трёх полей. Вся разница в хэше: HashCode.Combine дополнительно перемешивает значения, каскад складывает их напрямую — отсюда 33–42%.Дело не в самом record — и это проверено контрольным замером: CascadeKey, IEquatable с тем же каскадом вместо HashCode.Combine, идёт с record наравне на всех четырёх машинах (1,00–1,04 на словаре в 1000 записей, .NET 10), а вариант с HashCode.Combine отстаёт от обоих в 1,5–1,7 раза. На остальных размерах словаря и рантаймах картина та же. Record лишь избавляет от ручного кода.Тот же IEquatable с каскад-хэшем идёт наравне с record: 1,00–1,04 на всех машинах×4,4–5,7 на всех четырёх машинах: замедление не зависит от железаОтдельно про неизменяемость: изменение ключа после вставки меняет его хэш-код, и запись теряется. В замерах ключи после вставки не меняются. На уровне типа это закрывается модификатором readonly — readonly struct или readonly record struct.История 3. Enum, рантаймы и почему это не исправятНачну с enum-ключа: ему часто приписывают боксинг, и в старых версиях .NET он действительно был. В .NET Framework компаратор по умолчанию для enum использовал ObjectEqualityComparer, а тот сравнивает через Equals(object) — с упаковкой. Это видно в reference source (mscorlib, EqualityComparer.cs):// Depending on the enum type, we need to special case the comparers// so that we avoid boxing// ...// Otherwise return an ObjectEqualityComparerreturn new ObjectEqualityComparer();Сейчас — нет: рантайм для enum с int-основой отдаёт специализированный EnumEqualityComparer, который кастует enum к его числовому типу и сравнивает числа — без object и без упаковки (ComparerHelpers.cs, метод создания компаратора):if (t.IsEnum && Enum.GetUnderlyingType(t) == typeof(int)){ return (EqualityComparer)RuntimeTypeHandle .CreateInstanceForAnotherGenericParameter( typeof(EnumEqualityComparer), t);}И сам EnumEqualityComparer (реализация из mscorlib; в dotnet/runtime она делает то же самое) — числовое сравнение, ни одного object:public override bool Equals(T x, T y){ int x_final = JitHelpers.UnsafeEnumCast(x); int y_final = JitHelpers.UnsafeEnumCast(y); return x_final == y_final;}По замерам это подтверждается: enum-ключ идёт наравне с int на всех четырёх машинах (×0,91–1,01; местами enum даже чуть впереди — это разброс замера, разницы нет), аллокаций — ноль.Про оставшиеся ключи таблицы. Guid реализует IEquatable — боксинга нет, но ключ 16 байт против четырёх у int, отсюда ×2,1 к нему (1152 нс против 539).String — ×4,3 к int: на каждом поиске хэш считается по всем символам строки, у трёх int-полей он в разы короче. Он сам реализует IEquatable — боксинга здесь нет, дело только в длине хэшируемых данных.Дальше: не ускоряют ли новые рантаймы ключи без IEquatable сами. Смотрим:10,88 → 10,02 → 9,16 мкс с восьмёрки по десятку: −16%, отставание от IEquatable не изменилось — ×5,4Даже ключ без IEquatable на десятке быстрее — минус 16% к восьмёрке. Но разрыв ×5 остаётся — по контракту: EqualityComparer.Default подбирает компаратор по интерфейсам типа, без IEquatable остаётся Equals(object) с боксингом. Закрывается разрыв только в самом типе: реализовать IEquatable или объявить ключ как record struct.Словарь на 100 000 записей сжимает разрыв до ×4,2 (10,34 мкс против 2,49) — в игру вступают кэш-промахи, общие для всех. На miss ключ без IEquatable медленнее в 4,5 раза: Equals может и не вызваться, но GetHashCode с боксингом обязателен всегда.ВыводыПо цифрам:struct-ключ без IEquatable: поиск в 4,4–5,7 раза медленнее и 96 байт в куче на каждый успешный TryGetValue — на всех четырёх машинах и всех трёх рантаймах;override Equals без IEquatable проблему не решает: отставание в 1,4–2,4 раза и 32 байта на поиск — аргумент боксится в Equals(object);record struct оказался быстрее варианта с IEquatable на 33–42% — разница в хэш-функции, а не в типе: каскад, сгенерированный компилятором, работает...

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	Бенчмаркая ключи Dictionary: забыл IEquatable — получил ×5 и 96 байт на каждый поиск	1	9.13	25-07-2026
2	Бенчмаркая Sum: ускорил циклом — замедлил в ×4,7	2	7	18-07-2026
3	Бенчмаркая регресс LINQ: обещали −19%, на четырёх машинах намерил +31%	0	14.72	18-07-2026
4	Бенчмаркая foreach и энумераторы: аллокации, которые прятались 10 лет	0	9.45	11-07-2026
5	Бенчмаркая проверки границ: фикс, который шёл 8  лет, и проверка, которая жива до сих пор	0	11.86	14-07-2026
6	Жертвы чистого кода	0	7	10-07-2026
7	Как я потратил вечер, разбираясь, почему кэш в клоде, gpt и джемини — это три разных зверя	0	6.67	24-07-2026
8	[Перевод] Натуральные ключи в БД. Последний раз объясняю	0	6.24	24-07-2026
9	ЦИФРОВОЙ РЕЗОНАНС: БИТВА ЗА чистый код Тишина в ребе - ...	1	4	29-06-2026

Классификация: Мнения. Схожих патентов: 0. Схожих новостей: 9. Тональность: 0. Информативность: 9.77. Источник: vk.com.