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

Уважаемые читатели, в этой статье я хочу рассказать, что происходит с Dictionary, когда ключ-структура не реализует IEquatable, — и представить свои выводы.

Структура в роли ключа Dictionary — частый случай: пара int-полей, составной идентификатор, координата. Такой ключ компилируется и работает — по коду проблемы не видно. Если же у структуры нет IEquatable<T>, словарю остаётся сравнивать ключи через 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:

История 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;}

Причина — в выборе компаратора. Для типа без IEquatable EqualityComparer<T>.Default берёт ObjectEqualityComparer: каждое сравнение идёт через Equals(object), хэш — через GetHashCode. У ключа без переопределений это методы базового ValueType; если Equals и GetHashCode переопределены — вызываются они, но сигнатура с object остаётся, а с ней и боксинг. Обе операции принимают object, значит, структуру надо упаковать.

Вот это место в Tier1-листинге FindValue, машина №2, .NET 10:

; Dictionary<PlainKey,int>: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:<CanCompareBitsOrUseFastGetHashCodeHelper>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 в теле метода.

Каждая упаковка — 32 байта: 12 байт полей структуры плюс 16 байт заголовка объекта, с округлением кучи. Много это или мало: на миллионе поисков в секунду выходит 96 МБ/с аллокаций, и вся эта память проходит через GC. Колонка Allocated одинакова на всех четырёх машинах и всех трёх рантаймах.

История 2. Override, IEquatable и record

Все восемь ключей в одной таблице:

Вариант с override Equals и GetHashCode, но без IEquatable, встречается часто: кажется, что раз сравнение переопределено — всё в порядке.

Но это не так! Сигнатура Equals(object) никуда не делась, аргумент боксится на каждом сравнении. Итог — 32 байта на поиск (одна упаковка аргумента Equals(object)) и отставание от IEquatable-варианта в 1,4–2,4 раза. Лучше, чем совсем без переопределений, но проблему не решает.

Для решения вопроса есть несколько вариантов:

• реализовать IEquatable<T>: типизированный Equals без боксов, компаратор вызывается напрямую, без виртуального вызова, сравнение инлайнится;

• record struct. Компилятор сам генерит IEquatable, Equals и GetHashCode.

И тут самое интересное: record (1126 нс) оказался быстрее варианта с IEquatable (1681 нс) — на 33–42% на всех четырёх машинах. Разница не в типе, а в хэш-функции.

Вариант с IEquatable:

public struct EquatableKey : IEquatable<EquatableKey>{    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<int>.Default.GetHashCode(A);      num = num * -1521134295 + EqualityComparer<int>.Default.GetHashCode(B);    num = num * -1521134295 + EqualityComparer<int>.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 лишь избавляет от ручного кода.

Отдельно про неизменяемость: изменение ключа после вставки меняет его хэш-код, и запись теряется. В замерах ключи после вставки не меняются. На уровне типа это закрывается модификатором 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<T>();

Сейчас — нет: рантайм для enum с int-основой отдаёт специализированный EnumEqualityComparer, который кастует enum к его числовому типу и сравнивает числа — без object и без упаковки (ComparerHelpers.cs, метод создания компаратора):

if (t.IsEnum && Enum.GetUnderlyingType(t) == typeof(int)){    return (EqualityComparer<T>)RuntimeTypeHandle        .CreateInstanceForAnotherGenericParameter(            typeof(EnumEqualityComparer<int>), 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 сами. Смотрим:

Даже ключ без IEquatable на десятке быстрее — минус 16% к восьмёрке. Но разрыв ×5 остаётся — по контракту: EqualityComparer<T>.Default подбирает компаратор по интерфейсам типа, без IEquatable<T> остаётся Equals(object) с боксингом. Закрывается разрыв только в самом типе: реализовать IEquatable<T> или объявить ключ как record struct.

Словарь на 100 000 записей сжимает разрыв до ×4,2 (10,34 мкс против 2,49) — в игру вступают кэш-промахи, общие для всех. На miss ключ без IEquatable медленнее в 4,5 раза: Equals может и не вызваться, но GetHashCode с боксингом обязателен всегда.

Выводы

По цифрам:

• struct-ключ без IEquatable<T>: поиск в 4,4–5,7 раза медленнее и 96 байт в куче на каждый успешный TryGetValue — на всех четырёх машинах и всех трёх рантаймах;

• override Equals без IEquatable проблему не решает: отставание в 1,4–2,4 раза и 32 байта на поиск — аргумент боксится в Equals(object);

• record struct оказался быстрее варианта с IEquatable на 33–42% — разница в хэш-функции, а не в типе: каскад, сгенерированный компилятором, работает быстрее HashCode.Combine;

• enum-ключ не боксится и идёт наравне с int;

• с .NET 8 по .NET 10 путь с боксингом ускорился на 16%, но разрыв ×5 рантайм закрыть не может: без IEquatable у словаря нет способа сравнивать ключи, кроме Equals(object) с боксингом.

Что делать на практике:

• у каждого struct-ключа словаря должен быть IEquatable<T> — либо объявить такие ключи как record struct: компилятор сгенерит сравнение сам;

• если у ключа есть только override Equals — добавьте IEquatable<T>: иначе Equals(object) боксит аргумент, 32 байта на поиск;

• если править тип ключа нельзя — передайте в конструктор Dictionary свой IEqualityComparer<T>: типизированный Equals убирает боксинг без правки типа.

Код из статьи

• BoxProof — бенчмарк (8 видов ключей, hit и miss, словари на 16/1000/100000 записей, net8/9/10) и снятие дизасма FindValue

Ссылки

• EqualityComparer.cs — сами компараторы: Generic, Object и EnumEqualityComparer

• EqualityComparer.cs (mscorlib) — боксинг enum в .NET Framework: ObjectEqualityComparer через Equals(object)

• ComparerHelpers.cs (dotnet/runtime) — современный выбор компаратора: EnumEqualityComparer для enum, без упаковки

• ValueType.cs — Equals и GetHashCode общего случая — побитовое сравнение или рефлексия

• Dictionary.cs — FindValue, из которого сняты листинги

• Record types — что компилятор генерит для равенства record

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