{"id":1275,"date":"2018-07-17T12:19:42","date_gmt":"2018-07-17T04:19:42","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/seteplia\/?p=1275"},"modified":"2019-06-11T21:39:27","modified_gmt":"2019-06-12T04:39:27","slug":"performance-implications-of-default-struct-equality-in-c","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/premier-developer\/performance-implications-of-default-struct-equality-in-c\/","title":{"rendered":"Performance implications of default struct equality in C#"},"content":{"rendered":"

If you’re familiar with C#, then you most likely heard that you should always override Equals<\/code> and GetHashCode<\/code> for custom structs for performance reasons. To better understand the importance and the rationale behind this advice we’re going to look at the default behavior to see why and where the performance hit comes from. Then we’ll look at a performance bug that occurred in my project and at the end we’ll discuss some tools that can help to avoid the issue altogether.<\/p>\n

How important the issue is?<\/h4>\n

Not every potential<\/strong> performance issue affects an end-to-end time of your application. Enum.HasFlag<\/code> is not very efficient (*), but unless it is used on a very hot path, it would not cause a severe issue for your product. The same is true for defensive copies<\/a> caused by non-readonly structs in the readonly contexts. The issues are real but they’re unlikely to be visible in regular applications.<\/p>\n

(*) The implementation was fixed in .NET Core 2.1 and as I’ve mentioned in the previous post<\/a>, now you can mitigate the issue with a custom HasFlag<\/code> implementation for the older runtimes.<\/p>\n

But the issue we’re talking about today is different. If a struct does not provide Equals<\/code>and GetHashCode<\/code>, then the default versions of these methods from System.ValueType<\/code> are used. The versions that could easily affect an application’s end-to-end performance in a very significant way.<\/p>\n

Why the default implementations are so slow?<\/h4>\n

The CLR authors tried their best to make the default implementations of Equals<\/code> and GetHashCode<\/code> for value types as efficient as possible. But there are a couple of reasons why they won’t be as efficient as a custom version written by hand (or generated by a compiler) for a specific type.<\/p>\n

    \n
  1. Boxing allocation. The way the CLR is designed, every call to a member defined in System.ValueType<\/code> or System.Enum<\/code> types cause a boxing allocation (**).<\/li>\n<\/ol>\n

    (**) Unless the method is a JIT intrinsic. For instance, in Core CLR 2.1 the JIT compiler knows about Enum.HasFlag<\/code> and emits a very optimal code that causes no boxing allocations.<\/p>\n

      \n
    1. Potential collisions of the default GetHashCode<\/code> implementation. An implementer of a hash function faces a dilemma: make a good distribution of the hash function or to make it fast. In some cases, it’s possible to achieve them both, but it is hard to do this generically in ValueType.GetHashCode<\/code>.<\/li>\n<\/ol>\n

      The canonical hash function of a struct “combines” hash codes of all the fields. But the only way to get a hash code of a field in a ValueType<\/code> method is to use reflection. So, the CLR authors decided to trade speed over the distribution and the default GetHashCode<\/code> version just returns a hash code of a first non-null field and “munges” it with a type id<\/a> (***) (for more details see RegularGetValueTypeHashCode<\/code><\/a> in coreclr repo at github).<\/p>\n

      (***) Based on the comment in the CoreCLR repo, this behavior may change in the future.<\/p>\n

      public readonly struct Location\r\n{\r\n    public string Path { get; }\r\n    public int Position { get; }\r\n    public Location(string path, int position) => (Path, Position) = (path, position);\r\n}\r\n\r\n\r\nvar hash1 = new Location(path: \"\", position: 42).GetHashCode();\r\nvar hash2 = new Location(path: \"\", position: 1).GetHashCode();\r\nvar hash3 = new Location(path: \"1\", position: 42).GetHashCode();\r\n\/\/ hash1 and hash2 are the same and hash1 is different from hash3<\/pre>\n
      This is a reasonable behavior unless it’s not. For instance, if you’re unlucky enough and the first field of your struct has the same value for most instances, then a hash function will provide the same result all the time. And, as you may imagine, this will cause a drastic performance impact if these instances are stored in a hash set or a hash table.<\/p>\n
        \n
      1. Reflection-based implementation is slow. Very slow. Reflection is a powerful tool when used correctly. But it is horrible if it’s used on an application’s hot path.<\/li>\n<\/ol>\n
        Let’s see how a poor hash function that you can get because of (2) and the reflection-based implementation affects the performance:<\/p>\n
        public readonly struct Location1\r\n{\r\n    public string Path { get; }\r\n    public int Position { get; }\r\n    public Location1(string path, int position) => (Path, Position) = (path, position);\r\n}\r\n\r\npublic readonly struct Location2\r\n{\r\n    \/\/ The order matters!\r\n    \/\/ The default GetHashCode version will get a hashcode of the first field\r\n    public int Position { get; }\r\n    public string Path { get; }\r\n    public Location2(string path, int position) => (Path, Position) = (path, position);\r\n}\r\n\r\npublic readonly struct Location3 : IEquatable<Location3>\r\n{\r\n    public string Path { get; }\r\n    public int Position { get; }\r\n    public Location3(string path, int position) => (Path, Position) = (path, position);\r\n\r\n    public override int GetHashCode() => (Path, Position).GetHashCode();\r\n    public override bool Equals(object other) => other is Location3 l && Equals(l);\r\n    public bool Equals(Location3 other) => Path == other.Path && Position == other.Position;\r\n}\r\n\r\n\r\nprivate HashSet<Location1> _locations1;\r\nprivate HashSet<Location2> _locations2;\r\nprivate HashSet<Location3> _locations3;\r\n\r\n\r\n[Params(1, 10, 1000)]\r\npublic int NumberOfElements { get; set; }\r\n\r\n[GlobalSetup]\r\npublic void Init()\r\n{\r\n    _locations1 = new HashSet<Location1>(Enumerable.Range(1, NumberOfElements).Select(n => new Location1(\"\", n)));\r\n    _locations2 = new HashSet<Location2>(Enumerable.Range(1, NumberOfElements).Select(n => new Location2(\"\", n)));\r\n    _locations3 = new HashSet<Location3>(Enumerable.Range(1, NumberOfElements).Select(n => new Location3(\"\", n)));\r\n    _locations4 = new HashSet<Location4>(Enumerable.Range(1, NumberOfElements).Select(n => new Location4(\"\", n)));\r\n}\r\n\r\n[Benchmark]\r\npublic bool Path_Position_DefaultEquality()\r\n{\r\n    var first = new Location1(\"\", 0);\r\n    return _locations1.Contains(first);\r\n}\r\n\r\n[Benchmark]\r\npublic bool Position_Path_DefaultEquality()\r\n{\r\n    var first = new Location2(\"\", 0);\r\n    return _locations2.Contains(first);\r\n}\r\n\r\n[Benchmark]\r\npublic bool Path_Position_OverridenEquality()\r\n{\r\n    var first = new Location3(\"\", 0);\r\n    return _locations3.Contains(first);\r\n}<\/pre>\n
        Method | NumOfElements | Mean | Gen 0 | Allocated | \r\n-------------------------------- |-------------- |--------------:|--------:|----------:| \r\nPath_Position_DefaultEquality | 1 | 885.63 ns | 0.0286 | 92 B | \r\nPosition_Path_DefaultEquality | 1 | 127.80 ns | 0.0050 | 16 B | \r\nPath_Position_OverridenEquality | 1 | 47.99 ns | - | 0 B | \r\nPath_Position_DefaultEquality | 10 | 6,214.02 ns | 0.2441 | 776 B | \r\nPosition_Path_DefaultEquality | 10 | 130.04 ns | 0.0050 | 16 B | \r\nPath_Position_OverridenEquality | 10 | 47.67 ns | - | 0 B | \r\nPath_Position_DefaultEquality | 1000 | 589,014.52 ns | 23.4375 | 76025 B | \r\nPosition_Path_DefaultEquality | 1000 | 133.74 ns | 0.0050 | 16 B | \r\nPath_Position_OverridenEquality | 1000 | 48.51 ns | - | 0 B |<\/pre>\n
        If the first field is always the same, the default hash function returns the same value for all the elements. This effectively transforms a hash set into a linked list with O(N) for insertion and lookup operations. And the operation that populates the collection becomes O(N^2) (N insertions with O(N) complexity per insertion). It means that the insertion of 1000 elements into a set will cause almost 500_000 calls to ValueType.Equals<\/code>. A method, that uses reflection under the hood!<\/p>\n
        And as you can see from the benchmark, the performance may be tolerable if you’re lucky and the first element of the struct is unique (Position_Path_DefaultEquality<\/code>case). But the performance may be horrible if this is not the case.<\/p>\n
        Real-world issue<\/h4>\n
        Now you can guess what kind of issue I’ve faced recently. A couple of weeks ago, I received a bug report that the end-to-end time for an app I’m working on increased from 10 seconds to 60. Luckily the report was very detailed and contained an ETW trace that immediately showed the bottleneck: ValueType.Equals<\/code> was taking 50 seconds.<\/p>\n
        After a very quick look at the code it was clear what was the problem:<\/p>\n
        private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;\r\nreadonly struct ErrorLocation\r\n{\r\n    \/\/ Empty almost all the time\r\n    public string OptionalDescription { get; }\r\n    public string Path { get; }\r\n    public int Position { get; }\r\n}<\/pre>\n
        We used a tuple that contained a custom struct with default equality implementation. And unfortunately, the struct had an optional first field that was almost always equals to string.Equals<\/code>. The performance was OK until the number of elements in the set increased significantly causing a real performance issue, taking minutes to initialize a collection with tens of thousands of items.<\/p>\n
        Is the default implementation of ValueType.Equals\/GetHashCode<\/code> always slow?<\/h4>\n
        Both ValueType.Equals<\/code> and ValueType.GetHashCode<\/code> have a special optimization. If a type does not have “pointers” and is properly packed (I’ll show an example in a minute) then more optimal versions are used: GethashCode<\/code> iterates over an instance and XORs blocks of 4 bytes and Equals<\/code> method compares two instances using memcmp<\/code>.<\/p>\n
        \/\/ Optimized ValueType.GetHashCode implementation\r\nstatic INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef)\r\n{\r\n    INT32 hashCode = 0;\r\n    INT32 *pObj = (INT32*)pObjRef;\r\n\r\n   \/\/ this is a struct with no refs and no \"strange\" offsets, just go through the obj and xor the bits\r\n   INT32 size = mt->GetNumInstanceFieldBytes();\r\n   for (INT32 i = 0; i < (INT32)(size \/ sizeof(INT32)); i++)\r\n       hashCode ^= *pObj++;\r\n\r\nreturn hashCode;\r\n}\r\n\r\n\/\/ Optimized ValueType.Equals implementation\r\nFCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1, Object* obj2)\r\n{\r\n    TypeHandle pTh = obj1->GetTypeHandle();\r\n\r\n    FC_RETURN_BOOL(memcmp(obj1->GetData(), obj2->GetData(), pTh.GetSize()) == 0);\r\n}<\/pre>\n
        The check itself is implemented in ValueTypeHelper::CanCompareBits<\/code><\/a> and it is called from both ValueType.Equals<\/code><\/a> and from ValueType.GetHashCode<\/code><\/a>implementations.<\/p>\n
        But the optimization is very tricky.<\/p>\n
        First, it is hard to know when the optimization is enabled and even minor changes in the code can turn it “on” and “off”:<\/p>\n
        public struct Case1\r\n{\r\n    \/\/ Optimization is \"on\", because the struct is properly \"packed\"\r\n    public int X { get; }\r\n    public byte Y { get; }\r\n}\r\n\r\npublic struct Case2\r\n{\r\n    \/\/ Optimization is \"off\", because struct has a padding between byte and int\r\n    public byte Y { get; }\r\n    public int X { get; }\r\n}<\/pre>\n
        For more information about memory layout see my blogpost “Managed object internals, Part 4. Fields layout”<\/a>.<\/p>\n
        Second, a memory comparison will not necessarily give you the right results. Here is a simple example:<\/p>\n
        public struct MyDouble\r\n{\r\n    public double Value { get; }\r\n    public MyDouble(double value) => Value = value;\r\n}\r\n\r\n\r\ndouble d1 = -0.0;\r\ndouble d2 = +0.0;\r\n\r\n\/\/ True\r\nbool b1 = d1.Equals(d2);\r\n\r\n\/\/ False!\r\nbool b2 = new MyDouble(d1).Equals(new MyDouble(d2));<\/pre>\n
        -0.0<\/code> and +0.0<\/code> are equal but have different binary representations. This means that Double.Equals<\/code> returns true<\/code>, but MyDouble.Equals<\/code> returns false<\/code>. For most cases the difference is non-substantial, but just imagine how many hours you may potentially spend trying to fix an issue caused by this difference.<\/p>\n
        And how can we avoid the issue in the future?<\/h4>\n
        You may wonder, how the issue mentioned above may appear in the real world? One obvious way to enforce Equals<\/code> and GetHashCode<\/code> for structs is to use FxCop rule CA1815<\/a>. But there is an issue with this approach: it is a bit too strict.<\/p>\n
        A performance critical application may have hundreds of structs that are not necessarily designed to be used in hash sets or dictionaries. This may cause app developers to suppress the rule that can backfire ones a struct use cases changes.<\/p>\n
        A more appropriate approach is to warn a developer when “inappropriate” struct with default equality members (defined in the app or in a third-party library) is stored in a hash set. Of course, I’m talking about ErrorProne.NET<\/a> and the rule that I’ve added there ones I’ve faced this issue:<\/p>\n
        \"image\"<\/a><\/p>\n
        The ErrorProne.NET<\/a> version is not perfect and will “blame” a valid code if a custom equality comparer is provided in a constructor:<\/p>\n
        \"image\"<\/a><\/p>\n
        But I think it still valid to warn when a struct with default equality members is used by not when it is produced. For instance, when I tested my rule I’ve realized that System.Collections.Generic.KeyValuePair<TKey, TValue><\/code> defined in mscorlib, does not override Equals<\/code> and GetHashCode<\/code>. Today it is unlikely that someone will define a variable of type HashSet<KeyValuePair<string, int>><\/code> but my point is that even BCL can violate the rule and it is useful to catch it until its not too late.<\/p>\n
        Conclusion<\/h3>\n