字典 枚举 键 性能

17
我对使用枚举作为键的通用字典存在顾虑。正如下面的页面所述,使用枚举键会分配内存: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>的性能?
非常感谢任何建议。

4
这听起来对我来说有点过早优化了。你正在开发什么样的应用程序? - Tim Schmelter
3
我觉得你很难在这里做得比“枚举”更好。它的性能与使用整数相同(默认情况下支持整数)。 - Servy
2
@MagnusAndersson 枚举只是使用整数的语法糖。字典获取键时使用了一定量的内存并不让我感到惊讶。无论何时,你都需要使用一定量的内存来完成任何操作。计算机运行在内存上。你不可能得到比现有更好的结果。如果你确实在应用程序中遇到了可测量的问题,几乎肯定不是因为你选择将 Enum 作为字典键而不是整数。 - Servy
3
@Magnus,请展示一个简单的程序来证明您的观点,即枚举类型的性能表现与整数类型不同。 - Kirk Woll
1
@Magnus,你是如何确定“int分配0内存”的?请展示一下能够证明这一点的代码。 - Kirk Woll
显示剩余15条评论
4个回答

41
问题在于装箱。这是将值类型转换为对象的行为,可能是必要的,也可能是不必要的。 Dictionary比较键的方式实质上是使用EqualComparer<T>.Default,并调用GetHashCode()来查找正确的桶,然后使用Equals比较是否有与我们正在查找的相等的值。
好消息是:.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();
    }

如果泛型有枚举约束,甚至可能会像 UnsafeEnumCast<T>(T val) where T : Enum->Integer 这样的语句一样方便,但是...它们没有。您可能想知道,在EnumCast的getILIntrinsicImplementation中到底发生了什么?我也很好奇。目前还不确定如何检查它。我相信它会在运行时被具体的IL代码替换?!现在,回答您的问题:是的,你说得对。在紧密的循环中,使用Enum作为Mono上的键会更慢。因为就我所看到的而言,Mono对枚举进行了装箱。您可以查看EnumIntEqualityComparer,正如您所看到的,它调用了Array.UnsafeMov,这基本上将类型T转换为整数,通过装箱:(int)(object) instance;。这是泛型的“经典”限制,对于这个问题没有好的解决方案。

解决方案1

为您的具体枚举实现一个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 上提供更好的性能。


我更新了这篇文章。如果mono不支持,你可以编写一个通用类,并使用它,而不是为每个枚举编写类:http://referencesource.microsoft.com/#mscorlib/system/collections/generic/equalitycomparer.cs#0f1674ddefef561e#references - Erti-Chris Eelmaa
我现在没有基准测试能力,但我相信解决方案#2是你可能得到的最接近的。 - Erti-Chris Eelmaa
对解决方案2进行测试会导致从CreateDelegate调用中出现“ArgumentException: method return type is incompatible”的错误。我仍在消化这个比较器中发生的事情,你有什么想法来解决这个问题吗?我使用的枚举类型绝对是整数类型,所以我不知道为什么会出现错误。 - Magnus Andersson
@Erti-ChrisEelmaa 正是这个原因,我点赞的主要部分是正确的。我只是不同意将IEqualityComparer隐式装箱到Dictionary构造函数中。首先将IEqualityComparer结构化并没有带来任何优势,只会增加复杂性并对开发人员隐藏一些东西。为什么开发人员要花时间思考它是否被装箱,以及结果他/她可以... - ipavlu
该死的编辑规则,5分钟计时器接管了:)。 如果您制作大量这些字典怎么办?如果它是一个类,您不能错过它的构造。如果它是一个结构体,您很容易错过它。使事情明确是一种简单的生活方式,特别是当代码必须由其他开发人员阅读并且奢侈的选择只会带来混乱和在重构或大型团队开发期间可能出现问题时。 - ipavlu
显示剩余12条评论

1
我曾经遇到过这个问题,最终将其并入了我编写的通用枚举扩展和帮助方法库中(使用C++/CLI编写(编译为AnyCPU),因为C#不允许为枚举类型创建类型约束)。该库在Apache 2.0许可证下可在NuGetGitHub上获取。
您可以通过从库中的静态Enums类型中获取IEqualityComparer来在Dictionary中实现它:
var equalityComparer = Enums.EqualityComparer<MyEnum>();
var dictionary = new Dictionary<MyEnum, MyValueType>(equalityComparer);

这些值不需要装箱,使用类似于已提供的一个答案中提到的UnsafeEnumCast技术处理(由于它是不安全的,因此在测试中被广泛覆盖)。 因此,它非常快(因为这将是在这种情况下替换相等比较器的唯一要点)。 包括基准应用程序以及从我的构建PC生成的最新结果。

1

枚举作为字典键现在具有与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);
    }
}

这两个测试在我的Ryzen 5 PC上,在.NET 5.0 Release版本中所需的时间始终约为300毫秒,而枚举版本在大多数运行中略快。

0
在较新的 .NET 版本中(已测试过 .NET7),使用 int 作为键与使用 IEqualityComparer 结构体作为字典的构造函数参数相比,性能相同甚至更好。 以下是一些代码示例,展示了一些替代方案及其对应的性能。该代码使用 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"];
        }
    }
}

基准测试结果:

方法 平均值 误差 标准偏差
Int 2.385 微秒 0.0443 微秒 0.0455 微秒
Enum 2.502 微秒 0.0415 微秒 0.0388 微秒
EqualityComparer 7.701 微秒 0.0916 微秒 0.0765 微秒
Switch 2.072 微秒 0.0271 微秒 0.0253 微秒
String 6.765 微秒 0.1316 微秒 0.1293 微秒

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接