字典枚举键性能

本文关键字:性能 枚举 字典 | 更新日期: 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
Int2.385 us0.0443 us0.0455 us
枚举2.502 us0.0415 us0.0388 us
均衡器比较器7.701 us0.0916 us0.0765 us
交换机2.072 us0.0271 us0.0253 us
字符串6.765 us0.1316 us0.1293 us