在 switch 与字典中的 Func 值，哪个更快，为什么? [英] In a switch vs dictionary for a value of Func, which is faster and why?

问题描述

假设有以下代码:

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"被扩展为包含更多键.为什么会这样?

By iterating over both methods and comparing, I am getting that the dictionary is slightly faster, even when "a", "b", "c", "d" is expanded to include more keys. Why is this so?

这与圈复杂度有关吗?是因为jitter只将字典中的return语句编译为本机代码一次吗?是不是因为字典的查找是O(1)，可能不是这样对于 switch 语句?(这些只是猜测)

Does this have to do with cyclomatic complexity? Is is because the jitter compiles the return statements in the dictionary to native code only once? Is it because the lookup of the dictionary is O(1), which may not be the case for a switch statement? (These are just guesses)

推荐答案

简而言之，switch语句是线性执行的，而字典是对数执行的.

The short answer is that the switch statement executes linearly, while the dictionary executes logarithmically.

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

At the IL level, a small switch statement is usually implemented as a series of if-elseif statements comparing equality of the switched variable and each case. So, this statement will execute in a time linearly proportional to the number of valid options for myVar; the cases will be compared in the order they appear, and the worst-case scenario is that all the comparisons are tried and either the last one matches or none do. So, with 32 options, the worst case is that it's none of them, and the code will have made 32 comparisons to determine this.

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

A Dictionary, on the other hand, uses an index-optimized collection to store values. In .NET, a Dictionary is based on a Hashtable, which has effectively constant access time (the disadvantage being extremely poor space efficiency). Other options commonly used for "mapping" collections like Dictionaries include balanced tree structures like red-black trees, which provide logarithmic access (and linear space efficiency). Any of these will allow the code to find the key corresponding to the proper "case" in the collection (or determine it does not exist) much faster than a switch statement can do the same.

编辑:其他答案和评论者已经谈到了这一点，所以为了完整起见，我也会这样做.正如我最初推断的那样，Microsoft 编译器 not 总是编译到 if/elseif 的开关.它通常在少量案例和/或稀疏"案例(非增量值，如 1、200、4000)的情况下这样做.对于较大的相邻案例集，编译器将使用 CIL 语句将开关转换为跳转表".对于大量稀疏情况，编译器可以实现二进制搜索以缩小范围，然后遍历"少量稀疏情况或为相邻情况实现跳转表.

EDIT: Other answers and commenters have touched on this, so in the interest of completeness I will as well. The Microsoft compiler does not always compile a switch to an if/elseif as I inferred originally. It typically does so with small numbers of cases, and/or with "sparse" cases (non-incremental values, like 1, 200, 4000). With larger sets of adjacent cases, the compiler will convert the switch into a "jump table" using a CIL statement. With large sets of sparse cases, the compiler can implement a binary search to narrow the field, and then "fall through" a small number of sparse cases or implement a jump table for adjacent cases.

但是，编译器通常会选择性能和空间效率最佳折衷的实现，因此它只会在大量密集的情况下使用跳转表.这是因为跳转表在内存中需要一个与其必须覆盖的案例范围相同的空间，这对于稀疏案例来说在内存方面是非常低效的.通过在源代码中使用 Dictionary，您基本上可以强制编译器使用；它会按照你的方式去做，而不是为了提高内存效率而牺牲性能.

However, the compiler will typically choose the implementation that is the best compromise of performance and space efficiency, so it will only use a jump table for a large number of densely-packed cases. This is because a jump table requires a space in memory on the order of the range of cases it must cover, which for sparse cases is terribly inefficient memory-wise. By using a Dictionary in source code, you basically force the compiler's hand; it will do it your way, instead of compromising on performance to gain memory efficiency.

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

So, I would expect most cases in which either a switch statement or a Dictionary could be used in source to perform better when using a Dictionary. Large numbers of cases in switch statements are to be avoided anyway, as they are less maintainable.

这篇关于在 switch 与字典中的 Func 值，哪个更快，为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！