Overrides Equals and GetHashCode. Do you need it?

Original author: Sergey Teplyakov
  • Transfer
If you are familiar with C #, you most likely know that you must always redefine Equals, and also GetHashCodeto avoid performance degradation. 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 method is Enum.HasFlagnot very effective (*), but if you do not use it on a resource-intensive piece of code, then 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 methods Equals and GetHashCode, then their standard versions fromSystem.ValueType. And they can significantly reduce the performance of the final application.

Why are standard versions slow?

The CLR authors have struggled 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 specific type manually (or generated by the compiler).

1. Distribution of packaging-transformation. The CLR is designed in such a way that every call to an element defined in types System.ValueTypeor System.Enumstarts a wrapping-transform (**).

(**) If the method does not support JIT compilation. For example, in Core CLR 2.1, the JIT compiler recognizes a method Enum.HasFlagand generates suitable code that does not launch wrapping.

2. Potential conflicts in the standard version of the methodGetHashCode. When implementing a hash function, we are faced with a dilemma: make hash function distribution good or fast. In some cases, you can do both, but in the type ValueType.GetHashCodeit is usually fraught with difficulties.

A traditional hash function of type "struct" combines the hash codes of all fields. But the only way to get the hash code of a field in a method ValueTypeis to use reflection. That is why the CLR authors decided to sacrifice speed for the sake of distribution, and the standard version GetHashCodeonly returns the hash code of the first non-zero field and “spoils” it with a type identifier (***) (for more details, see RegularGetValueTypeHashCodecoreclr repo on github).

(***) Judging by the comments in the CoreCLR repository, the situation may change in the future.

publicreadonlystruct Location
    publicstring Path { get; }
    publicint Position { get; }
    publicLocation(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 matches 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 piece of code.

Let's look at how an unsuccessful hash function, which can result from (2) and a reflection-based implementation, affects performance:

publicreadonlystruct Location1
    publicstring Path { get; }
    publicint Position { get; }
    publicLocation1(string path, int position) => (Path, Position) = (path, position);
publicreadonlystruct Location2
    // The order matters!// The default GetHashCode version will get a hashcode of the first fieldpublicint Position { get; }
    publicstring Path { get; }
    publicLocation2(string path, int position) => (Path, Position) = (path, position);
publicreadonlystruct Location3 : IEquatable<Location3>
    publicstring Path { get; }
    publicint Position { get; }
    publicLocation3(string path, int position) => (Path, Position) = (path, position);
    publicoverrideintGetHashCode() => (Path, Position).GetHashCode();
    publicoverrideboolEquals(object other) => other is Location3 l && Equals(l);
    publicboolEquals(Location3 other) => Path == other.Path && Position == other.Position;
private HashSet<Location1> _locations1;
private HashSet<Location2> _locations2;
private HashSet<Location3> _locations3;
[Params(1, 10, 1000)]
publicint NumberOfElements { get; set; }
    _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)));
    var first = new Location1("", 0);
    return _locations1.Contains(first);
    var first = new Location2("", 0);
    return _locations2.Contains(first);
    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 items into the set will result in almost 500,000 calls 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 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 - it took ValueType.Equals50 seconds to load.

After a quick scan of the code, it became clear what the problem was:

privatereadonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonlystruct ErrorLocation
    // Empty almost all the timepublicstring OptionalDescription { get; }
    publicstring Path { get; }
    publicint Position { get; }

I used a tuple that contained a custom type of struct with the standard version Equals. And, unfortunately, he had an optional first field, which was almost always equal 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 ValueType.Equals/GetHashCodedefault implementation always work slowly?

Both for ValueType.Equalsand for ValueType.GetHashCodethere 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: iterations GetHashCode are performed on the blocks of the instance, XOR is used, 4 bytes in size, the method Equals compares two instances using memcmp.

// Optimized ValueType.GetHashCode implementationstatic 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 both iteration ValueType.Equalsand 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:

publicstruct Case1
    // Optimization is "on", because the struct is properly "packed"publicint X { get; }
    publicbyte Y { get; }
publicstruct Case2
    // Optimization is "off", because struct has a padding between byte and intpublicbyte Y { get; }
    publicint 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:

publicstruct MyDouble
    publicdouble Value { get; }
    publicMyDouble(doublevalue) => Value = value;
double d1 = -0.0;
double d2 = +0.0;
// Truebool b1 = d1.Equals(d2);
// False!bool b2 = new MyDouble(d1).Equals(new MyDouble(d2));

-0,0and +0,0equal, but have different binary representations. This means that it Double.Equalswill be true, and MyDouble.Equals- false. In most cases, the difference is not significant, 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 start the techniques Equals and GetHashCode in the types struct - use rule FxCop CA1815 . 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 have unpleasant consequences if the type of struct 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 aboutErrorProne.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 designer uses a custom equality mapper:

But I still think it is worth warning if the type of struct with equal elements is not used when produced. For example, when I checked my rule, I realized that the structure System.Collections.Generic.KeyValuePair <TKey, TValue>defined in mscorlib does not overwrite Equals and GetHashCode. It is unlikely that today someone will define a type variable 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.


  • 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 GetHashCodewill be very bad if the first field of many instances has the same value.
  • For standard methods, Equals and GetHashCode there are optimized versions, but you should not rely on them, because even a small code change can turn them off.
  • Use the FxCop rule to ensure that each struct type 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

Also popular now: