使用Generic EnumComparer加速基于枚举的字典
在本文中，我将演示使用枚举作为键的字典中由于装箱（boxing）引起的性能问题，并提供使用轻量级代码生成（DynamicMethod）的解决方案。
引言
在本文中，我将介绍一个非常快速的泛型 EnumComparer 类，它实现了 IEqualityComparer 接口。这个类对于加速以 Enum 作为键的字典非常有用。在我的测试中，它的运行速度大约快了 8 倍。
背景
泛型集合在 .NET 2.0 中引入，并在两个主要方面改进了常规集合：
- 类型安全
- 值类型元素的性能
常规集合将值类型视为 System.Object，这会导致大量的装箱和拆箱操作。泛型集合消除了装箱，提高了性能。
由于 Enum 是值类型，您可能会认为它们也会从中受益，而且大多数情况下您是正确的。但是，当 Enum 被用作泛型 Dictionary 的键时，装箱会卷土重来。
当我第一次得知这个鲜为人知的事实时感到很惊讶。Vojislav Stojkovic 在他的文章：.NUTS: Enum Conundrum 中研究并描述了这一点。我强烈建议您阅读它。
总而言之，他的结论是：Dictionary 需要一个相等性实现来确定键是否相等，并且对于不实现 IEquatable 的类型的默认实现会使用 Object.Equals 和 Object.GetHashCode 的重写。由于 Enum 不实现 IEquatable，因此在比较它们时，它们会被强制转换为 object（装箱）。
但是我们不必使用默认实现：Dictionary 类可以在其构造函数中接受一个 IEqualityComparer 实例。我们所要做的就是为我们的 Enum 提供一个 IEqualityComparer，这样装箱就会消失。这正是 Vojislav 所做的。但是，这个解决方案要求您为打算用作 dictionary 键的每种 enum 类型编写自己的 IEqualityComparer 实现。
如果我们能利用泛型的强大功能编写一个通用的 EnumComparer，让它能够用于各种 Enum，那不是很好吗？那样确实很好，但这并不容易。
初次尝试
让我们从写一些类似这样的东西开始：
// 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;
}
}
正如 Vojislav 所发现的，这将无法正常工作。
或者可以呢？
.NET 2.0 的另一项功能是轻量级的 Reflection.Emit。有了它，我们就可以在运行时生成方法。这很有用，因为它允许我们绕过泛型的限制。在某种程度上，这就像 C++ 类模板特化：我们将在运行时为每个泛型类型生成一个特化方法。这个功能唯一的缺点是您需要用 IL 编写您要生成的代码。关于这个主题（称为 DynamicMethod 或轻量级代码生成/LCG）的良好入门可以 在这里 找到。
那么它如何使用呢？让我们来看看。
第二次尝试
我们将在运行时生成两个方法：一个用于 Equals 实现，另一个用于 GetHashCode 实现。我们生成的实现与我们第一次尝试中的完全相同，只是这次我们可以绕过编译错误，因为它们在运行时并不相关。
那么，废话不多说，代码在这里：
/// <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<DayOfWeek,
/// string>(EnumComparer<DayOfWeek>.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>));
}
}
这个解决方案既快速又通用。但能做得更好吗？
正如读者 Simone Busoli 善意指出的那样，可以。
第三次尝试
LCG 是一种很好的代码生成技术，但 .NET 3.5 和 C# 3 引入了一个新的改进方法：表达式树。基本上，它们是表示表达式的层次结构。要生成代码，您可以先在运行时构建表达式树，然后将其编译为 delegate。由于表达式树由对象组成，因此与在 DynamicMethod 中操作 IL 相比，它更容易构建和维护。关于此的一个良好入门可以在 这里 找到。
那么，我们如何使用表达式树实现我们的 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 版本。
Using the Code
要使用 EnumComparer，只需将其传递给 Dictionary：
var comparer = EnumComparer<DayOfWeek>.Instance;
var dictionary = new Dictionary<DayOfWeek, int>(comparer);
基准测试
没有一些数字，这篇文章就不完整了，对吧？
我测试了 EnumComparer 的两种实现，与手动编写的比较器、默认比较器以及 int 的 Dictionary 进行了比较。我在一个 dictionary 上运行了 1,000,000 次迭代，结果令人鼓舞：
两种泛型 EnumComparer 都几乎和手动编写的比较器一样好！而且表达式树版本不仅更清晰，而且比 LCG 版本更快。
顺便说一句，我很好奇它为什么会更快。我知道表达式树在编译时使用了 LCG。所以我想知道它怎么能生成更快的代码？如果您能找出原因，我很乐意您添加评论。
那么初始构建阶段的代码生成成本如何呢？让我们来看看：
在这里，两者都比手动编写的比较器（简单的类构造）慢得多。所以您应该只在预计会进行大量比较（数万次）时才考虑使用此解决方案。
(注意：我最初写这篇文章时，我的测试表明泛型 EnumComparer 比手动编写的稍快。但是，当我再次进行基准测试时，手动编写的比较器反而更快。我不知道为什么结果会发生变化，但现在附加文件中包含了完整的基准测试代码，您可以自己测试。)
事后思考
Dictionary 的性能问题在我第一次得知时就让我感到惊讶。而且，构建简单的泛型比较器解决方案并非易事，这让我感到一种特殊的瘙痒，我必须去挠。于是我坐下来，敲打键盘，直到一个优雅的解决方案出现。
但是一个新的问题浮现在我的脑海里：这个解决方案应该在什么时候使用？
我的第一个答案是：“可能永远都不会”。原因是它很可能是过早/微优化。正如您应该知道的，优化应该只在您确切知道瓶颈在哪里时才进行。
在我第一次发布这篇文章后，我发现一些实际用例可能会出现：Ayende 在 NHibernate 中 写博客 提到一个实际的性能问题，可以通过此解决方案解决。所以也许它不像我想的那么没用。:-)
发布文章的另一个好结果是 Simon Busoli 关于使用表达式树改进我的解决方案的评论。这让我很高兴，所以我决定更新这篇文章。
总而言之，我希望您阅读这篇文章的乐趣和我写它的乐趣一样大。谁知道呢？您可能会发现它很有用。
示例项目
该解决方案包含 3 个项目：
- 此处显示的示例代码
- 单元测试
- 基准测试
参考文献
- [1] Stojkovic, Vojislav. .NUTS: Enum Conundrum. [在线] http://beardseye.blogspot.com/2007/08/nuts-enum-conundrum.html
历史
- 2009年2月20日：初始帖子
- 2009年3月4日：添加了使用表达式树的改进版本