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).

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 12

      0

      Меня по сих пор удивляет, почему enum в C# не реализовывает IEquatable<T>.
      EqualityComparer в данном случае является лишь полумерой, т.к. стоимость одного сравнения остаётся довольно высокой — вызов виртуальной функции.

        +1
        Я подозреваю, что сложность в предложенном подходе заключается в том, что JIT-у пришлось бы много работать, чтобы это сделать. Например, реализация IList массивом является достаточно нетривиальной штукой.
          0
          А с какой стати JIT тут будет напрягаться, если enum — это просто int?

          Microsoft ещё с 2008 года упорно отвечает на предложения по добавлению IEquatable и IComparable к enum в стиле «спасибо, хорошая идея, но у нас нет планов по её добавлению в ближайший релиз C#».

          Мне кажется, что при переходе на .NET 2.0 про enum-ы просто забыли, а теперь не хотят добавлять этот функционал из-за обратной совместимости.
        +2

        Вообще-то, для переводов есть отдельный тип статьи. А у вас даже нет указания на конкретный первоисточник.

          +4
          Спасибо за замечания. Указания на первоисточник есть в начале статьи. Тип статьи я вначале не смог найти (ее действительно трудно заметить). Написал в поддержку, показали где выбирается.
          +3
          Enum — это не просто int. Это кастомный тайп, отнаследованный от System.Enum, который отнаследован от System.ValueType, который содержит примитив внутри. Это может быть int, а может быть short или byte. Именно за счет того, что поля могут быть разного типа mscorlib содержит семейство «сравнителей»: SByteEnumEqualityComparer, и простой EnumEqualityComparer.

          Некоторая работа по оптимизации кишочков идет. Например, новый JIT знает о существовании Enum.HasFlags. Плюс идет работа по девиртуализации вызовов.

          Да, и я не совсем понял, как реализация IEquatable поможет избавиться от виртуального вызова. Можете пояснить этот момент?
            0
            Да, и я не совсем понял, как реализация IEquatable поможет избавиться от виртуального вызова. Можете пояснить этот момент?

            Очень просто: вызов .Equals() для value-типов — невиртуальный, тогда как вызов EqualityComparer.Equals() — виртуальный.

              +1
              Простите, но я не понимаю:).

              1. Наличие IEquatable никак не влияет на то, будет ли вызов Equals/GetHashCode виртуальным или нет.
              2. Вызов метода, определенного в System.ValueType или System.Enum приводит к упаковке:
              int n = 42; var t = n.GetType(); — невиртуальный, но приводит к упаковке.

              Теперь вопрос: как реализация IEquatable поможет избавиться от виртуального вызова и при этом не будет упаковки (котооорая дороже виртуального вызова).
                0
                1. В случае вызова метода .Equals() у объекта JIT-компилятор может решить на месте, нужно ли здесь делать виртуальный вызов или можно применить оптимизацию. Например, когда класс является sealed, и в нём Equals/GetHashCode переопределены, то вызов будет прямым.


                2. Но если метод переопределён в потомке, то упаковки не будет.

                Теперь вопрос: как реализация IEquatable поможет избавиться от виртуального вызова и при этом не будет упаковки (котооорая дороже виртуального вызова).

                Не IEquatable, а IEquatable<T>. Позволит избежать упаковки, т.к. аргументом является не object, а сама структура T. А вызов будет невиртуальным — см. п. 1.

                  0
                  1. Эта возможность есть и сейчас и для этого IEquatable не нужен.
                  2. Потомка не существует. Для этого нужно, чтобы каждый enum был унаследован от System.Enum.

                  Это все я к тому, что для того, чтобы избежать виртуального вызова и упаковке совсем не обязательно, чтобы перечисления реализовывали интерфейс. Для этого необходимо и достаточно, чтобы JIT-компилятор знал о них, аналогично тому, как он сейчас уже знает о Enum.HasFlags.
                    0

                    Напомню, что речь идёт о сравнении generic типов, а не о сравнениях вообще.


                    Это все я к тому, что для того, чтобы избежать виртуального вызова и упаковке совсем не обязательно, чтобы перечисления реализовывали интерфейс

                    Нет. Реализация интерфейса обязательна, если мы хотим делать эффективные сравнения в generic методах. То есть требовать от типа, чтобы он был IEquatable<T>. Но если для примитивных типов этот интерфейс определён, то для перечислений его, упс, нету.


                    Из следующих трёх вариантов:


                    bool Func1<T>(T v1, T v2)  => v1.Equals(v2);   // Будет вызван object.Equals(object other), со всеми его минусами
                    
                    bool Func2<T>(T v1, T v2) => EqualityComparer<T>.Default.Equals(v1, v2);    // Будет вызван эффективный компаратор, но ценой одного виртуального вызова, т.к. EqualityComparer<T>.Default возвращает абстрактный класс с виртуальным Equals
                    
                    bool Func3<T>(T v1, T v2) where T : IEquatable<T> => v1.Equals(v2);    // Будет вызван T.Equals(T other)

                    самым быстрым будет третий, второй — где-то в пару раз медленее третьего (для мелких структур), ну а первый — на порядок медленнее.

            0
            До чего дошел прогресс…
            Перевод на русский английской статьи русскоязычного хабраюзера, который присутствует в комментариях к этому переводу.
            image

            Only users with full accounts can post comments. Log in, please.