47 Stimmen

Sind .Net-Switch-Anweisungen gehasht oder indiziert?

Führt .Net 4 (oder eine frühere Version) irgendeine Art von Optimierung für längere Switch-Anweisungen auf der Grundlage von Strings durch?

Ich arbeite um einen potenziellen Leistungsengpass aufgrund einiger langer Switch-Anweisungen auf der Suche nach übereinstimmenden Zeichenfolgen in den Fällen, und ich habe immer angenommen, dass diese in linearer Zeit gesucht werden (oder fast linear, d.h. nicht mit einem Index, um schnell die übereinstimmende Zeichenfolge zu finden). Aber dies scheint ein offensichtlicher Bereich zu sein, den .Net optimieren könnte, also dachte ich, ich würde überprüfen, ob dies der Fall ist oder nicht.

Dies ist eine Abwandlung meiner letzten Frage: indizierte switch-Anweisung oder gleichwertig? .net, C#

119voto

Brian Gideon Punkte 46450

Kompilieren Sie den folgenden Code.

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

Verwenden Sie nun Reflektor o ILDASM um die vom C#-Compiler erzeugte AWL zu untersuchen. Fügen Sie weitere Case-Anweisungen hinzu, dekompilieren Sie und beobachten Sie das Ergebnis.

  • Wenn die Anzahl der Case-Anweisungen gering ist, führt der Compiler einen sequentiellen Gleichheitsvergleich durch.
  • Wenn die Anzahl der Case-Anweisungen groß ist, gibt der Compiler eine Dictionary Nachschlagen.

Ich habe den C# 3.0 Compiler verwendet und festgestellt, dass sich die Strategie bei 7 Case-Anweisungen ändert. Ich vermute, Sie werden etwas ähnliches mit C# 4.0 und anderen sehen.

Aktualisierung:

Ich möchte darauf hinweisen, dass Sie Aufrufe zu Dictionary.Add in der AWL-Ausgabe, wo sie das Wörterbuch für die spätere Verwendung aufbaut. Lassen Sie sich nicht einreden, dass dies jedes Mal geschieht. Der Compiler generiert tatsächlich eine separate statische Klasse und führt eine statische Inline-Initialisierung dieser Klasse durch. Achten Sie besonders auf die Anweisung bei L_0026. Wenn die Klasse bereits initialisiert ist, überspringt die Verzweigung die Add Anrufe.

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)

Beachten Sie auch, dass das Wörterbuch eine Zuordnung von der ursprünglichen Zeichenkette zu einer Ganzzahl enthält. Diese Ganzzahl wird zur Formulierung eines separaten Schalters in AWL verwendet.

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 

Update 2:

Was auch immer es wert ist, VB.NET scheint nicht über die gleiche Optimierung für seine Select konstruieren.

7voto

13xforever Punkte 461

Es sieht so aus, als ob die neueren Compiler die ComputeStringHash() und dann den String-Vergleich bei einem Hash-Treffer anstelle der Wörterbuchkonstruktion.

// [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

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X