Override Equals and GetHashCode. Do you need it?
If you are familiar with C #, you most likely know that you must always override
Not every potential performance issue affects the execution time of an application. The
')
(*) Fixed in .NET Core 2.1, and, as I mentioned in a previous post , now the effects can be mitigated using self-configured HasFlag for older versions.
But the problem that we will talk about today is special. If the structure does not create the
The CLR authors tried their best to make the standard versions of Equals and GetHashCode as efficient as possible for value types. But there are several reasons why these methods lose in the effectiveness of a user version written for a particular type manually (or generated by the compiler).
1. Distribution of packaging-transformation. The CLR is designed in such a way that each call to an element defined in the
(**) If the method does not support JIT compilation. For example, in Core CLR 2.1, the JIT compiler recognizes the
2. Potential conflicts in the standard version of the
A traditional hash function of type "struct" combines the hash codes of all fields. But the only way to get the field hash code in the
(***) Judging by the comments in the CoreCLR repository, the situation may change in the future.
This is a reasonable algorithm until something goes wrong. But if you are unlucky and the value of the first field of your struct type is the same in most instances, then the hash function will always produce the same result. As you may have guessed, if you save these instances in a hash set or hash table, then the performance will drop dramatically.
3. The speed of implementation based on reflection is low. Very low. Reflection is a powerful tool if used correctly. But the consequences will be terrible if you run it on a resource-intensive code section.
Let's take a look at how an unsuccessful hash function, which can result from (2) and reflection-based implementation, affects performance:
If the value of the first field is always the same, then by default the hash function returns an equal value for all elements and the hash set is effectively converted into a linked list with O (N) insert and search operations. The number of operations to fill the collection becomes O (N ^ 2) (where N is the number of inserts with complexity O (N) for each insert). This means that inserting 1000 elements into the set will yield almost 500,000 calls to
As the test shows, the performance will be acceptable if you are lucky and the first element of the structure is unique (in the case of
I think now you can guess what problem I recently encountered. A couple of weeks ago, I received an error message: the execution time of the application I am working on increased from 10 to 60 seconds. Fortunately, the report was very detailed and contained a trace of Windows events, so the problem place was discovered quickly -
After a quick scan of the code, it became clear what the problem was:
I used a tuple that contained a custom type of struct with the standard version of
Does the implementation of
Both for
The check itself is performed in
But optimization is a very insidious thing.
Firstly, it is difficult to understand when it is turned on; even minor changes to the code can turn it on and off:
For more information about the structure of memory, see my blog "Internal elements of a managed object, part 4. Structure of fields . "
Secondly, a comparison of memory does not necessarily give you the correct result. Here is a simple example:
You can ask me how the above mentioned can happen in a real situation? One of the obvious ways to run the
An application for which performance is critical can have hundreds of struct types that are not necessarily used in hash sets or dictionaries. Therefore, application developers can disable the rule, which will backfire if the struct type uses modified functions.
A more correct approach is to warn the developer if a “inappropriate” type of struct with equal values ​​of default elements (defined in an application or a third-party library) is stored in a hash set. Of course, I'm talking about ErrorProne.NET and the rule I added there as soon as I ran into this problem:
The ErrorProne.NET version is not perfect and will “blame” the correct code if the constructor uses a custom equality mapper:
But I still think it is worth warning if the type of struct with equal elements by default is not used when produced. For example, when I checked my rule, I realized that the
Equals , as well as GetHashCode , to avoid performance GetHashCode . But what happens if this is not done? Today, let's compare the performance with the two settings and consider the tools to help avoid errors.How serious is this problem?
Not every potential performance issue affects the execution time of an application. The
Enum.HasFlag method Enum.HasFlag not very effective (*), but if you don’t use it on a resource-intensive piece of code, there will be no serious problems in the project. This is also true for protected copies created by non-readonly struct types in a readonly context. The problem exists, but is unlikely to be noticeable in ordinary applications.')
(*) Fixed in .NET Core 2.1, and, as I mentioned in a previous post , now the effects can be mitigated using self-configured HasFlag for older versions.
But the problem that we will talk about today is special. If the structure does not create the
Equals and GetHashCode methods, then their standard versions from System.ValueType . And they can significantly reduce the performance of the final application.Why are standard versions slow?
The CLR authors tried their best to make the standard versions of Equals and GetHashCode as efficient as possible for value types. But there are several reasons why these methods lose in the effectiveness of a user version written for a particular type manually (or generated by the compiler).
1. Distribution of packaging-transformation. The CLR is designed in such a way that each call to an element defined in the
System.ValueType or System.Enum types starts a wrapping (**).(**) If the method does not support JIT compilation. For example, in Core CLR 2.1, the JIT compiler recognizes the
Enum.HasFlag method and generates suitable code that does not start wrapping.2. Potential conflicts in the standard version of the
GetHashCode method. When implementing a hash function, we are faced with a dilemma: do a hash function distribution well or quickly. In some cases, both can be done, but in the ValueType.GetHashCode type this is usually difficult.A traditional hash function of type "struct" combines the hash codes of all fields. But the only way to get the field hash code in the
ValueType method is to use reflection. That is why the CLR authors decided to sacrifice speed for the sake of distribution, and the standard version of GetHashCode only returns the hash code of the first non-zero field and “spoils” it with a type identifier (***) (for more details, see the coreclr repo on the coreclr repo on github).(***) Judging by the comments in the CoreCLR repository, the situation may change in the future.
public readonly struct Location { public string Path { get; } public int Position { get; } public Location(string path, int position) => (Path, Position) = (path, position); } var hash1 = new Location(path: "", position: 42).GetHashCode(); var hash2 = new Location(path: "", position: 1).GetHashCode(); var hash3 = new Location(path: "1", position: 42).GetHashCode(); // hash1 and hash2 are the same and hash1 is different from hash3 This is a reasonable algorithm until something goes wrong. But if you are unlucky and the value of the first field of your struct type is the same in most instances, then the hash function will always produce the same result. As you may have guessed, if you save these instances in a hash set or hash table, then the performance will drop dramatically.
3. The speed of implementation based on reflection is low. Very low. Reflection is a powerful tool if used correctly. But the consequences will be terrible if you run it on a resource-intensive code section.
Let's take a look at how an unsuccessful hash function, which can result from (2) and reflection-based implementation, affects performance:
public readonly struct Location1 { public string Path { get; } public int Position { get; } public Location1(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location2 { // The order matters! // The default GetHashCode version will get a hashcode of the first field public int Position { get; } public string Path { get; } public Location2(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location3 : IEquatable<Location3> { public string Path { get; } public int Position { get; } public Location3(string path, int position) => (Path, Position) = (path, position); public override int GetHashCode() => (Path, Position).GetHashCode(); public override bool Equals(object other) => other is Location3 l && Equals(l); public bool Equals(Location3 other) => Path == other.Path && Position == other.Position; } private HashSet<Location1> _locations1; private HashSet<Location2> _locations2; private HashSet<Location3> _locations3; [Params(1, 10, 1000)] public int NumberOfElements { get; set; } [GlobalSetup] public void Init() { _locations1 = new HashSet<Location1>(Enumerable.Range(1, NumberOfElements).Select(n => new Location1("", n))); _locations2 = new HashSet<Location2>(Enumerable.Range(1, NumberOfElements).Select(n => new Location2("", n))); _locations3 = new HashSet<Location3>(Enumerable.Range(1, NumberOfElements).Select(n => new Location3("", n))); _locations4 = new HashSet<Location4>(Enumerable.Range(1, NumberOfElements).Select(n => new Location4("", n))); } [Benchmark] public bool Path_Position_DefaultEquality() { var first = new Location1("", 0); return _locations1.Contains(first); } [Benchmark] public bool Position_Path_DefaultEquality() { var first = new Location2("", 0); return _locations2.Contains(first); } [Benchmark] public bool Path_Position_OverridenEquality() { var first = new Location3("", 0); return _locations3.Contains(first); } Method | NumOfElements | Mean | Gen 0 | Allocated | -------------------------------- |------ |--------------:|--------:|----------:| Path_Position_DefaultEquality | 1 | 885.63 ns | 0.0286 | 92 B | Position_Path_DefaultEquality | 1 | 127.80 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1 | 47.99 ns | - | 0 B | Path_Position_DefaultEquality | 10 | 6,214.02 ns | 0.2441 | 776 B | Position_Path_DefaultEquality | 10 | 130.04 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 10 | 47.67 ns | - | 0 B | Path_Position_DefaultEquality | 1000 | 589,014.52 ns | 23.4375 | 76025 B | Position_Path_DefaultEquality | 1000 | 133.74 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1000 | 48.51 ns | - | 0 B | If the value of the first field is always the same, then by default the hash function returns an equal value for all elements and the hash set is effectively converted into a linked list with O (N) insert and search operations. The number of operations to fill the collection becomes O (N ^ 2) (where N is the number of inserts with complexity O (N) for each insert). This means that inserting 1000 elements into the set will yield almost 500,000 calls to
ValueType.Equals . Here are the consequences of the method that uses reflection!As the test shows, the performance will be acceptable if you are lucky and the first element of the structure is unique (in the case of
Position_Path_DefaultEquality ). But if this is not the case, then the performance will be extremely low.Real problem
I think now you can guess what problem I recently encountered. A couple of weeks ago, I received an error message: the execution time of the application I am working on increased from 10 to 60 seconds. Fortunately, the report was very detailed and contained a trace of Windows events, so the problem place was discovered quickly -
ValueType.Equals loaded in 50 seconds.After a quick scan of the code, it became clear what the problem was:
private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation { // Empty almost all the time public string OptionalDescription { get; } public string Path { get; } public int Position { get; } } I used a tuple that contained a custom type of struct with the standard version of
Equals . And, unfortunately, it had an optional first field, which almost always was String.equals . Performance remained high until the number of elements in the set increased significantly. Within minutes, a collection with tens of thousands of elements was initialized.Does the implementation of ValueType.Equals/GetHashCode always work slowly by default?
Both for
ValueType.Equals , and for ValueType.GetHashCode there are special optimization methods. If the type does not have “pointers” and it is packaged correctly (I will show an example in a minute), then optimized versions are used: GetHashCode iterations are performed on instance blocks, 4-byte XOR is used, Equals method compares two instances using memcmp . // Optimized ValueType.GetHashCode implementation static INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef) { INT32 hashCode = 0; INT32 *pObj = (INT32*)pObjRef; // this is a struct with no refs and no "strange" offsets, just go through the obj and xor the bits INT32 size = mt->GetNumInstanceFieldBytes(); for (INT32 i = 0; i < (INT32)(size / sizeof(INT32)); i++) hashCode ^= *pObj++; return hashCode; } // Optimized ValueType.Equals implementation FCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1, Object* obj2) { TypeHandle pTh = obj1->GetTypeHandle(); FC_RETURN_BOOL(memcmp(obj1->GetData(), obj2->GetData(), pTh.GetSize()) == 0); } The check itself is performed in
ValueTypeHelper::CanCompareBits , it is called from the iteration ValueType.Equals , and from the iteration ValueType.GetHashCode .But optimization is a very insidious thing.
Firstly, it is difficult to understand when it is turned on; even minor changes to the code can turn it on and off:
public struct Case1 { // Optimization is "on", because the struct is properly "packed" public int X { get; } public byte Y { get; } } public struct Case2 { // Optimization is "off", because struct has a padding between byte and int public byte Y { get; } public int X { get; } } For more information about the structure of memory, see my blog "Internal elements of a managed object, part 4. Structure of fields . "
Secondly, a comparison of memory does not necessarily give you the correct result. Here is a simple example:
public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0; // True bool b1 = d1.Equals(d2); // False! bool b2 = new MyDouble(d1).Equals(new MyDouble(d2)); -0,0 and +0,0 are equal, but have different binary representations. This means that Double.Equals is correct, and MyDouble.Equals is false. In most cases, the difference is insignificant, but imagine how many hours you will spend on correcting the problem caused by this difference.How to avoid a similar problem?
You can ask me how the above mentioned can happen in a real situation? One of the obvious ways to run the
Equals and GetHashCode methods in struct types is to use the FxCop CA1815 rule . But there is one problem: this is too strict an approach.An application for which performance is critical can have hundreds of struct types that are not necessarily used in hash sets or dictionaries. Therefore, application developers can disable the rule, which will backfire if the struct type uses modified functions.
A more correct approach is to warn the developer if a “inappropriate” type of struct with equal values ​​of default elements (defined in an application or a third-party library) is stored in a hash set. Of course, I'm talking about ErrorProne.NET and the rule I added there as soon as I ran into this problem:
The ErrorProne.NET version is not perfect and will “blame” the correct code if the constructor uses a custom equality mapper:
But I still think it is worth warning if the type of struct with equal elements by default is not used when produced. For example, when I checked my rule, I realized that the
System.Collections.Generic.KeyValuePair <TKey, TValue> structure defined in mscorlib does not overwrite Equals and GetHashCode . It is unlikely that today someone will define a variable of type HashSet <KeyValuePair<string, int>> , but I believe that even the BCL can break the rule. Therefore, it is useful to discover this before it is too late.Conclusion
- Implementing the default equality for struct types can have serious consequences for your application. This is a real, not a theoretical problem.
- The default equality elements for value types are based on reflection.
- The distribution performed by the standard version of
GetHashCodewill be very bad if the first field of many instances has the same value. - There are optimized versions for the standard methods
EqualsandGetHashCode, but you shouldn’t rely on them, because even a small code change can turn them off. - Use the FxCop rule to ensure that each type of struct overrides the elements of equality. However, it is better to prevent the problem with the analyzer if the “inappropriate” structure is stored in a hash set or in a hash table.
Additional resources
Source: https://habr.com/ru/post/418515/
All Articles