What is the algorithm used by the memberwise equality test in .NET structs?

Question

What is the algorithm used by the memberwise equality test in .NET structs? I would like to know this so that I can use it as the basis for my own algorithm.

I am trying to write a recursive memberwise equality test for arbitrary objects (in C#) for testing the logical equality of DTOs. This is considerably easier if the DTOs are structs (since ValueType.Equals does mostly the right thing) but that is not always appropriate. I would also like to override comparison of any IEnumerable objects (but not strings!) so that their contents are compared rather than their properties.

This has proven to be harder than I would expect. Any hints will be greatly appreciated. I'll accept the answer that proves most useful or supplies a link to the most useful information.

Thanks.

Answer 1

There is no default memberwise equality, but for the base value types (float, byte, decimal etc), the language spec demands bitwise comparison. The JIT optimizer optimizes this to the proper assembly instructions, but technically this behavior is equal to the C memcmp function.

Some BCL examples

• DateTime simply compares its internal InternalTicks member field, which is a long;
• PointF compares X and Y as in (left.X == right.X) && (left.Y == right.Y);
• Decimal does not compare internal fields but falls back to InternalImpl, which means, it's in the internal unviewable .NET part (but you can check SSCLI);
• Rectangle explicitly compares each field (x, y, width, height);
• ModuleHandle uses its Equals override and there are many more that do this;
• SqlString and other SqlXXX structs uses its IComparable.Compare implementation;
• Guid is the weirdest in this list: it has its own short-circuit long list of if-statements comparing each and every internal field (_a to _k, all int) for inequality, returning false when unequal. If all are not unequal, it returns true.

Conclusion

This list is rather arbitrary, but I hope it shines some light on the issue: there's no default method available, and even the BCL uses a different approach for each struct, depending on its purpose. The bottom line seems to be that later additions more frequently call their Equals override or Icomparable.Compare, but that merely moves the issue to another method.

Other ways:

You can use reflection to go through each field, but this is very slow. You can also create a single extension method or static helper that does a bitwise compare on the internal fields. Use StructLayout.Sequential, take the memory address and the size, and compare the memory blocks. This requires unsafe code, but it is quick, easy (and a bit dirty).

Update: rephrasing, added some actual examples, added new conclusion

---

Update: implementation of memberwise compare

The above was apparently a slight misunderstanding of the question, but I leave it there since I think it contains some value for future visitors regardless. Here's a more to the point answer:

Here's an implementation of a memberwise compare for objects and value types alike, that can go through all properties, fields and enumerable contents, recursively no matter how deep. It is not tested, probably contains some typos, but it compiles alright. See comments in code for more details:

public static bool MemberCompare(object left, object right)
{
    if (Object.ReferenceEquals(left, right))
        return true;

    if (left == null || right == null)
        return false;

    Type type = left.GetType();
    if (type != right.GetType())
        return false;

    if(left as ValueType != null)
    {
        // do a field comparison, or use the override if Equals is implemented:
        return left.Equals(right);
    }

    // check for override:
    if (type != typeof(object)
        && type == type.GetMethod("Equals").DeclaringType)
    {
        // the Equals method is overridden, use it:
        return left.Equals(right);
    }

    // all Arrays, Lists, IEnumerable<> etc implement IEnumerable
    if (left as IEnumerable != null)
    {
        IEnumerator rightEnumerator = (right as IEnumerable).GetEnumerator();
        rightEnumerator.Reset();
        foreach (object leftItem in left as IEnumerable)
        {
            // unequal amount of items
            if (!rightEnumerator.MoveNext())
                return false;
            else
            {
                if (!MemberCompare(leftItem, rightEnumerator.Current))
                    return false;
            }                    
        }
    }
    else
    {
        // compare each property
        foreach (PropertyInfo info in type.GetProperties(
            BindingFlags.Public | 
            BindingFlags.NonPublic | 
            BindingFlags.Instance | 
            BindingFlags.GetProperty))
        {
            // TODO: need to special-case indexable properties
            if (!MemberCompare(info.GetValue(left, null), info.GetValue(right, null)))
                return false;
        }

        // compare each field
        foreach (FieldInfo info in type.GetFields(
            BindingFlags.GetField |
            BindingFlags.NonPublic |
            BindingFlags.Public |
            BindingFlags.Instance))
        {
            if (!MemberCompare(info.GetValue(left), info.GetValue(right)))
                return false;
        }
    }
    return true;
}

Update: fixed a few errors, added use of overridden Equals if and only if available
Update: object.Equals should not be considered an override, fixed.