Czy kompilator C# zoptymalizuje wywołania do tej samej metody w pętli?

Question

Rozważmy następujący kod:

enum Test { 
    OptionOne, 
    OptionTwo 
} 

List<string> testValues = new List<string> { ... } // A huge collection of strings 

foreach(var val in testValues) 
{ 
    if(val == Test.OptionOne.ToString()) // **Here** 
    { 
     // Do something 
    } 
} 

Czy kompilator optymalizacji połączeń do Test.OptionOne.ToString() czy będzie to nazwać dla każdego elementu w kolekcji testValues?

Answer 1

Twoje pytanie jest jedną z analizy niezmienników pętli - czy kompilator może wykryć pewne wyrażenie w pętli, która nie zależy od stanu pętli do jej oceny i nie ma efekty?

Istnieje dobry powód, by mieć nadzieję, że kompilator może zadowolić obie propozycje - kompilator może być wystarczająco inteligentny, aby wiedzieć, że wywoływanie ToString() na wyliczeniu nie zmienia się nigdy; i że wywołanie ToString() na wyliczeniu nie ma żadnych znaczących skutków ubocznych.

Może być powód, dla którego kompilator aktywnie zdecydowałby się nie podnosić niezmiennika - być może wywołanie funkcji jest w jakiś sposób szybsze niż przechowywanie dodatkowej zmiennej na stosie.

Pytanie sprowadza się do tego, czy numer czy nie jest.

Przygotowałem następujący program, używając VS2012 targetowania .Net 4.6 i skompilowałem z włączonymi optymalizacjami. Wydaje się, że kompilator nie wybrał podnosić niezmiennego z pętli:

public static void Main() 
    { 
     for(int i = 0; i < 10; i++) 
     { 
      Console.Out.WriteLine(i); 
      Console.Out.WriteLine(Test.Option1.ToString()); 
     } 
    } 

    public enum Test 
    { 
     Option1, 
     Option2, 
     Option3 
    } 

Oto surowy IL z programu, że uzyskane za pomocą ILSpy 2.3.1. Zwróć uwagę na numer ToString(), w samym środku pętli.

.method public hidebysig static 
    void Main() cil managed 
{ 
    .custom instance void [mscorlib]System.STAThreadAttribute::.ctor() = (
     01 00 00 00 
    ) 
    // Method begins at RVA 0x2050 
    // Code size 46 (0x2e) 
    .maxstack 2 
    .entrypoint 
    .locals init (
     [0] int32 i 
    ) 

    IL_0000: ldc.i4.0 
    IL_0001: stloc.0 
    IL_0002: br.s IL_0028 
    // loop start (head: IL_0028) 
     IL_0004: call class [mscorlib]System.IO.TextWriter [mscorlib]System.Console::get_Out() 
     IL_0009: ldloc.0 
     IL_000a: callvirt instance void [mscorlib]System.IO.TextWriter::WriteLine(int32) 
     IL_000f: call class [mscorlib]System.IO.TextWriter [mscorlib]System.Console::get_Out() 
     IL_0014: ldc.i4.0 
     IL_0015: box TestProject.Program/Test 
---> IL_001a: callvirt instance string [mscorlib]System.Object::ToString() 
     IL_001f: callvirt instance void [mscorlib]System.IO.TextWriter::WriteLine(string) 
     IL_0024: ldloc.0 
     IL_0025: ldc.i4.1 
     IL_0026: add 
     IL_0027: stloc.0 

     IL_0028: ldloc.0 
     IL_0029: ldc.i4.s 10 
     IL_002b: blt.s IL_0004 
    // end loop 

    IL_002d: ret 
} // end of method Program::Main 

Dostałam też ciekaw czy JITer wykonawcze będą podnosić niezmienna, ale to też nie wydaje się.Zmieniłem kod do następującego, aby czystsze montaż:

public static void Main() 
    { 
     TextWriter cons = Console.Out; 
     for(int i = 0; i < 10; i++) 
     { 
      cons.WriteLine(i); 
      cons.WriteLine(Test.Option1.ToString()); 
     } 
    } 

a następnie wykorzystywane debugger VS, aby uzyskać zespół, uważając, aby upewnić się, VS pozwoliło JITer zoptymalizować. Nadal nie zadzwonił do ToString():

  TextWriter cons = Console.Out; 
00000000 push  rdi 
00000001 push  rsi 
00000002 sub   rsp,28h 
00000006 call  0000000050D76460 
0000000b mov   rsi,rax 
      for(int i = 0; i < 10; i++) 
0000000e xor   edi,edi 
      { 
       cons.WriteLine(i); 
00000010 mov   rcx,rsi 
00000013 mov   edx,edi 
00000015 mov   rax,qword ptr [rsi] 
00000018 mov   rax,qword ptr [rax+60h] 
0000001c call  qword ptr [rax+28h] 
       cons.WriteLine(Test.Option1.ToString()); 
0000001f mov   rcx,7FE90116770h 
00000029 call  000000005F6302D0 
0000002e mov   rcx,rsi 
00000031 xor   ecx,ecx 
00000033 mov   dword ptr [rax+8],ecx 
00000036 mov   rcx,rax 
00000039 mov   rax,qword ptr [rax] 
0000003c mov   rax,qword ptr [rax+40h] 
00000040 call  qword ptr [rax]   <---- call System.Enum.ToString() 
00000042 mov   rdx,rax 
00000045 mov   rcx,rsi 
00000048 mov   rax,qword ptr [rsi] 
0000004b mov   rax,qword ptr [rax+68h] 
0000004f call  qword ptr [rax+20h] 
      for(int i = 0; i < 10; i++) 
00000052 inc   edi 
00000054 cmp   edi,0Ah 
00000057 jl   0000000000000010 
00000059 add   rsp,28h 
      } 
     } 

Answer 2

Nie, ale można znacznie zmniejszyć złożoność robiąc coś takiego:

using System.Linq; 

var testValues = new List<string> { ... }; // A huge collection of strings 
var testDict = testValue.ToDictionary(elem => elem, elem => true); 

var needle = Test.OptionOne.ToString(); 
if (testDict.ContainsKey(needle)) 
{ 
    // do something 
} 

wartość słownik odzyskiwanie ma złożoność O (1).

Myślę, że alternatywą jest HashSet, ponieważ masz tylko klucze. Ciekawe pytanie i odpowiedzi dotyczące budowania HashSet z listy można znaleźć here.

[edytuj] następujący komentarz Scotta, będę to możliwość korzystania Hashset (również w czasie O (1)):

var testHash = new HashSet<string>(testValues); 
if (testHash.Contains(needle)) 
{ 
    // do something 
} 

podstawie btlog „s poprawne obserwacyjnych, przykładowy kod zawiedzie duplikatów . Można to obejść, albo:

• zbudować bezpośrednio ze HashSet podczas pobierania danych (unikać listę w pierwszej kolejności)
• otrzymania drugiej listy mające różne wartości za pomocą Distinct

Jednak drugie podejście: raises the complexity to O(N)