In C#, when we think of member-wise equality, we often think of value types. Indeed, their default behaviour (in contrast to that of reference types) is to provide both Equals() and GetHashCode() methods based on their composition rather than their location in memory. However, there are times when we want our reference types to be regarded as equal based on composition as well; the most obvious example of this is System.String, which masquerades as a value type in more ways than one. Let’s look at some other examples of reference types that we might want to equate in a member-wise fashion:

• Database objects; where multiple instances of the same record should be regarded as equal.
• An in-memory tuple; whose values are of importance and their provenance not.
• A compound key in a dictionary or table; where it must be possible to create a new, separate instance to match an existing one.

It’s also worthwhile to point out that anonymous types exhibit member-wise equality as well; this makes it possible to do such things in LINQ as performing a group-by on multiple fields.

Needless to say, there are times when we want this behaviour in our reference types. The usual method of implementing this behaviour (unless using an anonymous type, of course) is to override the Equals/GetHashCode methods in a similar manner to this:

public override bool Equals(object obj) {
    if (obj is MyType) {
        MyType that = (MyType)obj;
        return (this.PropertyA == that.PropertyA) && (this.PropertyB == that.PropertyB);
    }
    else {
        return base.Equals(obj);
    }
}

public override int GetHashCode() {
    return PropertyA.GetHashCode() ^ PropertyB.GetHashCode();
}

Note: It’s important to override both methods and be consistent in the logic used to determine equality/identity for the type. Some framework methods will call the full-blown Equals() method, while others will be content to operate on the hash code only. As a developer, you expect to get the same behaviour every time, without having to know how the framework methods are implemented!

As you can see, this is typical boilerplate code; there seems to be no obvious way to avoid having to type this code out every time, since each class will have a different set of properties (or other members) that must be considered for equality… or is there? What if we could write a very clever base class from which to extend any reference types we want to equate in a member-wise fashion? A base class that would somehow know the public properties of whichever subclass was being compared at the time?

I Know What You’re Thinking…

…you’re thinking reflection, aren’t you? Well, true, reflection does allow a base class to discover the properties of its children, and yes, it could pop the values out of each property of each instance and try to equate them… but… and this is the big BUT… this would be a terribly inefficient technique!

public override bool Equals(object obj) {
    // we're not even checking whether 'obj' is of the same type
    foreach (PropertyInfo property in this.GetType().GetProperties()) {
        if (!property.GetValue(this, null).Equals(property.GetValue(obj, null))) return false;
    }

    return true;
}

Even if we cached the complete set of PropertyInfo objects for each subclass (so they would only have to be retrieved once per type), there’s still the massive overheads of using the reflection API to dynamically get the property values – something which must be performed during every call to Equals() and GetHashCode(). (Think about it – there’s no other way to get the property values. We can’t just cast to the subclass type, because we don’t know what the type is! It might not even exist at the point when the base class is compiled.)

No, i’m afraid reflection doesn’t address this need adequately. In my tests, a reflection-based Equals method like the one above performed at roughly 16 times slower than a type written using boilerplate code!

Expression Trees to the Rescue!

The poor performance of the reflection technique comes largely from the inability to ‘teach’ the runtime how to efficiently repeat the equality comparison once it has discovered the properties of the class; it never learns and it never gets faster! However, there is a different technique we can use which allows the runtime to discover how to perform an equality comparison efficiently after learning the process once; we can build an expression tree to model the equality comparison:

Expression trees are not only a means of representing lambda expressions in a dynamic, structured manner – their real power comes from the ability to dynamically construct an expression tree using the API, then compile it into bona fide, executable code – using Expression<T>.Compile(). What expression trees allow us to do in the context of our base class, then, is to dynamically create (and then compile) a tailor-made Equals() and GetHashCode() implementation for each subclass – and then call these methods again and again and again, with very little performance hit!

static Func<object, object, bool> MakeEqualsMethod(Type type) {
    ParameterExpression pThis = Expression.Parameter(typeof(object), "x");
    ParameterExpression pThat = Expression.Parameter(typeof(object), "y");

    // cast to the subclass type
    UnaryExpression pCastThis = Expression.Convert(pThis, type);
    UnaryExpression pCastThat = Expression.Convert(pThat, type);

    // compound AND expression using short-circuit evaluation
    Expression last = null;
    foreach (PropertyInfo property in type.GetProperties()) {
        BinaryExpression equals = Expression.Equal(
            Expression.Property(pCastThis, property),
            Expression.Property(pCastThat, property)
        );

        if (last == null)
            last = equals;
        else
            last = Expression.AndAlso(last, equals);
    }

    // call Object.Equals if second parameter doesn't match type
    last = Expression.Condition(
        Expression.TypeIs(pThat, type),
        last,
        Expression.Equal(pThis, pThat)
    );

    // compile method
    return Expression.Lambda<Func<object, object, bool>>(last, pThis, pThat)
        .Compile();
}

Of course, we must still use reflection when constructing the expression trees – how else will we discover the properties? But the key point is that we only have to do this step once; from then on, we have a compiled method (callable via a delegate) which is almost indistinguishable from one written using the boilerplate technique. The method takes parameters of type System.Object, because it would be impossible to cast to the subclass type (or write the delegate signature for it) if it required strongly-typed parameters.

The process for creating the GetHashCode() method is fairly similar; we simply replace the conditional AND nodes with XOR, and the Equals nodes with calls to each property’s own hash code method. Obviously, there’s only one input in this case.

We store the delegates for each subclass type against their corresponding System.Type in a class-scoped Dictionary<TKey,TValue>. When an instance is constructed, it checks to see if its type is in the dictionary; if not, it generates and compiles the methods, otherwise it simply proceeds. The delegates are invoked thusly:

public override int GetHashCode() {
    return _functions[GetType()].GetHashCodeFunc(this);
}

public override bool Equals(object obj) {
    return _functions[GetType()].EqualsFunc(this, obj);
}

Usage

With the base class written, all that is needed in order to access the member-wise equality functionality is to extend the class and add an arbitrary number of public properties (only a get accessor is required). For example:

public class MyMemberwiseType : MemberwiseEqualityObject {
    public Guid ID { get; set; }
    public int Number { get; set; }
    public DateTime Date { get; set; }
}

Any attempt to equate two instances of MyMemberwiseType will result in a member-wise comparison. Likewise, operations using the hash code (such as Enumerable.GroupBy) will also operate in this fashion.

Performance

I ran a simple test which compares the execution time of three different memberwise equality comparison techniques (anonymous types, reflection and my expression tree implementation). Each subclass had 8 properties, with each test instance being initialised with the same set of random values (making the test completely fair on each implementation). Under these conditions, when faced with the task of comparing 5 million instances for equality, I obtained the following results:

• Using an anonymous type: 0.770 sec – this is the fastest, obviously, since its Equals() method is generated at compile-time.
• Using reflection: 9.882 sec
• Using dynamically-compiled equality comparison: 0.972 sec

As you can see, there is a massive overhead in using reflection, however my dynamic compilation technique produces results which are much more comparable to a hard-coded method. There’s no such thing as a free lunch, as they say, but in this case the sacrifice is only a small one to avoid a lot of boilerplate code!

Final Words

Currently, the base class performs its comparison on all public properties, unconditionally. It would not be difficult to use a custom attribute type to include/exclude members from consideration, or even to allow non-public properties or fields to be included. Since these changes would affect only the structure of the expression tree (and not add any processing to the Equals() method itself), there would be no performance hit in doing so.

In summary, then, i’ve demonstrated how to save on boilerplate code for member-wise equality comparisons by writing a base class which dynamically generates Equals() and GetHashCode() methods, using expression trees. If, like me, you find the task of writing such code to be a tedious exercise, I hope you enjoy the possibilities presented by this solution 🙂

Download

MemberwiseEquality.zip – includes MemberwiseEqualityObject (the implementation itself), ReflectEqualityObject (for performance comparison) and a console application to replicate my tests.