Are .Net switch statements hashed or indexed?

Question

Does .Net 4 (or any prior version) perform any sort of optimization on longer switch statements based on strings?

I'm working around a potential performance bottleneck due to some long switch statements looking for matching strings in the cases, and I've always assumed these are searched in linear time (or near linear, i.e. not using an index to quickly find the matching string). But this seems like an obvious area that .Net could optimize, so thought I'd check if this is the case or not.

This is a derivative question from my recent one: http://stackoverflow.com/questions/3365677/indexed-switch-statement-or-equivalent-net-c

Answer 1

Compile the following code.

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

Now use Reflector or ILDASM to examine the IL the C# compiler generates. Keep adding case statements and decompiling and observe the result.

• If the number of case statements is small then the compiler emits a sequential equality comparison.
• If the number of case statements is large then the compiler emits a Dictionary lookup.

I was using the C# 3.0 compiler and I observed that the strategy changes at 7 case statements. I suspect you will see something similiar with C# 4.0 and others.

Update:

I should point that you will see calls to Dictionary.Add in the IL output where it is building up the dictionary for later use. Do not be fooled into thinking this happens everytime. The compiler is actually generating a separate static class and doing an inline static initialization of it. Pay particular attention to the instruction at L_0026. If the class is already initialized then the branch will skip over the Add calls.

    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 "1"
    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 "2"
    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 "3"
    L_004c: ldc.i4.2 
    L_004d: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

Also, notice the dictionary actually contains a map from the string to an integer, but it is not the same integer that the switch was originally compiled from. This integer is used to formulate a separate switch in 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