{"id":535,"date":"2017-05-17T01:18:46","date_gmt":"2017-05-16T17:18:46","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/seteplia\/?p=535"},"modified":"2019-06-11T22:39:22","modified_gmt":"2019-06-12T05:39:22","slug":"box-or-not-to-box-that-is-the-question","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/premier-developer\/box-or-not-to-box-that-is-the-question\/","title":{"rendered":"To box or not to Box? That is the question!"},"content":{"rendered":"

Discussions on reddit<\/a>, hacker news<\/a>. <\/span><\/span><\/span><\/p>\n

Recently I’ve noticed that the Equal <\/b>method from our ValueTuple <\/b>(*) <\/b>struct generates significant memory traffic (~1Gb). That was a bit of a surprise to me. This struct is well designed and was used pretty heavily in many performance critical scenarios. Here how the struct looks like:<\/span><\/span><\/span><\/p>\n

public struct ValueTuple<TItem1, TItem2> : IEquatable<ValueTuple<TItem1, TItem2>>\r\n{\r\n    public TItem1 Item1 { get; }\r\n    public TItem2 Item2 { get; }\r\n\r\n    public ValueTuple(TItem1 item1, TItem2 item2)\r\n        : this()\r\n    {\r\n        Item1 = item1;\r\n        Item2 = item2;\r\n    }\r\n\r\n    public override int GetHashCode()\r\n    {\r\n        \/\/ Real implementation is a bit more complicated. Not a simple XOR\r\n        return EqualityComparer<TItem1>.Default.GetHashCode(Item1) ^\r\n            EqualityComparer<TItem2>.Default.GetHashCode(Item2);\r\n    }\r\n\r\n    public bool Equals(ValueTuple<TItem1, TItem2> other)\r\n    {\r\n        return (Item1 != null && Item1.Equals(other.Item1)) &&\r\n                (Item2 != null && Item2.Equals(other.Item2));\r\n    }\r\n\r\n    public override bool Equals(object obj)\r\n    {\r\n        return obj is ValueTuple<TItem1, TItem2> &&\r\n            Equals((ValueTuple<TItem1, TItem2>)obj);\r\n    }\r\n    \/\/ Other members, like equality operators are omitted for brevity\r\n}<\/pre>\n
(*) Our ValueTuple was implemented way before the one that was shipped with VS 2017, and our implementation is immutable. So even today we can’t switch to the implementation from the .NET Framework.<\/span><\/span><\/span><\/p>\n
Nothing special. Methods Equals <\/b>and GetHashCode <\/b>are overriden to avoid boxing allocation (more on this later in the post). Null check to avoid NullReferenceExcecption<\/b> if Item1 <\/b>or Item2 <\/b>are reference types. Null check potentially could have caused a boxing allocation if the JIT would have leave a check for null if Item1<\/b> or Item2<\/b> are structs. But luckily it is smart enough to eliminate the check in this case. Everything is simple and straightforward. Right? Almost.<\/span><\/span><\/span><\/p>\n
In our case the memory traffic was generated not for every ValueTuple <\/b>case, but only for a specific one: HashSet<ValueTuple<int, MyEnum>><\/b>. Ok. This helps a bit. Right?<\/span><\/span><\/span><\/p>\n
Let’s see what will happen when the Equals <\/b>method is called to compare two instances of ValueTuple<int, MyEnm>><\/b> type:<\/span><\/span><\/span><\/p>\n
\/\/ Compiler's view of the world\r\npublic bool Equals(ValueTuple<int, MyEnum> rhs)\r\n{\r\n    return Item1.Equals(rhs.Item1) && Item2.Equals(rhs.Item2);\r\n}<\/pre>\n
For the Item1<\/b> we’d have a call to int.Equals(int)<\/b>, and for Item2 <\/b>we’d have a call to MyEnum.Equals(MyEnum)<\/b> method. For the first case nothing special will happen, but for the second case the method call will cause a boxing allocation!<\/span><\/span><\/span><\/p>\n
“When” and “Why” boxing happens?<\/span><\/span><\/span><\/h2>\n
We used to think that boxing happens only when an instance of a value type is explicitly or implicitly converts to an object or to an interface:<\/span><\/span><\/span><\/p>\n
int n = 42;\r\nobject o = n; \/\/ Boxing\r\nIComparable c = n; \/\/ Boxing<\/pre>\n
But the reality is slightly more complicated. The JIT and the CLR will have to box an instance in some other cases: for instance, to invoke a method defined in “reference type” section of a value type.<\/span><\/span><\/span><\/p>\n
All custom structs are implicitly sealed and derived from the special class: System.ValueType<\/b>. All value types have “value semantic” meaning that the object\u2019s default referential equality is no longer suitable for them. To enforce the new semantic System.ValueType<\/b> provides a special implementation for two methods: GetHashCode<\/b> and <\/span>Equals.<\/span><\/b><\/span><\/span><\/span><\/p>\n
But default implementation has two problems: the performance is very bad (**) because it may use reflection and boxing will happen for every method invocation.<\/span><\/span><\/span><\/p>\n
(**) The performance of the default implementation of ValueType.Equals <\/b>and ValueType.GetHashCode <\/b>can vary significantly based on the structure of a given value type. If the struct doesn’t have pointers and is “packed” correctly, then bit-wise comparison is possible. Otherwise, reflection will be used that will cause a drastic performance degradation. See <\/span><\/span><\/span>CanCompareBits<\/u><\/span><\/span><\/a><\/span> implementation at the coreclr repo.<\/span><\/span><\/span><\/p>\n
The first issue is pretty well-known but the other one is more subtle: if the <\/span><\/span><\/span>struct does not override a method, boxing will happen!<\/span><\/span><\/span><\/p>\n
struct MyStruct\r\n{\r\n    public int N { get; }\r\n \r\n    public override int GetHashCode() => N.GetHashCode();\r\n \r\n    public override bool Equals(object obj)\r\n    {\r\n        return obj is MyStruct && Equals((MyStruct)obj);\r\n    }\r\n \r\n    public bool Equals(MyStruct other) => N == other.N;\r\n}\r\n \r\n\r\nvar myStruct = new MyStruct();\r\n \r\n\/\/ no boxing: MyStruct overrides GetHashCode\r\nvar hc = myStruct.GetHashCode();\r\n \r\n\/\/ no boxing: MyStruct overrides Equals\r\nvar equality = myStruct.Equals(myStruct);\r\n \r\n\/\/ boxing: MyStruct does not override ToString\r\nvar s = myStruct.ToString();\r\n \r\n\/\/ boxing: GetType is not virtual\r\nvar t = myStruct.GetType();<\/pre>\n
In the example above, the boxing will not happen in the first 2 cases, but will happen in the last two. Call to a method, defined in System.ValueType<\/b> (like ToString<\/b>, and GetType<\/b> in this case) will cause boxing and call to an overridden method (like Equals<\/b> and GetHashCode)<\/b> \u2013 will not.<\/span><\/span><\/span><\/p>\n
Now let\u2019s switch back to our example with ValueTuple<int, MyEnum><\/b>. User-defined enums are value types without an ability to override GetHashCode<\/b> and Equals<\/b>, and this means that every call to MyEnum.GetHashCode<\/b> or MyEnum.Equals<\/b> will cause an allocation.<\/span><\/span><\/span><\/p>\n
But can we avoid it? Yes, by using <\/span><\/span><\/span>EqualityComparer<T>.Default<\/u><\/span><\/span><\/a><\/span> instance.<\/span><\/span><\/span><\/p>\n
How EqualityComparer avoids allocations?<\/span><\/span><\/span><\/h2>\n
Let\u2019s get slightly simplified example and compare two ways of comparing enum values (pun intended): using Equals<\/b> method and using EqualityComparer<T>.Default<\/b>:<\/span><\/span><\/span><\/p>\n
var s1 = new ValueTuple<int, MyEnum>(42, MyEnum.Foo);\r\nvar s2 = new ValueTuple<int, MyEnum>(42, MyEnum.Bar);\r\n \r\n\/\/ Will cause a boxing allocation\r\nbool r = s1.Equals(s2);<\/pre>\n
Let\u2019s use <\/span><\/span><\/span>BenchmarkDotNet<\/u><\/span><\/span><\/a><\/span> to prove that the first case causes an allocation and the other one does not (to avoid iterator allocation I\u2019m using a simple foreach<\/b> loop and not something like Enumerable.Any<\/b> or Enumerable.Contains<\/b>): <\/span><\/span><\/span><\/p>\n
[MemoryDiagnoser]\r\npublic class EnumComparisonBenchmark\r\n{\r\n    public MyEnum[] values = \r\n            Enumerable.Range(1, 1_000_000)\r\n              .Select(n => MyEnum.Foo).ToArray();\r\n \r\n    public EnumComparisonBenchmark()\r\n    {\r\n        values[values.Length - 1] = MyEnum.Bar;\r\n    }\r\n \r\n    [Benchmark]\r\n    public bool UsingEquals()\r\n    {\r\n        foreach(var n in values)\r\n        {\r\n            if (n.Equals(MyEnum.Bar)) return true;\r\n        }\r\n        return false;\r\n    }\r\n \r\n    [Benchmark]\r\n    public bool UsingEqualityComparer()\r\n    {\r\n            var comparer = EqualityComparer<MyEnum>.Default;\r\n        foreach (var n in values)\r\n        {\r\n            if (comparer.Equals(n, MyEnum.Bar)) return true;\r\n        }\r\n        return false;\r\n    }\r\n}<\/pre>\n
                Method |      Mean |      Gen 0 |  Allocated |\r\n---------------------- |----------:|-----------:|-----------:|\r\n           UsingEquals | 13.300 ms | 15195.9459 | 48000597 B |\r\n UsingEqualityComparer |  4.659 ms |          - |       58 B |<\/pre>\n
As we can see, the regular Equals<\/b> call causes a lot of allocations for no reason. Moreover, EqualityComparer<\/b> is way faster, although in my case I haven\u2019t seen any difference after I\u2019ve switched the implementation to use EqualityComparer<\/b>. The main question is: how does EqualityComparer<\/b> do this?<\/span><\/span><\/span><\/p>\n
EqualityComparer<\/span><\/span><\/b> is an abstract class that provides the most suitable comparer based on a given type argument via EqualityComparer<T>.Default<\/b> property. Main logic resides in method <\/span><\/span><\/span><\/span>ComparerHelpers.CreateDefaultEqualityComparer<\/u><\/span><\/span><\/b><\/a> and in case of enums it delegates it to another helper method \u2013 <\/span><\/span>TryCreateEnumEqualityComparer<\/u><\/span><\/span><\/b><\/a><\/span>. The last method then checks the underlying type of the enum and creates special comparer instance that does some nasty tricks:<\/span><\/span><\/span><\/p>\n
[Serializable]\r\ninternal class EnumEqualityComparer<T> \r\n    : EqualityComparer<T> where T : struct\r\n{\r\n    [Pure]\r\n    public override bool Equals(T x, T y)\r\n    {\r\n        int x_final = System.Runtime.CompilerServices\r\n           .JitHelpers.UnsafeEnumCast(x);\r\n        int y_final = System.Runtime.CompilerServices\r\n           .JitHelpers.UnsafeEnumCast(y);\r\n        return x_final == y_final;\r\n    }\r\n \r\n    [Pure]\r\n    public override int GetHashCode(T obj)\r\n    {\r\n        int x_final = System.Runtime.CompilerServices\r\n           .JitHelpers.UnsafeEnumCast(obj);\r\n        return x_final.GetHashCode();\r\n    }\r\n}<\/pre>\n
EnumEqualityComparer<\/span><\/u><\/span><\/span><\/a> converts a nenum instance to its underlying numeric value using JitHelpers.UnsafeEnumCast<\/b> with a following comparison of two numbers.<\/span><\/span><\/span><\/p>\n
So, what was the final fix?<\/span><\/span><\/span><\/h2>\n
The fix was very simple: instead of comparing values using Item1.Equals<\/b> we\u2019ve switched to EqualityComparer<T>.Default.Equals(Item1, other.Item1)<\/b>.<\/span><\/span><\/span><\/p>\n
Additional References<\/span><\/span><\/h2>\n
\u00b7<\/span><\/span>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span><\/span><\/span>Remove usage of EqualityComparer from ValueTuple’s GetHashCode.<\/a><\/p>\n
\u00b7<\/span><\/span>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span><\/span><\/span>GetHashCode should not box enums in generic methods.<\/a><\/u><\/p>\n
\u00b7<\/span><\/span>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/span><\/span><\/span><\/span>Optimize calls to enum\u2019s GetHashCode\/Equals.<\/a><\/u><\/p>\n","protected":false},"excerpt":{"rendered":"
Discussions on reddit, hacker news. Recently I’ve noticed that the Equal method from our ValueTuple (*) struct generates significant memory traffic (~1Gb). That was a bit of a surprise to me. This struct is well designed and was used pretty heavily in many performance critical scenarios. Here how the struct looks like: public struct ValueTuple<TItem1, […]<\/p>\n","protected":false},"author":4004,"featured_media":37840,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[6700],"tags":[6701,6695],"class_list":["post-535","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-net-internals","tag-code-review","tag-seteplia"],"acf":[],"blog_post_summary":"
Discussions on reddit, hacker news. Recently I’ve noticed that the Equal method from our ValueTuple (*) struct generates significant memory traffic (~1Gb). That was a bit of a surprise to me. This struct is well designed and was used pretty heavily in many performance critical scenarios. Here how the struct looks like: public struct ValueTuple<TItem1, […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts\/535","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/users\/4004"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/comments?post=535"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts\/535\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/media\/37840"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/media?parent=535"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/categories?post=535"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/tags?post=535"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}