Click here to Skip to main content
14,216,574 members
Click here to Skip to main content
Posted 19 Feb 2009


75 bookmarked

Accelerating Enum-Based Dictionaries with Generic EnumComparer

Rate this:
4.81 (32 votes)
Please Sign up or sign in to vote.
4.81 (32 votes)
5 Mar 2009     CPOL    
In this article, I will demonstrate a performance problem caused by boxing in Dictionaries that use Enums as keys, and will provide a solution using lightweight code generation (DynamicMethod).


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.


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:

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()
    /// <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)
         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 =
                    typeof (byte), typeof (sbyte), typeof (short), typeof (ushort),
                    typeof (int), typeof (uint), typeof (long), typeof (ulong)
         if (supportedTypes.Contains(underlyingType))
         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);


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:

Benchmark Results (add)

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:

Benchmark Results (build)

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.)


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



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


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Omer Mor
Israel Israel
I am a programmer since I got my first Apple IIe, and I love it.
Currently I am working with Microsoft technologies. I enjoy working on systems at the architecture level, while at the same time I can't help myself from tinkering with the bits & bytes. I also find a good debugging session to be as enjoyable as solving an elegant riddle.

Comments and Discussions

QuestionGreat Article Pin
Dave Kerr4-Oct-11 20:49
mvaDave Kerr4-Oct-11 20:49 
QuestionWhat about .Net 4.0? Pin
Mike Nakis16-May-11 21:14
memberMike Nakis16-May-11 21:14 
AnswerRe: What about .Net 4.0? Pin
Omer Mor23-Jul-11 9:44
memberOmer Mor23-Jul-11 9:44 
GeneralSpeculation why Expression Trees are faster Pin
wishay4-Apr-11 3:12
memberwishay4-Apr-11 3:12 
GeneralRe: Speculation why Expression Trees are faster Pin
Omer Mor23-Jul-11 10:31
memberOmer Mor23-Jul-11 10:31 
GeneralImplementing IComparer<T> interface Pin
kamuuser27-May-10 4:36
memberkamuuser27-May-10 4:36 
GeneralRe: Implementing IComparer interface Pin
Omer Mor23-Jul-11 10:29
memberOmer Mor23-Jul-11 10:29 
GeneralAwesomely useful idea! Pin
bentomkins23-Aug-09 7:48
memberbentomkins23-Aug-09 7:48 
GeneralRe: Awesomely useful idea! Pin
Omer Mor1-Apr-10 12:00
memberOmer Mor1-Apr-10 12:00 
Generalcool Pin
Mubi | www.mrmubi.com24-Jun-09 9:47
professionalMubi | www.mrmubi.com24-Jun-09 9:47 
Question"Probably never"? Pin
Qwertie14-Mar-09 8:09
memberQwertie14-Mar-09 8:09 
AnswerRe: "Probably never"? Pin
Omer Mor16-Mar-09 10:49
memberOmer Mor16-Mar-09 10:49 
GeneralSorry, but I've got to ask .... Pin
stano12-Mar-09 6:34
memberstano12-Mar-09 6:34 
AnswerRe: Sorry, but I've got to ask .... Pin
Omer Mor12-Mar-09 9:46
memberOmer Mor12-Mar-09 9:46 
GeneralRe: Sorry, but I've got to ask .... Pin
stano12-Mar-09 17:32
memberstano12-Mar-09 17:32 
GeneralRe: Sorry, but I've got to ask .... Pin
Omer Mor13-Mar-09 10:24
memberOmer Mor13-Mar-09 10:24 
GeneralTest benchmarks Pin
GLLNS24-Feb-09 4:04
memberGLLNS24-Feb-09 4:04 
AnswerRe: Test benchmarks Pin
Omer Mor24-Feb-09 5:14
memberOmer Mor24-Feb-09 5:14 
GeneralRe: Test benchmarks Pin
GLLNS24-Feb-09 5:33
memberGLLNS24-Feb-09 5:33 
GeneralRe: Test benchmarks Pin
Omer Mor24-Feb-09 10:33
memberOmer Mor24-Feb-09 10:33 
GeneralWe're in the C# 3 era Pin
Simone Busoli21-Feb-09 3:34
memberSimone Busoli21-Feb-09 3:34 
AnswerRe: We're in the C# 3 era Pin
Omer Mor21-Feb-09 7:49
memberOmer Mor21-Feb-09 7:49 
GeneralRe: We're in the C# 3 era Pin
Simone Busoli21-Feb-09 7:53
memberSimone Busoli21-Feb-09 7:53 
GeneralRe: We're in the C# 3 era Pin
Richard Deeming4-Mar-09 8:51
mveRichard Deeming4-Mar-09 8:51 
AnswerRe: We're in the C# 3 era Pin
Omer Mor5-Mar-09 8:28
memberOmer Mor5-Mar-09 8:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.