.Net switch语句是哈希还是编入索引？

Question

.Net 4(或任何先前版本)是否基于字符串对较长的switch语句执行任何类型的优化？

我正在解决潜在的性能瓶颈,因为一些长的switch语句在这些情况下寻找匹配的字符串,我一直认为这些是在线性时间内搜索的(或接近线性的,即不使用索引来快速找到匹配串).但这似乎是.Net可以优化的一个显而易见的领域,所以我想我会检查是否是这种情况.

这是我最近的一个衍生问题:索引切换语句,或同等的？.net,C#

Answer 1

编译以下代码.

public static int Main(string[] args)
{
    switch (args[0])
    {
        case "x": return 1;
        case "y": return 2;
        case "z": return 3;
    }
    return 0;
}

现在使用Reflector或ILDASM来检查C#编译器生成的IL.继续添加case语句并反编译并观察结果.

• 如果case语句的数量很小,则编译器会发出顺序相等比较.
• 如果case语句的数量很大,则编译器会发出Dictionary查找.

我正在使用C#3.0编译器,我观察到策略在7个案例语句中发生了变化.我怀疑你会看到类似于C#4.0和其他人的东西.

更新:

我应该指出,您将Dictionary.Add在IL输出中看到它正在构建字典以供以后使用.不要误以为每次都会发生这种情况.编译器实际上是生成一个单独的静态类并对其进行内联静态初始化.请特别注意L_0026的说明.如果该类已初始化,则分支将跳过Add调用.

L_0021: ldsfld class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32> <PrivateImplementationDetails>{816396DD-F271-4C12-83D0-CC9C9CD67AD6}::$$method0x6000001-1
L_0026: brtrue.s L_0089
L_0028: ldc.i4.7 
L_0029: newobj instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::.ctor(int32)
L_002e: dup 
L_002f: ldstr "x"
L_0034: ldc.i4.0 
L_0035: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
L_003a: dup 
L_003b: ldstr "y"
L_0040: ldc.i4.1 
L_0041: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
L_0046: dup 
L_0047: ldstr "z"
L_004c: ldc.i4.2 
L_004d: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

另外,请注意字典实际上包含从原始字符串到整数的映射.该整数用于在IL中形成单独的开关.

L_0089: volatile. 
L_008b: ldsfld class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32> <PrivateImplementationDetails>{816396DD-F271-4C12-83D0-CC9C9CD67AD6}::$$method0x6000001-1
L_0090: ldloc.2 
L_0091: ldloca.s CS$0$0002
L_0093: call instance bool [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
L_0098: brfalse.s L_00da
L_009a: ldloc.3 
L_009b: switch (L_00be, L_00c2, L_00c6, L_00ca, L_00ce, L_00d2, L_00d6)
L_00bc: br.s L_00da
L_00be: ldc.i4.1 
L_00bf: stloc.1 
L_00c0: br.s L_00de
L_00c2: ldc.i4.2 
L_00c3: stloc.1 
L_00c4: br.s L_00de
L_00c6: ldc.i4.3 

更新2:

对于它的价值而言,VB.NET似乎没有对其Select构造进行相同的优化.

Answer 2

看起来较新的编译器使用的ComputeStringHash()是散列匹配，然后使用字典进行字符串比较，而不是使用字典构建。

// [19 6 - 19 22]
IL_0037: ldarg.0      // args
IL_0038: ldc.i4.0     
IL_0039: ldelem.ref   
IL_003a: stloc.s      V_5

IL_003c: ldloc.s      V_5
IL_003e: call         unsigned int32 '<PrivateImplementationDetails>'::ComputeStringHash(string)
IL_0043: stloc.s      V_6
IL_0045: ldloc.s      V_6
IL_0047: ldc.i4       -502520314 // 0xe20c2606
IL_004c: bgt.un.s     IL_007b
IL_004e: ldloc.s      V_6
IL_0050: ldc.i4       -536075552 // 0xe00c22e0
IL_0055: beq          IL_00f9
IL_005a: br.s         IL_005c
IL_005c: ldloc.s      V_6
IL_005e: ldc.i4       -519297933 // 0xe10c2473
IL_0063: beq          IL_00e9
IL_0068: br.s         IL_006a
IL_006a: ldloc.s      V_6
IL_006c: ldc.i4       -502520314 // 0xe20c2606
IL_0071: beq          IL_0119
IL_0076: br           IL_014c
IL_007b: ldloc.s      V_6
IL_007d: ldc.i4       -468965076 // 0xe40c292c
IL_0082: bgt.un.s     IL_009d
IL_0084: ldloc.s      V_6
IL_0086: ldc.i4       -485742695 // 0xe30c2799
IL_008b: beq.s        IL_0109
IL_008d: br.s         IL_008f
IL_008f: ldloc.s      V_6
IL_0091: ldc.i4       -468965076 // 0xe40c292c
IL_0096: beq.s        IL_00b6
IL_0098: br           IL_014c
IL_009d: ldloc.s      V_6
IL_009f: ldc.i4       -435409838 // 0xe60c2c52
IL_00a4: beq.s        IL_00d9
IL_00a6: br.s         IL_00a8
IL_00a8: ldloc.s      V_6
IL_00aa: ldc.i4       -418632219 // 0xe70c2de5
IL_00af: beq.s        IL_00c9
IL_00b1: br           IL_014c
IL_00b6: ldloc.s      V_5
IL_00b8: ldstr        "a"
IL_00bd: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_00c2: brtrue.s     IL_0129
IL_00c4: br           IL_014c
IL_00c9: ldloc.s      V_5
IL_00cb: ldstr        "b"
IL_00d0: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_00d5: brtrue.s     IL_012e
IL_00d7: br.s         IL_014c
IL_00d9: ldloc.s      V_5
IL_00db: ldstr        "c"
IL_00e0: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_00e5: brtrue.s     IL_0133
IL_00e7: br.s         IL_014c
IL_00e9: ldloc.s      V_5
IL_00eb: ldstr        "d"
IL_00f0: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_00f5: brtrue.s     IL_0138
IL_00f7: br.s         IL_014c
IL_00f9: ldloc.s      V_5
IL_00fb: ldstr        "e"
IL_0100: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_0105: brtrue.s     IL_013d
IL_0107: br.s         IL_014c
IL_0109: ldloc.s      V_5
IL_010b: ldstr        "f"
IL_0110: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_0115: brtrue.s     IL_0142
IL_0117: br.s         IL_014c
IL_0119: ldloc.s      V_5
IL_011b: ldstr        "g"
IL_0120: call         bool [mscorlib]System.String::op_Equality(string, string)
IL_0125: brtrue.s     IL_0147
IL_0127: br.s         IL_014c

// [21 17 - 21 26]
IL_0129: ldc.i4.0     
IL_012a: stloc.s      V_7
IL_012c: br.s         IL_01ac

// [22 17 - 22 26]
IL_012e: ldc.i4.1     
IL_012f: stloc.s      V_7
IL_0131: br.s         IL_01ac

// [23 17 - 23 26]
IL_0133: ldc.i4.2     
IL_0134: stloc.s      V_7
IL_0136: br.s         IL_01ac

// [24 17 - 24 26]
IL_0138: ldc.i4.3     
IL_0139: stloc.s      V_7
IL_013b: br.s         IL_01ac

// [25 17 - 25 26]
IL_013d: ldc.i4.4     
IL_013e: stloc.s      V_7
IL_0140: br.s         IL_01ac

// [26 17 - 26 26]
IL_0142: ldc.i4.5     
IL_0143: stloc.s      V_7
IL_0145: br.s         IL_01ac

// [27 17 - 27 26]
IL_0147: ldc.i4.6     
IL_0148: stloc.s      V_7
IL_014a: br.s         IL_01ac

// [28 16 - 28 26]
IL_014c: ldc.i4.m1    
IL_014d: stloc.s      V_7
IL_014f: br.s         IL_01ac