字典枚举键性能
本文关键字:性能 枚举 字典 | 更新日期: 2023-09-27 18:26:01
我担心使用枚举作为键的通用字典。
如下页所述,使用枚举键将分配内存:http://blogs.msdn.com/b/shawnhar/archive/2007/07/02/twin-paths-to-garbage-collector-nirvana.aspx
我已经测试并确认了这种行为,它给我的项目带来了问题。为了可读性,我认为对键使用枚举非常有用,对我来说,最佳解决方案是编写一个实现IDictionary<TKey, TValue>
的类,该类将在内部对键使用整数。原因是我不想更改所有现有的字典,使其使用整数作为键,并进行隐式转换。这将是最好的性能,但它会给我带来很多工作,而且会降低可读性。
因此,我尝试了几种方法,包括使用GetHashCode
(不幸的是,它会分配内存)来构建内部Dictionary<int, TValue>
。
所以,用一个问题来概括它;有人能想到一个解决方案吗?我可以用它来保持Dictionary<SomeEnum, TValue>
的可读性,同时具有Dictionary<int, TValue>
的性能?
非常感谢任何建议。
问题是装箱。这是一种将值类型转换为对象的行为,这可能是不必要的,也可能不是不必要的。
Dictionary
比较密钥的方式本质上是,它将使用EqualComparer<T>.Default
,并调用GetHashCode()
来查找正确的bucket,以及Equals
来比较bucket中是否有任何值等于我们要查找的值。
好处是:.NET框架有很好的优化,避免了"Enum integers"
的装箱。请参见CreateComparer()。在这里,您不太可能看到整数和枚举作为键之间的任何区别。
需要注意的是:这不是一个容易的行为,事实上,如果你深入研究,你会得出结论,这场战斗的四分之一是通过CLR"黑客"实现的。如图所示:
static internal int UnsafeEnumCast<T>(T val) where T : struct
{
// should be return (int) val; but C# does not allow, runtime
// does this magically
// See getILIntrinsicImplementation for how this happens.
throw new InvalidOperationException();
}
如果泛型有Enum约束,甚至可能有很长的UnsafeEnumCast<T>(T val) where T : Enum->Integer
行,这肯定会更容易,但。。。他们没有。
你可能想知道,EnumCast
的getILIntrinsimplementation到底发生了什么?我也想知道。目前还不确定如何检查它。我相信它在运行时被特定的IL代码取代了?!
单声道
现在,回答你的问题:是的,你是对的。Enum
作为Mono上的一个键,在一个紧密的循环中会更慢。据我所见,这是因为Mono在枚举上进行拳击。您可以查看EnumIntEqualityComparer,正如您所看到的,它调用Array.UnsafeMov
,它基本上通过装箱将T
的类型强制转换为整数:(int)(object) instance;
。这是泛型的"经典"限制,对于这个问题没有很好的解决方案。
解决方案1
为您的具体Enum实现EqualityComparer<MyEnum>
。这将避免所有铸造。
public struct MyEnumCOmparer : IEqualityComparer<MyEnum>
{
public bool Equals(MyEnum x, MyEnum y)
{
return x == y;
}
public int GetHashCode(MyEnum obj)
{
// you need to do some thinking here,
return (int)obj;
}
}
然后,你所需要做的就是将其传递给你的Dictionary
:
new Dictionary<MyEnum, int>(new MyEnumComparer());
它很有效,它为您提供了与整数相同的性能,并避免了装箱问题。然而,问题是,这不是通用的,为每个Enum
写这篇文章可能会让人觉得很愚蠢。
解决方案2
编写一个通用的Enum
比较器,并使用一些技巧来避免开箱。我是在这里的帮助下写的,
// todo; check if your TEnum is enum && typeCode == TypeCode.Int
struct FastEnumIntEqualityComparer<TEnum> : IEqualityComparer<TEnum>
where TEnum : struct
{
static class BoxAvoidance
{
static readonly Func<TEnum, int> _wrapper;
public static int ToInt(TEnum enu)
{
return _wrapper(enu);
}
static BoxAvoidance()
{
var p = Expression.Parameter(typeof(TEnum), null);
var c = Expression.ConvertChecked(p, typeof(int));
_wrapper = Expression.Lambda<Func<TEnum, int>>(c, p).Compile();
}
}
public bool Equals(TEnum firstEnum, TEnum secondEnum)
{
return BoxAvoidance.ToInt(firstEnum) ==
BoxAvoidance.ToInt(secondEnum);
}
public int GetHashCode(TEnum firstEnum)
{
return BoxAvoidance.ToInt(firstEnum);
}
}
解决方案3
现在,解决方案#2有一个小问题,因为Expression.Compile()
在iOS上并不那么出名(没有运行时代码生成),而且一些mono版本没有??Expression.Compile
??(不确定)。
您可以编写简单的IL代码来处理枚举转换,并对其进行编译
.assembly extern mscorlib
{
.ver 0:0:0:0
}
.assembly 'enum2int'
{
.hash algorithm 0x00008004
.ver 0:0:0:0
}
.class public auto ansi beforefieldinit EnumInt32ToInt
extends [mscorlib]System.Object
{
.method public hidebysig static int32 Convert<valuetype
.ctor ([mscorlib]System.ValueType) TEnum>(!!TEnum 'value') cil managed
{
.maxstack 8
IL_0000: ldarg.0
IL_000b: ret
}
}
为了将其编译成程序集,您必须调用:
ilasm enum2int.il /dll
,其中enum2int.il是包含il.的文本文件
现在可以引用给定的程序集(enum2int.dll
)并调用静态方法,例如:
struct FastEnumIntEqualityComparer<TEnum> : IEqualityComparer<TEnum>
where TEnum : struct
{
int ToInt(TEnum en)
{
return EnumInt32ToInt.Convert(en);
}
public bool Equals(TEnum firstEnum, TEnum secondEnum)
{
return ToInt(firstEnum) == ToInt(secondEnum);
}
public int GetHashCode(TEnum firstEnum)
{
return ToInt(firstEnum);
}
}
它可能看起来是致命的代码,但它避免了装箱,而且它应该会在Mono
上给您更好的性能。
我不久前遇到了同样的问题,并最终将其合并到我编写的通用枚举扩展和辅助方法库中(它是用C++/CLI(编译的AnyCPU)编写的,因为C#不允许为枚举类型创建类型约束)。它在NuGet和GitHub 上的Apache 2.0许可证下可用
您可以在Dictionary
中实现它,方法是从库中的静态Enums
类型获取IEqualityComparer
:
var equalityComparer = Enums.EqualityComparer<MyEnum>();
var dictionary = new Dictionary<MyEnum, MyValueType>(equalityComparer);
使用类似于已经提供的答案中提到的UnsafeEnumCast
的技术(由于不安全,因此在测试中被覆盖致死),在不装箱的情况下处理这些值。因此,它非常快(因为在这种情况下,这将是替换相等比较器的唯一点)。其中包括一个基准测试应用程序,以及我的构建PC生成的最新结果。
作为字典键的枚举现在具有与int
字典键相同或更好的性能。我使用NUnit:测量
public class EnumSpeedTest
{
const int Iterations = 10_000_000;
[Test]
public void WasteTimeInt()
{
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < Iterations; i++)
dict[i] = i;
long sum = 0;
for (int i = 0; i < Iterations; i++)
sum += dict[i];
Console.WriteLine(sum);
}
enum Enum { Zero = 0, One = 1, Two = 2, Three = 3 }
[Test]
public void WasteTimeEnum()
{
Dictionary<Enum, int> dict = new Dictionary<Enum, int>();
for (int i = 0; i < Iterations; i++)
dict[(Enum)i] = i;
long sum = 0;
for (int i = 0; i < Iterations; i++)
sum += dict[(Enum)i];
Console.WriteLine(sum);
}
}
在.NET 5.0版本中,在我的Ryzen 5 PC上进行这两次测试所花费的时间始终在300毫秒左右,枚举版本在大多数运行中都略快。
在更高的.net版本(针对.NET7进行了测试)中,性能与使用int
作为密钥相同。使用IEqualityComparer
结构作为Dictionary的构造函数参数甚至会使性能变差。作为参考,这里有一些代码显示了一些替代方案和相应的性能。该代码使用BenchmarkDotNet框架。
public enum MyEnum { Zero = 0, One = 1, Two = 2, Three = 3, Four = 4, Five = 5, Six = 6, Seven = 7, Eight = 8, Nine = 9, Ten = 10 }
public class DictionaryBenchmark
{
const int count = 100;
[Benchmark]
public void Int()
{
Dictionary<int, int> dict = new Dictionary<int, int>();
dict[0] = 0;
dict[1] = 1;
dict[2] = 2;
dict[3] = 3;
dict[4] = 4;
dict[5] = 5;
dict[6] = 6;
dict[7] = 7;
dict[8] = 8;
dict[9] = 9;
dict[10] = 10;
for (int i = 0; i < count; i++)
{
long sum = dict[0] +
dict[1] +
dict[2] +
dict[3] +
dict[4] +
dict[5] +
dict[6] +
dict[7] +
dict[8] +
dict[9] +
dict[10];
}
}
[Benchmark]
public void Enum()
{
Dictionary<MyEnum, int> dict = new Dictionary<MyEnum, int>();
dict[MyEnum.Zero] = 0;
dict[MyEnum.One] = 1;
dict[MyEnum.Two] = 2;
dict[MyEnum.Three] = 3;
dict[MyEnum.Four] = 4;
dict[MyEnum.Five] = 5;
dict[MyEnum.Six] = 6;
dict[MyEnum.Seven] = 7;
dict[MyEnum.Eight] = 8;
dict[MyEnum.Nine] = 9;
dict[MyEnum.Ten] = 10;
for (int i = 0; i < count; i++)
{
long sum = dict[MyEnum.Zero] +
dict[MyEnum.One] +
dict[MyEnum.Two] +
dict[MyEnum.Three] +
dict[MyEnum.Four] +
dict[MyEnum.Five] +
dict[MyEnum.Six] +
dict[MyEnum.Seven] +
dict[MyEnum.Eight] +
dict[MyEnum.Nine] +
dict[MyEnum.Ten];
}
}
struct MyEnumComparer : IEqualityComparer<MyEnum>
{
public bool Equals(MyEnum x, MyEnum y)
{
return x == y;
}
public int GetHashCode(MyEnum obj)
{
return (int)obj;
}
}
[Benchmark]
public void EqualityComparer()
{
Dictionary<MyEnum, int> dict = new Dictionary<MyEnum, int>(new MyEnumComparer());
dict[MyEnum.Zero] = 0;
dict[MyEnum.One] = 1;
dict[MyEnum.Two] = 2;
dict[MyEnum.Three] = 3;
dict[MyEnum.Four] = 4;
dict[MyEnum.Five] = 5;
dict[MyEnum.Six] = 6;
dict[MyEnum.Seven] = 7;
dict[MyEnum.Eight] = 8;
dict[MyEnum.Nine] = 9;
dict[MyEnum.Ten] = 10;
for (int i = 0; i < count; i++)
{
long sum = dict[MyEnum.Zero] +
dict[MyEnum.One] +
dict[MyEnum.Two] +
dict[MyEnum.Three] +
dict[MyEnum.Four] +
dict[MyEnum.Five] +
dict[MyEnum.Six] +
dict[MyEnum.Seven] +
dict[MyEnum.Eight] +
dict[MyEnum.Nine] +
dict[MyEnum.Ten];
}
}
[Benchmark]
public void Switch()
{
// dummy code to make benchmark more fair
Dictionary<MyEnum, int> dict = new Dictionary<MyEnum, int>();
dict[MyEnum.Zero] = 0;
dict[MyEnum.One] = 1;
dict[MyEnum.Two] = 2;
dict[MyEnum.Three] = 3;
dict[MyEnum.Four] = 4;
dict[MyEnum.Five] = 5;
dict[MyEnum.Six] = 6;
dict[MyEnum.Seven] = 7;
dict[MyEnum.Eight] = 8;
dict[MyEnum.Nine] = 9;
dict[MyEnum.Ten] = 10;
// end of dummy code
for (int i = 0; i < count; i++)
{
long sum = GetIntFromEnum(MyEnum.Zero) +
GetIntFromEnum(MyEnum.One) +
GetIntFromEnum(MyEnum.Two) +
GetIntFromEnum(MyEnum.Three) +
GetIntFromEnum(MyEnum.Four) +
GetIntFromEnum(MyEnum.Five) +
GetIntFromEnum(MyEnum.Six) +
GetIntFromEnum(MyEnum.Seven) +
GetIntFromEnum(MyEnum.Eight) +
GetIntFromEnum(MyEnum.Nine) +
GetIntFromEnum(MyEnum.Ten);
}
}
private int GetIntFromEnum(MyEnum fromMyEnum)
{
return fromMyEnum switch
{
MyEnum.Zero => 0,
MyEnum.One => 1,
MyEnum.Two => 2,
MyEnum.Three => 3,
MyEnum.Four => 4,
MyEnum.Five => 5,
MyEnum.Six => 6,
MyEnum.Seven => 7,
MyEnum.Eight => 8,
MyEnum.Nine => 9,
MyEnum.Ten => 10,
_ => throw new ArgumentOutOfRangeException(nameof(fromMyEnum), fromMyEnum, null)
};
}
[Benchmark]
public void String()
{
Dictionary<string, int> dict = new Dictionary<string, int>();
dict["Zero"] = 0;
dict["One"] = 1;
dict["Two"] = 2;
dict["Three"] = 3;
dict["Four"] = 4;
dict["Five"] = 5;
dict["Six"] = 6;
dict["Seven"] = 7;
dict["Eight"] = 8;
dict["Nine"] = 9;
dict["Ten"] = 10;
for (int i = 0; i < count; i++)
{
long sum = dict["Zero"] +
dict["One"] +
dict["Two"] +
dict["Three"] +
dict["Four"] +
dict["Five"] +
dict["Six"] +
dict["Seven"] +
dict["Eight"] +
dict["Nine"] +
dict["Ten"];
}
}
}
基准测试结果:
方法 | 平均值 | 错误 | StdDev |
---|---|---|---|
Int | 2.385 us | 0.0443 us | 0.0455 us |
枚举 | 2.502 us | 0.0415 us | 0.0388 us |
均衡器比较器 | 7.701 us | 0.0916 us | 0.0765 us |
交换机 | 2.072 us | 0.0271 us | 0.0253 us |
字符串 | 6.765 us | 0.1316 us | 0.1293 us |