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:
- Type safety
- 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 Enum
s 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 Enum
s 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 Enum
s? 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)
{
return (x == y);
}
public int GetHashCode(TEnum obj)
{
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:
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;
public static readonly EnumComparer<TEnum> Instance;
static EnumComparer()
{
getHashCode = generateGetHashCode();
equals = generateEquals();
Instance = new EnumComparer<TEnum>();
}
private EnumComparer()
{
assertTypeIsEnum();
assertUnderlyingTypeIsSupported();
}
public bool Equals(TEnum x, TEnum y)
{
return equals(x, y);
}
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);
}
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);
generator.Emit(OpCodes.Ldarg_1);
generator.Emit(OpCodes.Ceq);
generator.Emit(OpCodes.Ret);
return (Func<TEnum, TEnum, bool>)method.CreateDelegate
(typeof(Func<TEnum, TEnum, bool>));
}
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);
generator.Emit(OpCodes.Stloc_0);
generator.Emit(OpCodes.Ldloca_S, castValue);
generator.Emit(OpCodes.Call, getHashCodeMethod);
generator.Emit(OpCodes.Ret);
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 int
s. I ran 1,000,000 iterations on a dictionary
and the results were promising:
Both generic EnumComparer
s 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:
- The code shown here
- Unit-tests
- Benchmarks
References
History
- 20th February, 2009: Initial post
- 4th March, 2009: Added improved version using Expression Trees