To box or not to box? That is the question

Found an interesting blog about .NET (C #), which I really liked. I will try from time to time to translate the most interesting articles for you and we will discuss together. Thanks to the author for the wonderful material .

I recently noticed that the Equals method from our ValueTuple (*) structure generates significant memory traffic (~ 1 GB).

This was a surprise to me, since this structure is used in performance-critical scenarios. Here's what she looks like:

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); } //  ,    ,    } 

(*) Our ValueTuple was implemented before it appeared in Visual Studio in 2017, and our implementation is immutable.
')
The Equals and GetHashCode methods are overridden to avoid boxing. Checking for null is needed to avoid NullReferenceException if Item1 or Item2 are objects of reference types. Checks on null might lead to packaging, but JIT is smart enough to exclude this check for meaningful types. Everything is simple and clear. Right? Nearly.

In our case, memory traffic did not generate all the ValueTuple options, but only for a specific one: HashSet <ValueTuple <int, MyEnum >>. OK. It became clearer. True?

Let's see what happens when the Equals method is called to compare two instances of type 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); } 

For Item1 we will have a call int.Equals (int), and for Item2 we will call a method MyEnum.Equals (MyEnum). In the first case, nothing special will happen, but in the second case, calling the method will lead to packaging!

“When” and “Why” packaging occurs?

Typically, we assume that packaging occurs when an instance of a significant type is explicitly or implicitly converted to a reference type:

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

But the reality is a bit more complicated. JIT and CLR are forced to pack an instance of a significant type in other cases: for example, when calling methods defined in the ValueType class.
All user structures are implicitly sealed (sealed) and inherited from a special class: System.ValueType. All significant types have “semantics of values” and the behavior implemented in System.Object based on comparison of links does not fit them. To provide the semantics of the values, System.ValueType provides a special implementation for two methods: GetHashCode and Equals.

But the default implementation has two problems:

1. Performance is very bad (**) because it can use reflection;
2. Packaging while calling one of these methods.

(**) The performance of the implementation of ValueType.Equals and ValueType.GetHashCode by default may vary significantly depending on the format of a particular significant type. If the structure does not contain pointers and is “packed” correctly, a bitwise comparison is possible. Otherwise, reflection will be used, the use of which will lead to a sharp decrease in performance. See Implementing CanCompareBits in the coreclr registry.

The first problem described above is well known to many, but the second is more subtle: if the structure does not override the Equals method or GetHashCode, then when one of these methods is called, packaging will occur.

 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(); 

In the example above, the packaging will not occur in the first two cases, but will occur in the last two. Calling the method defined in System.ValueType (for example, ToString and GetType) will result in packing, and calling overdefined methods (for example, Equals and GetHashCode) will not result in packing.

Now back to our example with ValueTuple <int, MyEnum>. Custom enums are meaningful types without the ability to override the GetHashCode and Equals methods, which means that every call to MyEnum.GetHashCode or MyEnum.Equals will result in the packing and allocation of memory.
Can we avoid this? Yes, using EqualityComparer.Default.

How does EqualityComparer avoid packing and allocating memory?

Let's simplify the example a bit and compare two ways of comparing enumeration values: using the Equals method and using EqualityComparer .Default:

 MyEnum e1 = MyEnum.Foo; MyEnum e2 = MyEnum.Bar; //  bool b1 = e1.Equals(e2); //   bool b2 = EqualityComparer<MyEnum>.Default.Equals(e1, e2); 

Let's use BenchmarkDotNet to prove that the first case causes memory allocation and the other does not (to avoid iterator allocation, I use a simple foreach loop, and not something like Enumerable.Any or 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

As we see, the call to the Equals method causes a lot of memory allocations. EqualityComparer is faster, although in my case I did not see any difference after I replaced the implementation with EqualityComparer. Main question: how does EqualityComparer do it?

EqualityComparer is an abstract class that provides the most appropriate comparator, based on a given type argument, through the EqualityComparer .Default property. The main logic is in the ComparerHelpers.CreateDefaultEqualityComparer method, and in the case of enumerations, it passes it to another auxiliary method, TryCreateEnumEqualityComparer. The latter method then checks the base type of the enumeration and creates a special comparison object that does some unpleasant tricks:

 [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 converts an enum instance into its base numeric value using JitHelpers.UnsafeEnumCast with the following comparison of two numbers.

So what is the final solution?

The fix was very simple: instead of comparing values ​​using Item1.Equals, we switched to EqualityComparer .Default.Equals (Item1, other.Item1).