Переопределение Equals и GetHashCode. А оно надо?

Если вы знакомы с C#, то, скорее всего, знаете, что необходимо всегда переопределять Equals, а также GetHashCode, чтобы избежать снижения производительности. Но что будет, если этого не сделать? Сегодня сравним производительность при двух вариантах настройки и рассмотрим инструменты, помогающие избегать ошибок.

Насколько серьезна эта проблема?

Не каждая потенциальная проблема с производительностью влияет на время выполнения приложения. Метод Enum.HasFlag не очень эффективен (*), но если не использовать его на ресурсоемком участке кода, то серьезных проблем в проекте не возникнет. Это верно и случае с защищенными копиями, созданными типами non-readonly struct в контексте readonly. Проблема существует, но вряд ли будет заметна в обычных приложениях.

(*) Исправлено в .NET Core 2.1, и, как я уже упоминал в предыдущей публикации, теперь последствия можно смягчить с помощью самостоятельно настроенных HasFlag для более старых версий.

Но проблема, о которой мы поговорим сегодня, особенная. Если в структуре не создаются методы Equals и GetHashCode, то используются их стандартные версии из System.ValueType. А они могут значительно снизить производительность конечного приложения.

Почему стандартные версии работают медленно?

Авторы CLR изо всех сил старались сделать стандартные версии Equals и GetHashCode максимально эффективными для типов значений. Но есть несколько причин, по которым эти методы проигрывают в эффективности пользовательской версии, написанной для определенного типа вручную (или сгенерированной компилятором).

1. Распределение упаковки-преобразования. CLR создан таким образом, что каждый вызов элемента, определенного в типах System.ValueType или System.Enum, запускает упаковку-преобразование (**).

(**) Если метод не поддерживает JIT-компиляцию. Например, в Core CLR 2.1 компилятор JIT распознает метод Enum.HasFlag и генерирует подходящий код, который не запускает упаковку-преобразование.

2. Потенциальные конфликты в стандартной версии метода GetHashCode. При реализации хэш-функции мы сталкиваемся с дилеммой: сделать распределение хэш-функции хорошо или быстро. В ряде случаев можно выполнить и то и другое, но в типе ValueType.GetHashCode это обычно сопряжено с трудностями.

Традиционная хэш-функция типа struct «объединяет» хэш-коды всех полей. Но единственный способ получить хэш-код поля в методе ValueType — использовать рефлексию. Вот почему авторы CLR решили пожертвовать скоростью ради распределения, и стандартная версия GetHashCode только возвращает хэш-код первого ненулевого поля и «портит» его идентификатором типа (***) (подробнее см. RegularGetValueTypeHashCode в coreclr repo на github).

(***) Судя по комментариям в репозитории CoreCLR, в будущем ситуация может измениться.

public readonly struct Location
{
    public string Path { get; }
    public int Position { get; }
    public Location(string path, int position) => (Path, Position) = (path, position);
}
 

var hash1 = new Location(path: "", position: 42).GetHashCode();
var hash2 = new Location(path: "", position: 1).GetHashCode();
var hash3 = new Location(path: "1", position: 42).GetHashCode();
// hash1 and hash2 are the same and hash1 is different from hash3

Это разумный алгоритм пока что-то не пойдет не так. Но если вам не повезло и значение первого поля вашего типа struct совпадают в большинстве экземпляров, то хэш-функция всегда будет выдавать одинаковый результат. Как вы уже догадались, если сохранить эти экземпляры в хэш-наборе или хэш-таблице, то производительность резко упадет.

3. Скорость реализации на основе рефлексии низкая. Очень низкая. Рефлексия — это мощный инструмент, если использовать его правильно. Но последствия будут ужасны, если запустить его на ресурсоемком участке кода.

Давайте посмотрим, как неудачная хэш-функция, которая может получиться из-за (2) и реализации на основе рефлексии, влияет на производительность:

public readonly struct Location1
{
    public string Path { get; }
    public int Position { get; }
    public Location1(string path, int position) => (Path, Position) = (path, position);
}
 
public readonly struct Location2
{
    // The order matters!
    // The default GetHashCode version will get a hashcode of the first field
    public int Position { get; }
    public string Path { get; }
    public Location2(string path, int position) => (Path, Position) = (path, position);
}
 
public readonly struct Location3 : IEquatable<Location3>
{
    public string Path { get; }
    public int Position { get; }
    public Location3(string path, int position) => (Path, Position) = (path, position);
 
    public override int GetHashCode() => (Path, Position).GetHashCode();
    public override bool Equals(object other) => other is Location3 l && Equals(l);
    public bool Equals(Location3 other) => Path == other.Path && Position == other.Position;
}
 

private HashSet<Location1> _locations1;
private HashSet<Location2> _locations2;
private HashSet<Location3> _locations3;

 
[Params(1, 10, 1000)]
public int NumberOfElements { get; set; }
 
[GlobalSetup]
public void Init()
{
    _locations1 = new HashSet<Location1>(Enumerable.Range(1, NumberOfElements).Select(n => new Location1("", n)));
    _locations2 = new HashSet<Location2>(Enumerable.Range(1, NumberOfElements).Select(n => new Location2("", n)));
    _locations3 = new HashSet<Location3>(Enumerable.Range(1, NumberOfElements).Select(n => new Location3("", n)));
    _locations4 = new HashSet<Location4>(Enumerable.Range(1, NumberOfElements).Select(n => new Location4("", n)));
}
 
[Benchmark]
public bool Path_Position_DefaultEquality()
{
    var first = new Location1("", 0);
    return _locations1.Contains(first);
}
 
[Benchmark]
public bool Position_Path_DefaultEquality()
{
    var first = new Location2("", 0);
    return _locations2.Contains(first);
}
 
[Benchmark]
public bool Path_Position_OverridenEquality()
{
    var first = new Location3("", 0);
    return _locations3.Contains(first);
}

                  Method | NumOfElements |          Mean |   Gen 0 | Allocated |
-------------------------------- |------ |--------------:|--------:|----------:|
   Path_Position_DefaultEquality |     1 |     885.63 ns |  0.0286 |      92 B |
   Position_Path_DefaultEquality |     1 |     127.80 ns |  0.0050 |      16 B |
 Path_Position_OverridenEquality |     1 |      47.99 ns |       - |       0 B |
   Path_Position_DefaultEquality |    10 |   6,214.02 ns |  0.2441 |     776 B |
   Position_Path_DefaultEquality |    10 |     130.04 ns |  0.0050 |      16 B |
 Path_Position_OverridenEquality |    10 |      47.67 ns |       - |       0 B |
   Path_Position_DefaultEquality |  1000 | 589,014.52 ns | 23.4375 |   76025 B |
   Position_Path_DefaultEquality |  1000 |     133.74 ns |  0.0050 |      16 B |
 Path_Position_OverridenEquality |  1000 |      48.51 ns |       - |       0 B |

Если значение первого поля всегда одинаково, то по умолчанию хэш-функция возвращает равное значение для всех элементов и хэш-набор эффективно преобразуется в связанный список с O(N) операций вставки и поиска. Число операций заполнения коллекции становится равным O(N^2) (где N — количество вставок со сложностью O(N) для каждой вставки). Это означает, что вставка в набор 1000 элементов даст почти 500 000 вызовов ValueType.Equals. Вот последствия метода, использующего рефлексию!

Как показывает тест, производительность будет приемлемой, если вам повезет и первый элемент структуры будет уникальным (в случае Position_Path_DefaultEquality). Но если это не так, то производительность будет крайне низкой.

Реальная проблема

Думаю, теперь вы догадываетесь, с какой проблемой я недавно столкнулся. Пару недель назад я получил сообщение об ошибке: время выполнения приложения, над которым я работаю, увеличилось с 10 до 60 секунд. К счастью, отчет был весьма подробным и содержал трассировку событий Windows, поэтому проблемное место обнаружилось быстро — ValueType.Equals загружался 50 секунд.

После беглого просмотра кода стало ясно, в чем проблема:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Я использовал кортеж, который содержал пользовательский тип struct со стандартной версией Equals. И, к сожалению, он имел необязательное первое поле, которое почти всегда равнялось String.equals. Производительность оставалась высокой, пока значительно не увеличилось количество элементов в наборе. За считанные минуты инициализировалась коллекция с десятками тысяч элементов.

Всегда ли реализация ValueType.Equals/GetHashCode по умолчанию работает медленно?

И для ValueType.Equals, и для ValueType.GetHashCode есть специальные методы оптимизации. Если у типа нет «указателей» и он правильно упакован (я покажу пример через минуту), тогда используются оптимизированные версии: итерации GetHashCode выполняются над блоками экземпляра, используется XOR размером 4 байта, метод Equals сравнивает два экземпляра, используя memcmp.

// Optimized ValueType.GetHashCode implementation
static INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef)
{
    INT32 hashCode = 0;
    INT32 *pObj = (INT32*)pObjRef;
 
   // this is a struct with no refs and no "strange" offsets, just go through the obj and xor the bits
   INT32 size = mt->GetNumInstanceFieldBytes();
   for (INT32 i = 0; i < (INT32)(size / sizeof(INT32)); i++)
       hashCode ^= *pObj++;
  
   return hashCode;
}
 
// Optimized ValueType.Equals implementation
FCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1, Object* obj2)
{
    TypeHandle pTh = obj1->GetTypeHandle();
 
    FC_RETURN_BOOL(memcmp(obj1->GetData(), obj2->GetData(), pTh.GetSize()) == 0);
}

Сама проверка выполняется в ValueTypeHelper::CanCompareBits, она вызывается и из итерации ValueType.Equals, и из итерации ValueType.GetHashCode.

Но оптимизация – очень коварная вещь.

Во-первых, сложно понять, когда она включена; даже незначительные изменения в коде могут включать ее и выключать:

public struct Case1
{
    // Optimization is "on", because the struct is properly "packed"
    public int X { get; }
    public byte Y { get; }
}
 
public struct Case2
{
    // Optimization is "off", because struct has a padding between byte and int
    public byte Y { get; }
    public int X { get; }
}

Дополнительную информацию о структуре памяти см. в моем блоге «Внутренние элементы управляемого объекта, часть 4. Структура полей».

Во-вторых, сравнение памяти вовсе не обязательно даст вам правильный результат. Вот простой пример:

public struct MyDouble
{
    public double Value { get; }
    public MyDouble(double value) => Value = value;
}
 

double d1 = -0.0;
double d2 = +0.0;
 
// True
bool b1 = d1.Equals(d2);
 
// False!
bool b2 = new MyDouble(d1).Equals(new MyDouble(d2));

-0,0 и +0,0 равны, но имеют разные двоичные представления. Это значит, что Double.Equals окажется верным, а MyDouble.Equals — ложным. В большинстве случаев разница несущественна, но представьте, сколько часов вы потратите на исправление проблемы, вызванной этой разницей.

Как избежать подобной проблемы?

Вы можете спросить меня, как упомянутое выше может произойти в реальной ситуации? Один из очевидных способов запуска методов Equals и GetHashCode в типах struct — использование правила FxCop CA1815. Но есть одна проблема: это слишком строгий подход.

Приложение, для которого критически важна производительность, может иметь сотни типов struct, которые не обязательно используются в хэш-наборах или словарях. Поэтому разработчики приложения могут отключить правило, что вызовет неприятные последствия, если тип struct использует измененные функции.

Более правильный подход — предупреждать разработчика, если «неподходящий» тип struct с равными значениями элементов по умолчанию (определенный в приложении или сторонней библиотеке) хранится в хэш-наборе. Конечно же я говорю об ErrorProne.NET и о правиле, которое я туда добавил, как только столкнулся с этой проблемой:



Версия ErrorProne.NET не идеальна и будет «обвинять» правильный код, если в конструкторе используется пользовательский сопоставитель равенства:



Но я все равно думаю, что стоит предупреждать, если тип struct с равными по умолчанию элементами используется не тогда, когда производится. Например, когда я проверил свое правило, то понял, что структура System.Collections.Generic.KeyValuePair <TKey, TValue>, определенная в mscorlib, не перезаписывает Equals и GetHashCode. Маловероятно, что сегодня кто-то определит переменную типа HashSet <KeyValuePair<string, int>>, но я считаю, что даже BCL может нарушить правило. Поэтому полезно обнаружить это, пока не поздно.

Заключение

• Реализация равенства по умолчанию для типов struct может привести к серьезным последствиям для вашего приложения. Это реальная, а не теоретическая проблема.
• Элементы равенства по умолчанию для типов значений основаны на рефлексии.
• Распределение, выполненное стандартной версией GetHashCode, будет очень плохим, если первое поле многих экземпляров имеет одинаковое значение.
• Для стандартных методов Equals и GetHashCode существуют оптимизированные версии, но не стоит на них полагаться, поскольку их может выключить даже небольшое изменение кода.
• Используйте правило FxCop, чтобы убедиться, что каждый тип struct переопределяет элементы равенства. Однако лучше предупредить проблему при помощи анализатора, если «неподходящая» структура хранится в хэш-наборе или в хэш-таблице.

Дополнительные ресурсы

• ErrorProne.NET на github
• ErrorProne.NET Structs в магазине