Производительность .NET Tuple и Equals

Это то, чего я не заметил до сегодняшнего дня. По-видимому,.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 tuple. Я использовал тип кортежа в качестве ключа в одном из словарей.

Есть ли какая-то причина, по которой это должно быть реализовано, как показано в первом коде?. Это немного обескураживает использование этого класса в этом случае.

Я не думаю, что рефакторинг кода и не дублирование данных должны были быть главной проблемой. Такая же реализация не общего/бокса отстала от 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 мс

Второй подход - 60 мс

Третий подход - 130 мс

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

Ответы

Ответ 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 длинно, Элементы позиции присваивания [размер] = элемент требует другого потому что 8 байтов должны быть скопированы вместо 4. Еще больше типы значений могут даже потребовать более одной инструкции; и т.д.