.NET Tuple and Equals performance

Question

This is something I had not noticed until today. Apparently, the .NET implementation of the much used tuple classes (Tuple<T>, Tuple<T1, T2> etc) causes boxing penalties for value types when equality based operations are performed.

Here is how the class is kind of implemented in the framework (source via ILSpy):

public class Tuple<T1, T2> : IStructuralEquatable 
{
    public T1 Item1 { get; private set; }
    public T2 Item2 { get; private set; }

    public Tuple(T1 item1, T2 item2)
    {
        this.Item1 = item1;
        this.Item2 = item2;
    }

    public override bool Equals(object obj)
    {
        return this.Equals(obj, EqualityComparer<object>.Default);
    }

    public override int GetHashCode()
    {
        return this.GetHashCode(EqualityComparer<object>.Default);
    }

    public bool Equals(object obj, IEqualityComparer comparer)
    {
        if (obj == null)
        {
            return false;
        }

        var tuple = obj as Tuple<T1, T2>;
        return tuple != null 
            && comparer.Equals(this.Item1, tuple.Item1) 
            && comparer.Equals(this.Item2, tuple.Item2);
    }

    public int GetHashCode(IEqualityComparer comparer)
    {
        int h1 = comparer.GetHashCode(this.Item1);
        int h2 = comparer.GetHashCode(this.Item2);

        return (h1 << 5) + h1 ^ h2;
    }
}

The problem I see is it causes a two stage boxing-unboxing, say for Equals calls, one, at the comparer.Equals which boxes the item, two, the EqualityComparer<object> calls the non-generic Equals which in turn will internally have to unbox the item to orginal type.

Instead why wouldn't they do something like:

public override bool Equals(object obj)
{
    var tuple = obj as Tuple<T1, T2>;
    return tuple != null
        && EqualityComparer<T1>.Default.Equals(this.Item1, tuple.Item1)
        && EqualityComparer<T2>.Default.Equals(this.Item2, tuple.Item2);
}

public override int GetHashCode()
{
    int h1 = EqualityComparer<T1>.Default.GetHashCode(this.Item1);
    int h2 = EqualityComparer<T2>.Default.GetHashCode(this.Item2);

    return (h1 << 5) + h1 ^ h2;
}

public bool Equals(object obj, IEqualityComparer comparer)
{
    var tuple = obj as Tuple<T1, T2>;
    return tuple != null
        && comparer.Equals(this.Item1, tuple.Item1)
        && comparer.Equals(this.Item2, tuple.Item2);
}

public int GetHashCode(IEqualityComparer comparer)
{
    int h1 = comparer.GetHashCode(this.Item1);
    int h2 = comparer.GetHashCode(this.Item2);

    return (h1 << 5) + h1 ^ h2;
}

I was surprised to see equality implemented this way in .NET tuple class. I was using tuple type as a key in one of the dictionaries.

Is there any reason why this has to be implemented as shown in the first code? Its a bit discouraging to make use of this class in that case.

I dont think code refactoring and non-duplicating data should have been the major concerns. The same non-generic/boxing implementation has gone behind IStructuralComparable too, but since IStructuralComparable.CompareTo is less used its not a problem often.

---

I benchmarked the above two approaches with a third approach which is still less taxing, like this (only the essentials):

public override bool Equals(object obj)
{
    return this.Equals(obj, EqualityComparer<T1>.Default, EqualityComparer<T2>.Default);
}

public bool Equals(object obj, IEqualityComparer comparer)
{
    return this.Equals(obj, comparer, comparer);
}

private bool Equals(object obj, IEqualityComparer comparer1, IEqualityComparer comparer2)
{
    var tuple = obj as Tuple<T1, T2>;
    return tuple != null
        && comparer1.Equals(this.Item1, tuple.Item1)
        && comparer2.Equals(this.Item2, tuple.Item2);
} 

for a couple of Tuple<DateTime, DateTime> fields a 1000000 Equals calls. This is the result:

1st approach (original .NET implementation) - 310 ms

2nd approach - 60 ms

3rd approach - 130 ms

The default implementation is about 4-5 times slower than the optimal solution.

Answer 1

You wondered if it 'has to' be implemented that way. In short, I would say no: there are many functionally equivalent implementations.

But why does the existing implementation make such explicit usage of EqualityComparer<object>.Default? It may just be a case of the person who wrote this mentally optimizing for the 'wrong', or at least different thing than your scenario of speed in an inner loop. Depending on their benchmark it may appear be the 'right' thing.

But what benchmark scenario could lead them to make that choice? Well the optimization they have targeted seems to be to optimize for the minimum number of EqualityComparer class template instantiations. They might likely choose this because template instantiation comes with memory or load-time costs. If so, we can guess their benchmark scenario could have been based on app-startup-time or memory usage rather than some tight looping scenario.

Here is one knowledge point to support the theory (found by using confirmation bias :) - EqualityComparer implementations method bodies cannot be shared if T is a struct. Excerpted from http://blogs.microsoft.co.il/sasha/2012/09/18/runtime-representation-of-genericspart-2/

When the CLR needs to create an instance of a closed generic type, such as List, it creates a method table and EEClass based on the open type. As always, the method table contains method pointers, which are compiled on the fly by the JIT compiler. However, there is a crucial optimization here: compiled method bodies on closed generic types that have reference type parameters can be shared. [...] The same idea does not work for value types. For example, when T is long, the assignment statement items[size] = item requires a different instruction, because 8 bytes must be copied instead of 4. Even larger value types may even require more than one instruction; and so on.