在一个开关vs字典中的Func值,这更快,为什么？

Question

假设有以下代码:

private static int DoSwitch(string arg)
{
    switch (arg)
    {
        case "a": return 0;
        case "b": return 1;
        case "c": return 2;
        case "d": return 3;
    }
    return -1;
}

private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
    {
        {"a", () => 0 },
        {"b", () => 1 },
        {"c", () => 2 },
        {"d", () => 3 },
    };

private static int DoDictionary(string arg)
{
    return dict[arg]();
}

通过迭代这两种方法并进行比较,即使"a","b","c","d"扩展为包含更多键,我也会得到字典稍快一些.为什么会这样？

这与圈复杂度有关吗？是因为抖动只将字典中的return语句编译为本机代码一次？是因为字典的查找是O(1),这可能不是switch语句的情况？(这些只是猜测)

Answer 1

简短的回答是switch语句线性执行,而字典以对数方式执行.

在IL级别,一个小的switch语句通常被实现为一系列if-elseif语句,比较切换变量和每种情况的相等性.因此,此语句将在与myVar的有效选项数成线性比例的时间内执行; 这些案例将按照它们出现的顺序进行比较,最坏的情况是所有的比较都经过了尝试,最后一个比较或者没有比较.因此,有32个选项,最糟糕的情况是它们都不是,代码将进行32次比较来确定这一点.

另一方面,字典使用索引优化的集合来存储值.在.NET中,Dictionary基于Hashtable,它具有有效的持续访问时间(缺点是空间效率极差).通常用于"映射"集合(如字典)的其他选项包括平衡树结构,如红黑树,它们提供对数访问(和线性空间效率).这些中的任何一个都允许代码找到与集合中正确的"case"相对应的密钥(或确定它不存在),这比switch语句可以做得更快.

编辑:其他答案和评论者已经触及了这一点,所以为了完整性,我也会这样做.微软编译器并不能总是编译开关的,如果/ elseif的,因为我原来的推断.它通常使用少量案例和/或"稀疏"案例(非增量值,如1,200,4000).对于较大的相邻情况集,编译器将使用CIL语句将开关转换为"跳转表".对于大量稀疏情况,编译器可以实现二进制搜索以缩小字段,然后"通过"少量稀疏情况或实现相邻情况的跳转表.

但是,编译器通常会选择性能和空间效率最佳折衷的实现,因此它只会对大量密集包装的情况使用跳转表.这是因为跳转表需要在内存空间中按照它必须覆盖的情况范围的顺序,这对于稀疏情况而言在内存方面是非常低效的.通过在源代码中使用Dictionary,你基本上强制编译器的手; 它会以你的方式做到,而不是在性能上妥协以获得内存效率.

所以,我希望大多数情况下可以在源代码中使用switch语句或Dictionary来使用Dictionary时表现更好.无论如何,要避免使用switch语句中的大量案例,因为它们的可维护性较差.

Answer 2

这是微观基准可能误导的一个很好的例子.C#编译器根据交换机/机箱的大小生成不同的IL.所以切换这样的字符串

switch (text) 
{
     case "a": Console.WriteLine("A"); break;
     case "b": Console.WriteLine("B"); break;
     case "c": Console.WriteLine("C"); break;
     case "d": Console.WriteLine("D"); break;
     default: Console.WriteLine("def"); break;
}

产生IL,对每种情况基本上做以下事情:

L_0009: ldloc.1 
L_000a: ldstr "a"
L_000f: call bool [mscorlib]System.String::op_Equality(string, string)
L_0014: brtrue.s L_003f

然后

L_003f: ldstr "A"
L_0044: call void [mscorlib]System.Console::WriteLine(string)
L_0049: ret 

也就是说,这是一系列的比较.所以运行时间是线性的.

但是,添加其他情况(例如,包括来自az的所有字母)会将生成的IL更改为以下内容:

L_0020: ldstr "a"
L_0025: ldc.i4.0 
L_0026: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

和

L_0176: ldloc.1 
L_0177: ldloca.s CS$0$0001
L_0179: call instance bool [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
L_017e: brfalse L_0314

最后

L_01f6: ldstr "A"
L_01fb: call void [mscorlib]System.Console::WriteLine(string)
L_0200: ret 

即它现在使用字典而不是一系列字符串比较,从而获得字典的性能.

换句话说,为这些生成的IL代码是不同的,这仅仅是IL级别.JIT编译器可以进一步优化.

TL; DR:因此,故事的士气是查看真实数据和配置文件,而不是尝试基于微基准进行优化.

Answer 3

与涉及编译器代码生成决策的许多问题一样，答案是“视情况而定”。

在许多情况下，构建您自己的哈希表可能会比编译器生成的代码运行得更快，因为编译器有其他成本指标，它试图平衡您没有的成本指标：主要是内存消耗。

哈希表将比少量 if-then-else IL 指令使用更多的内存。如果编译器为程序中的每个 switch 语句生成一个哈希表，那么内存使用量将会激增。

随着 switch 语句中 case 块数量的增加，您可能会看到编译器生成不同的代码。随着情况的增多，编译器更有理由放弃小而简单的 if-then-else 模式，转而采用更快但更丰富的替代方案。

我不知道 C# 或 JIT 编译器是否执行这种特定的优化，但当 case 选择器很多且大多是顺序的时，switch 语句的常见编译器技巧是计算跳转向量。这需要更多的内存（以编译器生成的嵌入代码流中的跳转表的形式），但执行时间恒定。减去 arg - "a"，使用结果作为跳转表的索引以跳转到适当的 case 块。繁荣，完成，无论是 20 个还是 2000 个案例。

当开关选择器类型是 char 或 int 或 enum并且case 选择器的值大多是连续的（“密集”）时，编译器更有可能切换到跳转表模式，因为可以轻松减去这些类型以创建偏移量或指数。字符串选择器有点难。

字符串选择器由 C# 编译器“驻留”，这意味着编译器将字符串选择器值添加到唯一字符串的内部池中。驻留字符串的地址或标记可以用作其标识，从而在比较驻留字符串的标识/字节相等性时允许进行类似 int 的优化。有了足够的大小写选择器，C# 编译器将生成 IL 代码，查找 arg 字符串的 intern 等效项（哈希表查找），然后将 interned 标记与预先计算的大小写选择器标记进行比较（或跳转表）。

如果您可以诱使编译器在 char/int/enum 选择器情况下生成跳转表代码，那么这可以比使用您自己的哈希表执行得更快。

对于字符串选择器的情况，IL 代码仍然必须执行哈希查找，因此与使用您自己的哈希表相比的任何性能差异都可能是无意义的。

不过，一般来说，在编写应用程序代码时，您不应该过多关注这些编译器的细微差别。Switch 语句通常比函数指针的哈希表更容易阅读和理解。如果 switch 语句足够大，足以将编译器推入跳转表模式，那么它们通常太大而无法人类阅读。

如果您发现 switch 语句位于代码的性能热点中，并且您已经使用分析器测量了它对性能的影响，那么更改代码以使用您自己的字典是性能增益的合理权衡。

从一开始就编写代码以使用哈希表，而没有性能测量来证明这种选择的合理性，这是过度设计，将导致代码深不可测，并带来不必要的更高维护成本。把事情简单化。