Производительность.NET Tuple and 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 звонки. Это результат:

1-й подход (оригинальная реализация.NET) - 310 мс

2-й подход - 60 мс

3-й подход - 130 мс

Реализация по умолчанию примерно в 4-5 раз медленнее, чем оптимальное решение.

Answer 1

Вы задавались вопросом, должно ли это быть реализовано таким образом. Короче говоря, я бы сказал нет: существует множество функционально эквивалентных реализаций.

Но почему существующая реализация делает такое явное использование EqualityComparer<object>.Default? Это может быть просто случай человека, который написал эту ментальную оптимизацию для "неправильного", или, по крайней мере, другую вещь, чем ваш сценарий скорости во внутреннем цикле. В зависимости от их теста это может показаться "правильным".

Но какой эталонный сценарий может заставить их сделать такой выбор? Похоже, что оптимизация, на которую они нацелены, заключается в том, чтобы оптимизировать минимальное количество экземпляров шаблона класса EqualityComparer. Вероятно, они выберут это, потому что создание шаблона требует затрат памяти и времени загрузки. Если это так, мы можем предположить, что их сценарий эталонного теста мог основываться на времени запуска приложения или использовании памяти, а не на каком-то жестком цикле.

Вот одна точка знаний, подтверждающая теорию (найденная с использованием смещения подтверждения:) - Тела метода реализаций EqualityComparer не могут быть разделены, если T является структурой. Выдержки из http://blogs.microsoft.co.il/sasha/2012/09/18/runtime-representation-of-genericspart-2/

Когда CLR необходимо создать экземпляр закрытого универсального типа, такого как List, он создает таблицу методов и EEClass на основе открытого типа. Как всегда, таблица методов содержит указатели на методы, которые компилируются на лету компилятором JIT. Однако здесь есть критически важная оптимизация: тела скомпилированных методов на закрытых универсальных типах, которые имеют параметры ссылочного типа, могут использоваться совместно. [...] Та же идея не работает для типов значений. Например, когда T является длинным, оператор присваивания items[size] = item требует другой инструкции, потому что вместо 4. Необходимо скопировать 8 байтов, даже для типов с большими значениями может потребоваться более одной инструкции; и так далее.