Ускорение словарей на базе Enum с помощью обобщенного EnumComparer

Written on 04 Сентября 2013. Posted in C#.NET

В данной статье показано снижение быстродействия, вызванное упаковкой в словари, использующие ключи Enum, и дано решение, использующее генерацию легкого кода (DynamicMethod).

• Скачать исходники - 307.67 Кб

Введение

В данной статье представлен очень быстрый обобщенный класс EnumComparer, реализующий IEqualityComparer. Этот класс полезен для ускорения словарей с ключами Enum. В испытаниях он работает в 8 раз быстрее.

Предыстория

Универсальные коллекции были введены в .NET 2.0 и улучшены по сравнению с обычными коллекциями в 2 главных аспектах:

1. Безопасность типов
2. Быстродействие для элементов типа значения

Обычные коллекции рассматривали типы значений как System.Object, что вызывало много операций упаковки и распаковки. Универсальные коллекции устранили упаковку и улучшили быстродействие.

Так как Enum – тип значения, в большинстве случаев он выигрывает от улучшения. Однако когда Enum используется в качестве ключа обобщенного словаря, упаковка возвращается украдкой.

Словарь требует реализации равенства, чтобы определить, являются ли ключи равными, и реализация по умолчанию для типов, не реализующих IEquatable, использует переопределения Object.Equals и Object.GetHashCode. Так как Enum не реализует IEquatable, он приводится к object (упаковка), чтобы сравнить их.

Но не обязательно использовать реализацию по умолчанию: Класс Dictionary может принимать экземпляр IEqualityComparer в своем конструкторе. Надо задать IEqualityComparer для Enum, и упаковка исчезнет. Однако данное решение требует написания собственной реализации IEqualityComparer для каждого типа enum, используемого в качестве ключа словаря.

Хорошо бы было использовать мощь обобщений, чтобы один раз написать универсальный EnumComparer, работающий для Enum. Так можно сделать, но это непросто.

Первая попытка

Для начала было написано следующее:

// Не будет компилироваться
class EnumComparer<TEnum> : IEqualityComparer<TEnum>
{
    public bool Equals(TEnum x, TEnum y)
    {
        // ошибка CS0019: Оператор '=='
        // невозможно применить к операндам типа 'TEnum' и 'TEnum'
        return (x == y);
    }
    public int GetHashCode(TEnum obj)
    {
        // ошибка CS0030: Нельзя преобразовать тип 'TEnum' в 'int'
        return (int)obj;
    }
}

Но это работать не будет.

Другая возможность .NET 2.0 – облегченная версия Reflection.Emit. С ее помощью можно генерировать методы во время выполнения. Это позволит обойти ограничения обобщений. Отчасти это похоже на специализацию шаблона класса C++: генерируется специализированный метод для каждого обобщенного типа во время выполнения. Единственный недостаток данной возможности в том, что приходится писать генерируемый код на промежуточном языке. Посмотрим, как он используется.

Вторая попытка

Будут генерироваться 2 метода во время выполнения: один для реализации Equals, второй для реализации GetHashCode. Генерируются точно такие же реализации, как и в первой попытке, только на этот раз обходятся ошибки компилятора, поскольку они не важны во время выполнения.

Код приведен ниже:

/// <summary>
/// Быстрая и эффективная реализация 
/// <see cref="IEqualityComparer{T}"/> для типов Enum.
/// Полезна для словарей, использующих Enums как ключи.
/// </summary>
/// <example>
/// <code>
/// var dict = new Dictionary&lt;DayOfWeek, 
/// string&gt;(EnumComparer&lt;DayOfWeek&gt;.Instance);
/// </code>
/// </example>
/// <typeparam name="TEnum">Тип Enum.</typeparam>
public sealed class EnumComparer<TEnum> : IEqualityComparer<TEnum>
    where TEnum : struct, IComparable, IConvertible, IFormattable
{
    private static readonly Func<TEnum, TEnum, bool> equals;
    private static readonly Func<TEnum, int> getHashCode;
     /// <summary>
    /// Средство доступа - синглтон.
    /// </summary>
    public static readonly EnumComparer<TEnum> Instance;
    /// <summary>
    /// Инициализирует класс <see cref="EnumComparer{TEnum}"/>
    /// путем генерации методов GetHashCode и Equals.
    /// </summary>
    static EnumComparer()
    {
        getHashCode = generateGetHashCode();
        equals = generateEquals();
        Instance = new EnumComparer<TEnum>();
    }
     /// <summary>
    /// Закрытый конструктор для предотвращения создания экземпляра пользователем.
    /// </summary>
    private EnumComparer()
    {
        assertTypeIsEnum();
        assertUnderlyingTypeIsSupported();
    }
    /// <summary>
    /// Определяет, равны ли заданные объекты.
    /// </summary>
    /// <param name="x">Первый объект типа <typeparamref name="TEnum"/> 
    /// to compare.</param>
    /// <param name="y">Второй объект типа <typeparamref name="TEnum"/> 
    /// to compare.</param>
    /// <returns>
    /// истина, если заданные объекты равны; иначе ложь.
    /// </returns>
    public bool Equals(TEnum x, TEnum y)
    {
        // вызывается сгенерированный метод
        return equals(x, y);
    }
    /// <summary>
    /// Возвращает хэш-код для заданного объекта.
    /// </summary>
    /// <param name="obj">Объект <see cref="T:System.Object"/> 
    /// для которого надлежит вернуть хэш-код.</param>
    /// <returns>Хэш-код для заданного объекта.</returns>
    /// <exception cref="T:System.ArgumentNullException">
    /// Тип <paramref name="obj"/> является ссылочным типом, и
    /// <paramref name="obj"/> пустой.
    /// </exception>
    public int GetHashCode(TEnum obj)
    {
        // вызывается сгенерированный метод
        return getHashCode(obj);
    }
     private static void assertTypeIsEnum()
    {
        if (typeof (TEnum).IsEnum)
            return;
         var message =
            string.Format("The type parameter {0} is not an Enum. 
            LcgEnumComparer supports Enums only.",
                              typeof (TEnum));
        throw new NotSupportedException(message);
    }
     private static void assertUnderlyingTypeIsSupported()
    {
        var underlyingType = Enum.GetUnderlyingType(typeof (TEnum));
        ICollection<Type> supportedTypes =
            new[]
                {
                    typeof (byte), typeof (sbyte), typeof (short), typeof (ushort),
                    typeof (int), typeof (uint), typeof (long), typeof (ulong)
                };
         if (supportedTypes.Contains(underlyingType))
            return;
         var message =
           string.Format("The underlying type of the type parameter {0} is {1}. " +
                         "LcgEnumComparer only supports Enums with underlying type of " +
                         "byte, sbyte, short, ushort, int, uint, long, or ulong.",
                         typeof (TEnum), underlyingType);
        throw new NotSupportedException(message);
    }
    /// <summary>
    /// Генерирует метод сравнения, сходный с этим:
    /// <code>
    /// bool Equals(TEnum x, TEnum y)
    /// {
    ///     return x == y;
    /// }
    /// </code>
    /// </summary>
    /// <returns>Сгенерированный метод.</returns>
    private static Func<TEnum, TEnum, bool> generateEquals()
    {
        var method = new DynamicMethod(typeof (TEnum).Name + "_Equals",
                                       typeof (bool),
                                       new[] {typeof (TEnum), typeof (TEnum)},
                                       typeof (TEnum), true);
        var generator = method.GetILGenerator();
        // Пишется тело
        generator.Emit(OpCodes.Ldarg_0);    // x загружается в стек
        generator.Emit(OpCodes.Ldarg_1);    // y загружается в стек
        generator.Emit(OpCodes.Ceq);        // x == y
        generator.Emit(OpCodes.Ret);        // возвращается результат
         return (Func<TEnum, TEnum, bool>)method.CreateDelegate
                    (typeof(Func<TEnum, TEnum, bool>));
    }
    /// <summary>
    /// Генерирует метод GetHashCode, сходный с этим:
    /// <code>
    /// int GetHashCode(TEnum obj)
    /// {
    ///     return ((int)obj).GetHashCode();
    /// }
    /// </code>
    /// </summary>
    /// <returns>Сгенерированный метод.</returns>
    private static Func<TEnum, int> generateGetHashCode()
    {
        var method = new DynamicMethod(typeof (TEnum).Name + "_GetHashCode",
                                       typeof (int),
                                       new[] {typeof (TEnum)},
                                       typeof (TEnum), true);
        var generator = method.GetILGenerator();
        var underlyingType = Enum.GetUnderlyingType(typeof (TEnum));
        var getHashCodeMethod = underlyingType.GetMethod("GetHashCode");
        var castValue =  generator.DeclareLocal(underlyingType);
        // Пишется тело
        generator.Emit(OpCodes.Ldarg_0);                    // obj загружается в стек
        generator.Emit(OpCodes.Stloc_0);                    // castValue = obj
        generator.Emit(OpCodes.Ldloca_S, castValue);        // *castValue загружается в //стек
        generator.Emit(OpCodes.Call, getHashCodeMethod);    // castValue.GetHashCode()
        generator.Emit(OpCodes.Ret);                        // возвращается результат
        return (Func<TEnum, int>)method.CreateDelegate(typeof(Func<TEnum, int>));
    }
}

Данное решение быстрое и универсальное. Но нельзя ли сделать лучше? Оказывается, можно.

Третий лучший вариант

LCG – прекрасная техника генерации кода, но .NET 3.5 & C# 3 ввел новый улучшенный способ: деревья выражений. Это иерархии, представляющие выражения. Для генерации кода строится дерево выражений во время выполнения и компилируется в делегат. Так как дерево выражений состоит из объектов, его легче строить и хранить, чем манипулировать промежуточным языком в DynamicMethod. Хороший пример этого есть тут.

Как реализовать EnumComparer с помощью деревьев выражений? Ниже показана новая реализация методов generateEquals() и generateGetHashCode():

private static Func<TEnum, TEnum, bool> generateEquals()
{
    var xParam = Expression.Parameter(typeof(TEnum), "x");
    var yParam = Expression.Parameter(typeof(TEnum), "y");
    var equalExpression = Expression.Equal(xParam, yParam);
    return Expression.Lambda<Func<TEnum, TEnum, bool>>(equalExpression, new[] 
                        { xParam, yParam }).Compile();
}
 private static Func<TEnum, int> generateGetHashCode()
{
    var objParam = Expression.Parameter(typeof(TEnum), "obj");
    var underlyingType = Enum.GetUnderlyingType(typeof (TEnum));
    var convertExpression = Expression.Convert(objParam, underlyingType);
    var getHashCodeMethod = underlyingType.GetMethod("GetHashCode");
    var getHashCodeExpression = Expression.Call(convertExpression, getHashCodeMethod);
    return Expression.Lambda<Func<TEnum, int>>(getHashCodeExpression, new[] 
                        { objParam }).Compile();
}

Имейте в виду, что если в проекте используется .NET 2.0, можно использовать только версию LCG.

форум c#

Ускорение словарей на базе Enum с помощью обобщенного EnumComparer

ОГЛАВЛЕНИЕ

Введение