2010-07-29 15 views
42

.Net 4 (veya herhangi bir önceki sürüm), dizeleri temel alarak daha uzun anahtar ifadelerinde herhangi bir optimizasyon gerçekleştirir mi?.Net anahtarı ifadeleri hash veya indeksli mi?

Durumlarda eşleşen dizeleri arayan bazı uzun anahtar deyimleri nedeniyle olası bir performans darboğazının etrafında çalışıyorum ve bunların her zaman doğrusal bir zamanda (ya da doğrusal yakın, yani bir dizini kullanarak değil) arandığını varsaydım. eşleşen dizeyi hızlıca bulabilirsiniz). Fakat bu, Net'in optimize edebileceği bariz bir alan gibi gözüküyor, bu yüzden durumun böyle olup olmadığını kontrol etmeyi düşündüm. indexed switch statement, or equivalent? .net, C#

+0

sen benim cevap gördünüz mü? Dize üzerindeki anahtar ifadelerinin, vaka ifadelerinin sayısı belirli bir eşiğe ulaşırsa, bir 'Sözlük' araması haline getirildiğini özellikle belirttim. –

+0

Brian, yazının bir bölümünü gördün. Bu konuyla ilgili belgelere işaret edebilir misin? Çakışan cevaplar buluyorum. Yardım için teşekkürler. –

+5

Konuyla ilgili resmi belgeleri (ara sıra blog yazısı dışında) bulmakta zorlanacaksınız. Bunun sebebi, bu bir uygulama detayıdır.Bacak işini yapmak için –

cevap

109

aşağıdaki kodu derleyin:

Bu benim son birinden bir türevi sorudur.

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

Şimdi, IL # derleyicisi oluşturur Cı incelemek Reflector veya ILDASM kullanın. Vaka ifadeleri eklemeye devam edin ve derleme yapın ve sonucu gözlemleyin.

  • Kasa ifadelerinin sayısı küçükse, derleyici sıralı bir eşitlik karşılaştırması gönderir.
  • durum açıklamalarının sayısı büyükse
  • sonra derleyici bir Dictionary arama yayar.

C# 3.0 derleyicisini kullanıyordum ve stratejinin 7 vaka ifadesinde değiştiğini gözlemledim. C# 4.0 ve diğerleri ile benzer bir şey göreceğinizden şüpheleniyorum.

Güncelleme:

Ben bunu daha sonra kullanmak üzere sözlüğe inşa ediyor IL çıktı Dictionary.Add çağrıları göreceği işaret etmelidir. Bu her zaman olur düşüncesine aldanmayın. Derleyici aslında ayrı bir statik sınıf üretiyor ve satır içi statik başlatılıyor. L_0026 adresindeki talimatlara özellikle dikkat edin. Sınıf zaten başlatılmışsa, şube Add çağrılarını atlayacaktır.

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) 

Ayrıca, sözlüğün aslında orijinal dizeden tamsayıya kadar bir harita içerdiğini de unutmayın. Bu tam sayı, IL'de ayrı bir anahtar oluşturmak için kullanılır. o VB.NET onun Select yapı için bu aynı optimizasyon sahip görünmüyor değer Ne için

:

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 

Güncelle 2. yeni derleyiciler yerine Sözlük inşaat isabet bir karma üzerinde ComputeStringHash() ve sonra dize karşılaştırma kullanmak gibi

+24

+1. –

+1

Bu optimizasyon hakkında eski bir makaleyi (.Net 1) okuduğumu hatırlıyorum. Ayrıca IsInterned ifadesini kullanarak ve referans karşılaştırma kullanarak bir şey vardır. Ama makaleyi bulamıyorum. – GvS

+1

FYI CSC 4.0, 7 vakada da değişiyor gibi gözüküyor (yine de kesinlikle buna asla güvenmemeliyiz!) –

2

görünüyor.

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

[github.com/dotnet/roslyn](https://github.com/dotnet/roslyn/blob/version-1.1.0/docs /compilers/CSharp/CodeGen%20Differences.md): "Roslyn, bir dize anahtarı ilk kez çalıştırıldığında, tahsisleri ve potansiyel olarak büyük bir cezayı önlemek için sözlükleri kullanmaz. Roslyn, dizeleri karma kodlarla eşleyen özel bir işlev kullanır. sayısal anahtar: Bir anlamda bu, statik sözlükleri kullanan eski tekniklerin kısmi bir çizgisidir. " – amartynov

İlgili konular