Accelerating Enum-Based Dictionaries with Generic EnumComparer

• Download source - 307.67 KB

Introduction

In this article, I'll introduce a very fast generic EnumComparer class that implements IEqualityComparer. This class is useful for accelerating dictionaries with Enum keys. In my tests, it run roughly x8 faster.

Background

Generic collections were introduced in .NET 2.0 and improved upon regular collections in 2 main aspects:

1. Type safety
2. Performance for value-type elements

Regular collections treated value-types as System.Object and this caused lots of boxing & unboxing operations. Generic collections eliminated the boxing and improved performance.

Since Enums are value-types, you'd expect them to benefit from this improvement as well, and most of the time you'll be correct. However, when an Enum is used as a key of a generic Dictionary boxing returns from the back door.

I was surprised when I first learned of this little-known fact. Vojislav Stojkovic researched and described it in his article: .NUTS: Enum Conundrum. I strongly recommend that you read it.

To sum up his conclusions: Dictionary requires an equality implementation to determine whether keys are equal, and the default implementation for types that does not implement IEquatable uses the overrides of Object.Equals and Object.GetHashCode. Since Enums do not implement IEquatable, they'll be casted to object (boxing) in order to compare them.

However we don't have to use the default implementation: The Dictionary class can accept an IEqualityComparer instance in its constructor. All we have to do is supply an IEqualityComparer for our Enum and the boxing will go away. And this is exactly what Vojislav did. However this solution requires you to write your implementation of IEqualityComparer for each enum type you intend to use as a dictionary key.

Wouldn't it be nice if we could leverage the power of generics to write once a generic EnumComparer that will work for Enums? It would - but it ain't gonna be easy.

First Attempt

Let's begin by writing something like this:

// WON'T COMPILE
class EnumComparer<TEnum> : IEqualityComparer<TEnum>
{
    public bool Equals(TEnum x, TEnum y)
    {
        // error CS0019: Operator '=='
        // cannot be applied to operands of type 'TEnum' and 'TEnum'
        return (x == y);
    }
    public int GetHashCode(TEnum obj)
    {
        // error CS0030: Cannot convert type 'TEnum' to 'int'
        return (int)obj;
    }
}

As Vojislav found out, this is not going to work.

Or is it?

Another .NET 2.0 feature is a lightweight version of Reflection.Emit. With it, we can generate methods at runtime. This is useful because it'll let us bypass the constraints of generics. In a way, it's like C++ class template specialization: we'll generate a specialized method for each generic type at runtime. The only downside for this feature is that you need to write the code you generate in IL. A good primer on the subject (called DynamicMethod or Lightweight Code Generation/LCG) can be found here.

So how is it used? Let's see.

Second Attempt

We're going to generate 2 methods at runtime: one for the Equals implementation, and the other for the GetHashCode implementation. The implementations that we'll generate are exactly the same as the ones in our first attempt, only this time we'll be able to bypass the compiler errors as they're not relevant at runtime.

So without further ado, here's the code:

/// <summary>
/// A fast and efficient implementation of 
/// <see cref="IEqualityComparer{T}"/> for Enum types.
/// Useful for dictionaries that use Enums as their keys.
/// </summary>
/// <example>
/// <code>
/// var dict = new Dictionary&lt;DayOfWeek, 
/// string&gt;(EnumComparer&lt;DayOfWeek&gt;.Instance);
/// </code>
/// </example>
/// <typeparam name="TEnum">The type of the 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>
    /// The singleton accessor.
    /// </summary>
    public static readonly EnumComparer<TEnum> Instance;
    /// <summary>
    /// Initializes the <see cref="EnumComparer{TEnum}"/> class
    /// by generating the GetHashCode and Equals methods.
    /// </summary>
    static EnumComparer()
    {
        getHashCode = generateGetHashCode();
        equals = generateEquals();
        Instance = new EnumComparer<TEnum>();
    }
     /// <summary>
    /// A private constructor to prevent user instantiation.
    /// </summary>
    private EnumComparer()
    {
        assertTypeIsEnum();
        assertUnderlyingTypeIsSupported();
    }
    /// <summary>
    /// Determines whether the specified objects are equal.
    /// </summary>
    /// <param name="x">The first object of type <typeparamref name="TEnum"/> 
    /// to compare.</param>
    /// <param name="y">The second object of type <typeparamref name="TEnum"/> 
    /// to compare.</param>
    /// <returns>
    /// true if the specified objects are equal; otherwise, false.
    /// </returns>
    public bool Equals(TEnum x, TEnum y)
    {
        // call the generated method
        return equals(x, y);
    }
    /// <summary>
    /// Returns a hash code for the specified object.
    /// </summary>
    /// <param name="obj">The <see cref="T:System.Object"/> 
    /// for which a hash code is to be returned.</param>
    /// <returns>A hash code for the specified object.</returns>
    /// <exception cref="T:System.ArgumentNullException">
    /// The type of <paramref name="obj"/> is a reference type and 
    /// <paramref name="obj"/> is null.
    /// </exception>
    public int GetHashCode(TEnum obj)
    {
        // call the generated method
        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>
    /// Generates a comparison method similar to this:
    /// <code>
    /// bool Equals(TEnum x, TEnum y)
    /// {
    ///     return x == y;
    /// }
    /// </code>
    /// </summary>
    /// <returns>The generated method.</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();
        // Writing body
        generator.Emit(OpCodes.Ldarg_0);    // load x to stack
        generator.Emit(OpCodes.Ldarg_1);    // load y to stack
        generator.Emit(OpCodes.Ceq);        // x == y
        generator.Emit(OpCodes.Ret);        // return result
         return (Func<TEnum, TEnum, bool>)method.CreateDelegate
					(typeof(Func<TEnum, TEnum, bool>));
    }
    /// <summary>
    /// Generates a GetHashCode method similar to this:
    /// <code>
    /// int GetHashCode(TEnum obj)
    /// {
    ///     return ((int)obj).GetHashCode();
    /// }
    /// </code>
    /// </summary>
    /// <returns>The generated method.</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);
        // Writing body
        generator.Emit(OpCodes.Ldarg_0);                    // load obj to stack
        generator.Emit(OpCodes.Stloc_0);                    // castValue = obj
        generator.Emit(OpCodes.Ldloca_S, castValue);        // load *castValue to stack
        generator.Emit(OpCodes.Call, getHashCodeMethod);    // castValue.GetHashCode()
        generator.Emit(OpCodes.Ret);                        // return result
        return (Func<TEnum, int>)method.CreateDelegate(typeof(Func<TEnum, int>));
    }
}

This solution is both fast and generic. But can it be better?

As reader Simone Busoli kindly pointed out, it can.

Third Time's the Charm

LCG is a great code-generation technique, but .NET 3.5 & C# 3 introduced a new and improved method: Expression Trees. Basically they are hierarchies that represents expressions. To generate code, you can build an Expression Tree at runtime, and compile it to a delegate. Since an Expression Tree is composed of objects, it is easier to build and maintain than manipulating IL in a DynamicMethod. A good primer on this can be found here.

So, how can we implement our EnumComparer using Expression Trees? Here is the new implementation for our generateEquals() and generateGetHashCode() methods:

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

Note that if you have to use .NET 2.0 in your project, you can only use the LCG version.

Using the Code

To use the EnumComparer, you just have to pass it to the Dictionary:

var comparer = EnumComparer<DayOfWeek>.Instance;
var dictionary = new Dictionary<DayOfWeek, int>(comparer);

Benchmark

This article wouldn't be complete without some numbers, would it?

I tested both implementations of the EnumComparer against a hand-written comparer, the default comparer, and a Dictionary of ints. I ran 1,000,000 iterations on a dictionary and the results were promising:

Both generic EnumComparers are almost as good as the hand-written comparer! And the Expression Tree version is not only clearer, but even faster than the LCG version.

As a side note, I have to wonder why it is faster. I know that Expression Trees are using LCG for compilation. So I wonder how could it generate faster code? If you can figure out why, I'd love if you add a comment.

What about the cost of generating the code at the initial build phase? Let's have a look:

Here both are much slower to build than the hand-written comparer (simple class construction). So you should consider using this solution only when you're expecting to do lots of comparisons (tens of thousands).

(Note: When I first wrote the article, my tests showed that the generic EnumComparer was slightly faster than the hand-written one. However, when I approached the benchmarks again, the hand-written comparer turned out to be faster. I don't know why the results changed, but now the attached file includes the full benchmarking code, and you could test it yourself.)

Afterthoughts

The performance problem of the Dictionary surprised me when I first learnt of it. And the fact that the trivial solution of a generic comparer is not so easy to build gave me that special itch that I had to scratch. So I sat down, and hammered the keyboard until an elegant solution emerged.

But then a new question popped to mind: When should this solution be used?

My first answer was: "Probably never". The reason is that it would likely be premature/micro-optimization. As you should know, optimization should be done only when you have real knowledge about where your bottlenecks are.

After I first published the article, I found that some real-world usage might see the light of day: Ayende blogged about a real performance problem in NHibernate that could be remedied by this solution. So maybe it's not as useless as I thought. :-)

Another good outcome from publishing the article was Simon Busoli's comment about improving my solution using Expression Trees. This made me quite happy, so I decided to update the article.

To conclude, I hope you enjoyed reading this as much as I enjoyed writing it. And who knows? You might even find this useful.

Sample Project

The solution contains 3 projects:

1. The code shown here
2. Unit-tests
3. Benchmarks

References

• [1] Stojkovic, Vojislav. .NUTS: Enum Conundrum. [online] http://beardseye.blogspot.com/2007/08/nuts-enum-conundrum.html

History

• 20^th February, 2009: Initial post
• 4^th March, 2009: Added improved version using Expression Trees