To box or not to Box? That is the question

Нашел интересный блог про .NET (C#), который мне очень понравился. Постараюсь время от времени переводить для Вас интереснейшие статьи и будем вместе обсуждать. Спасибо автору за прекрасный материал.

Недавно я заметил, что метод Equals из нашей структуры ValueTuple (*) генерирует значительный memory traffic (~1 ГБ).

Это было для меня неожиданностью, поскольку эта структура используется в сценариях, критичных к производительности. Вот как она выглядит:

public struct ValueTuple<TItem1, TItem2> : IEquatable<ValueTuple<TItem1, TItem2>>
{
    public TItem1 Item1 { get; }
    public TItem2 Item2 { get; }

    public ValueTuple(TItem1 item1, TItem2 item2)
    {
        Item1 = item1;
        Item2 = item2;
    }

    public override int GetHashCode()
    {
        // Реальная реализация немного сложнее. Не простой XOR
        return EqualityComparer<TItem1>.Default.GetHashCode(Item1) ^
            EqualityComparer<TItem2>.Default.GetHashCode(Item2);
    }

    public bool Equals(ValueTuple<TItem1, TItem2> other)
    {
        return (Item1 != null && Item1.Equals(other.Item1)) &&
                (Item2 != null && Item2.Equals(other.Item2));
    }

    public override bool Equals(object obj)
    {
        return obj is ValueTuple<TItem1, TItem2> && 
            Equals((ValueTuple<TItem1, TItem2>)obj);
    }
    // Другие члены, такие как операторы равенства, опущены для краткости
}

(*) Наш ValueTuple был реализован до того, как он появился в Visual Studio в 2017 году, и наша реализация является неизменяемой(immutable).

Методы Equals и GetHashCode переопределены для избегания упаковки (boxing). Проверка на null нужна, чтобы избежать NullReferenceException, если Item1 или Item2 являются объектами ссылочных типов. Проверки на null могли бы привести к упаковке, однако JIT достаточно умен, чтобы исключить эту проверку для значимых типов. Все просто и понятно. Правильно? Почти.

В нашем случае memory traffic генерировался не всех вариантов ValueTuple, а только для определенного: HashSet <ValueTuple <int, MyEnum>>. ОК. Стало понятнее. Правда?

Посмотрим, что произойдет, когда метод Equals вызывается для сравнения двух экземпляров типа ValueTuple <int, MyEnm >:

// Compiler's view of the world
public bool Equals(ValueTuple<int, MyEnum> rhs)
{
    return Item1.Equals(rhs.Item1) && Item2.Equals(rhs.Item2);
}

Для Item1 у нас будет вызов int.Equals (int), а для Item2 — вызов метода MyEnum.Equals (MyEnum). В первом случае ничего особенного не произойдет, но во втором случае вызов метода приведет к упаковке!

«Когда» и «Почему» происходит упаковка?

Обычно мы считаем, что упаковка происходит тогда, когда экземпляр значимого типа явно или неявно преобразуется в ссылочный тип:

int n = 42;
object o = n; // Boxing
IComparable c = n; // Boxing

Но реальность немного сложнее. JIT и CLR вынуждены упаковывать экземпляр значимого типа и в других случаях: например, при вызове методов, определенных в классе ValueType.
Все пользовательские структуры неявно запечатаны (sealed) и унаследованы от специального класса: System.ValueType. Все значимые типы имеют «семантику значений» и поведение, реализованное в System.Object, основанное на сравнении ссылок к ним не подходит. Для обеспечения семантики значений System.ValueType предоставляет специальную реализацию для двух методов: GetHashCode и Equals.

Но реализация по умолчанию имеет две проблемы:

1. Производительность очень плохая (**), потому что она может использовать рефлексию;
2. Упаковка во время вызова одного из этих методов.

(**) Производительность реализации ValueType.Equals и ValueType.GetHashCode по умолчанию может существенно различаться в зависимости от формата конкретного значимого типа. Если структура не содержит указателей и «упакована» правильно, возможно побитовое сравнение. В противном случае будет использоваться рефлексия, использование которой приведет к резкому снижению производительности. См. Реализацию CanCompareBits в реестре coreclr.

Первая описанная выше проблема многим хорошо известна, но вторая более тонкая: если структура не переопределяет метод Equals или GetHashCode, то при вызове одного из этих методов произойдет упаковка.

struct MyStruct
{
    public int N { get; }

    // Если пользователь не переопределит эти методы,
    // тогда будет использована версия, определенная в System.ValueType.

    public override int GetHashCode() => N.GetHashCode();

    public override bool Equals(object obj)
    {
        return obj is MyStruct && Equals((MyStruct)obj);
    }

    public bool Equals(MyStruct other) => N == other.N;
}

var myStruct = new MyStruct();

// Нет упаковки: MyStruct переопределяет GetHashCode
var hc = myStruct.GetHashCode();

// Нет упаковки: MyStruct переопределяет Equals
var equality = myStruct.Equals(myStruct);

// Упаковка: MyStruct не переопределяет ToString
var s = myStruct.ToString();

// Упаковка: GetType не виртуален
var t = myStruct.GetType();

В приведенном выше примере, упаковка не будет происходить в первых двух случаях, но произойдет в последних двух. Вызов метода, определенного в System.ValueType (например, ToString и GetType) приведет к упаковке, а вызов переопределенных методов (например, Equals и GetHashCode) не будет приводить к упаковке.

Теперь вернемся к нашему примеру с ValueTuple <int, MyEnum>. Пользовательские перечисления представляют собой значимые типы без возможности переопределять методы GetHashCode и Equals, а это означает, что каждый вызов MyEnum.GetHashCode или MyEnum.Equals приведет к упаковке и аллокации памяти.
Можем ли мы избежать этого? Да, используя EqualityComparer.Default.

Как EqualityComparer избегает упаковки и выделения памяти?

Давайте немного упростим пример и сравним два способа сравнения значений перечисления: используя метод Equals и используя EqualityComparer .Default:

MyEnum e1 = MyEnum.Foo;
MyEnum e2 = MyEnum.Bar;

// Упаковка
bool b1 = e1.Equals(e2);

// Нет упаковки
bool b2 = EqualityComparer<MyEnum>.Default.Equals(e1, e2);

Давайте используем BenchmarkDotNet, чтобы доказать, что первый случай вызывает выделение памяти, а другой — нет (чтобы избежать выделение итератора, я использую простой цикл foreach, а не что-то вроде Enumerable.Any или Enumerable.Contains):

[MemoryDiagnoser]
public class EnumComparisonBenchmark
{
    public MyEnum[] values = Enumerable.Range(1, 1_000_000).Select(n => MyEnum.Foo).ToArray();
    public EnumComparisonBenchmark()
    {
        values[values.Length - 1] = MyEnum.Bar;
    }

    [Benchmark]
    public bool UsingEquals()
    {
        foreach(var n in values)
        {
            if (n.Equals(MyEnum.Bar)) return true;
        }
        return false;
    }

    [Benchmark]
    public bool UsingEqualityComparer()
    {
        foreach (var n in values)
        {
            if (EqualityComparer<MyEnum>.Default.Equals(n, MyEnum.Bar)) return true;
        }
        return false;
    }
}

Method	Mean	Gen 0	Allocated
UsingEquals	13.300 ms	15195.9459	48000597 B
UsingEqualityComparer	4.659 ms	—	58 B

Как мы видим, вызов метода Equals вызывает множество аллокаций памяти. EqualityComparer работает быстрее, хотя в моем случае я не увидел никакой разницы после того, как я заменил реализацию на EqualityComparer. Главный вопрос: как это делает EqualityComparer?

EqualityComparer — это абстрактный класс, который предоставляет наиболее подходящий компаратор, основанный на заданном аргументе типа, через свойство EqualityComparer .Default. Основная логика находится в методе ComparerHelpers.CreateDefaultEqualityComparer, а в случае перечислений, он передает его другому вспомогательному методу — TryCreateEnumEqualityComparer. Последний метод затем проверяет базовый тип перечисления и создает специальный объект сравнения, который делает некоторые неприятные трюки:

[Serializable]
internal class EnumEqualityComparer<T> : EqualityComparer<T> where T : struct
{
    [Pure]
    public override bool Equals(T x, T y)
    {
        int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(x);
        int y_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(y);
        return x_final == y_final;
    }

    [Pure]
    public override int GetHashCode(T obj)
    {
        int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj);
        return x_final.GetHashCode();
    }

EnumEqualityComparer преобразует экземпляр enum в его базовое числовое значение, используя JitHelpers.UnsafeEnumCast со следующим сравнением двух чисел.

Итак, каково окончательное решение?

Исправление было очень простым: вместо сравнения значений с использованием Item1.Equals мы переключились на EqualityComparer .Default.Equals (Item1, other.Item1).