2010-07-29 12 views
42

Does .Net 4 (o qualsiasi versione precedente) esegue qualsiasi tipo di ottimizzazione su istruzioni switch più lunghe basate su stringhe?Le istruzioni dello switch .Net sono state cancellate o indicizzate?

Sto lavorando a un potenziale collo di bottiglia delle prestazioni a causa di alcune istruzioni di switch lunghe alla ricerca di stringhe corrispondenti nei casi e ho sempre pensato che queste siano state cercate in un tempo lineare (o quasi lineare, cioè non usando un indice per trova rapidamente la stringa corrispondente). Ma questo sembra un'area ovvia che .Net potrebbe ottimizzare, quindi ho pensato di verificare se questo è il caso o meno.

Questa è una domanda derivata dalla mia recente: indexed switch statement, or equivalent? .net, C#

+0

Hai visto la mia risposta? Ho specificamente menzionato che le istruzioni switch sulla stringa sono ottimizzate in una ricerca 'Dictionary' se il numero di istruzioni caso raggiunge una certa soglia. –

+0

Brian, hai appena visto quella parte del tuo post. Puoi indicarmi la documentazione su questo? Sto trovando risposte contrastanti. Grazie per l'aiuto. –

+5

Avrai difficoltà a trovare documentazione ufficiale (al di fuori del blog post occasionale) riguardante l'argomento. Il motivo è perché questo è un dettaglio di implementazione. –

risposta

109

compilare il seguente codice.

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

Ora usano Reflector o ILDASM per esaminare l'IL il compilatore C# genera. Continuate ad aggiungere dichiarazioni di caso e decompilare e osservare il risultato.

  • Se il numero di istruzioni caso è piccolo, il compilatore emette un confronto di uguaglianza sequenziale.
  • Se il numero di istruzioni caso è elevato, il compilatore emette una ricerca Dictionary.

Stavo usando il compilatore C# 3.0 e ho osservato che la strategia cambia in 7 case statement. Sospetto che vedrai qualcosa di simile a C# 4.0 e altri.

Aggiornamento:

Tengo a precisare che si vedrà chiamate al Dictionary.Add nell'output IL, dove sta costruendo il dizionario per un uso successivo. Non fatevi ingannare nel pensare che questo accada ogni volta. Il compilatore sta effettivamente generando una classe statica separata e sta eseguendo un'inizializzazione statica incorporata. Prestare particolare attenzione alle istruzioni su L_0026. Se la classe è già inizializzata, il ramo salterà sulle chiamate 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) 

Inoltre, si noti che il dizionario contiene effettivamente una mappa dalla stringa originale a un numero intero. Questo intero viene utilizzato per formulare un interruttore separato 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 

Aggiornamento 2:

Per quello che vale la pena di VB.NET non sembra avere la stessa ottimizzazione per la sua Select costrutto.

+24

+1 per fare il lavoro alle gambe. –

+1

Ricordo di aver letto un vecchio articolo (.Net 1) su questa ottimizzazione. Ha anche qualcosa da fare usando l'istruzione IsInterned e usando il confronto di riferimento. Ma non riesco a trovare l'articolo. – GvS

+1

FYI CSC 4.0 sembra passare anche a 7 casi (anche se ovviamente non ci si dovrebbe mai fidare di questo!) –

2

Sembra che i nuovi compilatori utilizzino lo ComputeStringHash() e quindi il confronto tra stringhe su un riscontro hash anziché sulla costruzione del dizionario.

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

Da [github.com/dotnet/roslyn](https://github.com/dotnet/roslyn/blob/version-1.1.0/docs /compilers/CSharp/CodeGen%20Differences.md): "Roslyn non utilizza i dizionari per evitare allocazioni e una penalità potenzialmente enorme quando un interruttore di stringa viene eseguito per la prima volta. Roslyn utilizza una funzione privata che associa le stringhe ai codici hash e un interruttore numerico In un certo senso si tratta di una parziale integrazione della precedente tecnologia che utilizzava dizionari statici. " – amartynov

Problemi correlati