.NET元组和Equals性能

Question

直到今天我才注意到的一件事情。显然，.NET实现的常用元组类（Tuple<T>，Tuple<T1, T2>等）在执行基于相等性的操作时会对值类型产生装箱惩罚。

以下是该类在框架中的实现方式（通过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;
    }
}

我看到的问题是它会导致两个阶段的装箱和拆箱，例如对于Equals调用，第一步在comparer.Equals处将项目装箱，第二步，EqualityComparer<object>调用非泛型Equals，这将内部转而必须将项目拆箱为原始类型。

为什么他们不做像这样的事情呢：

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;
}

我对在.NET元组类中这样实现平等感到惊讶。我将元组类型用作字典中的键。

有没有什么理由必须按照第一个代码所示进行实现？在这种情况下使用该类有点令人沮丧。

我认为代码重构和非重复数据不应该是主要问题。相同的非泛型/装箱实现也适用于IStructuralComparable，但由于IStructuralComparable.CompareTo不常用，因此通常不会出现问题。

---

我用第三种方法（只包含基本要素）对上述两种方法进行了基准测试，这种方法仍然较少负荷：

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);
} 

对于一些Tuple<DateTime，DateTime>字段进行了1000000次Equals调用，这是结果：

第一种方法（原始.NET实现）- 310毫秒

第二种方法 - 60毫秒

第三种方法 - 130毫秒

默认实现比最优解慢4-5倍。

- nawfal

---

我并没有看到为什么要使用 IEqualityComparer<object>，但我并不是说没有理由。但你仍然可以让它更好一些：http://pastebin.com/tNA2FYjq - MarcinJuraszek

@MarcinJuraszek 这样好在哪里呢？Tuple<,>实现了IStructuralEquatable，其中包含以下定义：bool Equals(object other, IEqualityComparer comparer); int GetHashCode(IEqualityComparer comparer); - nawfal

针对您的第二个例子做一个测试，其中“Tuple”类型不同。个人认为，如果您将元组用作键，则很可能成为创建具有明确相等性实现的适当命名的类的候选项，这将提高可读性。此外，您能提供用于测试性能的代码吗？我曾经遇到过与哈希码相关的性能问题，特别是在结构化键上，提供具有实现相等性的自定义类型或自定义相等性比较器可以显着提高性能，正如您所看到的。 - Adam Houldsworth

@nawfal 我们在服务器端使用了很多字典作为贫民缓存，最近我们清理了定义不清晰的复合键（目前是我们自己在.NET 2.0上实现的 Tuple），并审查了所有使用复合字典的情况。我们采取了两种方法。1）在字典中使用复合键，由自定义类或结构体制成，类型本身或字典上具有自定义相等性。2）嵌套字典的复合字典结构。根据键宽度创建很多字典，但访问非常快。性能得到了提高。 - Adam Houldsworth

@nawfal 类和结构体自定义键之间的区别微不足道，取决于诸如结构体大小和最终使用等某些因素，但通常重要的是提供良好的相等性实现。回答你的问题，Tuple默认代码可能不太理想，但除非编写/批准代码的人出现，否则你不太可能理解导致结果实现背后的动机。 - Adam Houldsworth

Answer 1

您想知道是否必须以这种方式实现。简而言之，我会说不需要：有许多功能等效的实现。

但是为什么现有实现如此明确地使用EqualityComparer .Default？可能只是编写此代码的人在心理上优化了与您在内部循环中速度方面不同的“错误”或至少不同的东西。根据他们的基准测试，它可能看起来是“正确”的选择。

但是什么基准测试场景可能导致他们做出这种选择呢？嗯，他们所针对的优化似乎是优化EqualityComparer类模板实例的最小数量。他们可能会选择这样做，因为模板实例化带有内存或加载时间成本。如果是这样，我们可以猜测他们的基准测试场景可能基于应用程序启动时间或内存使用情况，而不是某些紧密循环的情况。

这里有一个知识点支持这个理论（通过使用确认偏见找到 - 如果T是结构体，则EqualityComparer实现方法体不能共享）。摘自http://blogs.microsoft.co.il/sasha/2012/09/18/runtime-representation-of-genericspart-2/ 当CLR需要创建一个封闭泛型类型的实例，例如List时，它会基于开放类型创建一个方法表和EEClass。与往常一样，方法表包含方法指针，这些指针由JIT编译器即时编译。然而，在这里有一个关键的优化：对于具有引用类型参数的封闭泛型类型，可以共享已编译的方法体。但是，对于值类型，相同的想法并不适用。例如，当T为long时，赋值语句items[size] = item需要不同的指令，因为必须复制8个字节而不是4个字节。甚至更大的值类型可能需要多个指令等等。

- Tim Lovell-Smith