Recipe 3.9 Improving the Performance of a Structure's Equals Method

Problem

You need to provide a better performing Equals method than the default Equals method on a structure. The default implementation of Equals on a ValueType uses reflection to compare the fields of two ValueTypes, resulting in poor performance. Note that this recipe does not hold true for classes; although the same techniques apply if you want to overload the Equals method in a class.

Solution

Override the Equals method. When this method is overridden, you must also override the GetHashCode method:

public struct Line
{
    public Line(int startX, int startY, int endX, int endY)
    {
        x1 = startX;
        x2 = endX;
        y1 = startY;
        y2 = endY;
    }

    private int x1;
    private int y1;
    private int x2;
    private int y2;

    public override bool Equals(object obj)
    {
        bool isEqual = false;

        if (obj == null || (this.GetType( ) != obj.GetType( ))) 
        {
            isEqual = false;
        }
        else
        {
            Line theLine = (Line)obj;
            isEqual = (this.x1 == theLine.x1) && 
                      (this.y1 == theLine.y1) && 
                      (this.x2 == theLine.x2) && 
                      (this.y2 == theLine.y2);
        }
        return (isEqual);

    }

    public override int GetHashCode( )
    {
        return (x1+109*(x2+113*(y1+127*y2)));
    }
}

In addition, a strongly typed Equals method can be added to further streamline this operation:

public bool Equals(Line lineObj)
{
    bool isEqual = (this.x1 == lineObj.x1) && 
                   (this.y1 == lineObj.y1) && 
                   (this.x2 == lineObj.x2) && 
                   (this.y2 == lineObj.y2);

    return (IsEqual);
}

In this recipe, we chose a Line structure arbitrarily. However, your focus should be on the details of overriding an Equals method. In addition, we chose to define the equivalence of two Line objects as having the exact same starting and ending coordinates.

Discussion

All structures come with a predefined Equals method that internally uses reflection. Take a look at the IL code for the Equals method of the System.ValueType class in the mscorlib.dll using Ildasm. You will notice that the implementation of this Equals method first checks to see whether the object passed in to this method is null. If it is not, the next check is to determine whether the object implementing the Equals method is the same type as the one passed in to it. If so, a check is made using the internally implemented method ValueType.CanCompareBits. If this method determines that the bits of the two objects can be compared successfully, a call is made to ValueType.FastEqualsCheck. If this faster check for equivalence cannot be made, reflection—which performs slower—is used to obtain all the instance fields of both objects and compare them individually within a loop. This may not be the best way to go for your custom ValueType—from both a performance and a logic point of view.

Performance-wise, the Equals methods provided in this recipe are faster. From a logic point of view, you can create your own equivalence algorithm, and not depend on what the default implementation considers equivalence. For example, your ValueType could contain many different instance fields, but the equivalence of two of these ValueTypes may depend only on a subset of these instance fields. By overriding the Equals method, we can solve both of these problems at one time.

By creating a strongly typed Equals method, we can take performance one step farther. The overridden Equals method must confirm that the object type passed in to it is not only non-null, but that it is also of the same type. If both of these tests pass, an unboxing operation must be performed when the object that is passed is cast to its corresponding ValueType. Note also that a boxing operation must occur when the Equals method is called.

There are several rules that you should follow when determining when to override the Equals method. The Equals method should be overridden when implementing the IComparable interface on your structure/class. If the object passed as a parameter to this method is either null or not of the same type as this object, return a false. Finally, exceptions should not be explicitly thrown in this method, as it might confuse other developers that are trying to debug code using your object. These rules are valid for reference types as well.

Whenever the Equals method is overloaded, you should overload the GetHashCode method. If you fail to do so, the code will compile, but a warning will be issued stating that the GetHashCode method should be overridden.

Overridding the GetHashCode method is desirable for several reasons. Most importantly, overriding this method allows your ValueType to be used as a key in a System.Collection.HashTable object. The second reason is performance. If you take a look at the IL for the ValueType.GetHashCode method in the mscorlib.dll using Ildasm, you will see that it also uses reflection to obtain the first non-null instance field of the ValueType. Once it obtains this field, that field's GetHashCode method is called to return a hash code value. If no valid fields exist in the ValueType, the internal method ValueType.GetMethodTablePtrAsInt is called to get a hash code. The final reason for overloading this method is to control more precisely the algorithm for obtaining a hash code.

As a final note, when overloading the Equals method, you should strongly consider overloading the == and != operators. This overloading will provide consistency within your type. For example, some clients of your type may use the Equals method and some may attempt to use the == or != operators. Providing overrides to all three of these members allows consistent use of your type. The code to overload these two operators for the Line type is as follows:

public static bool operator ==(Line l1, Line l2)
{
    return (l1.Equals(l2));
}

public static bool operator !=(Line l1, Line l2)
{
    return (!l1.Equals(l2));
}

See Also

See the "ValueType.Equals Method" topic in the MSDN documentation .