Будет ли компилятор C# оптимизировать вызовы одного метода внутри цикла?

Question

Рассмотрим следующий код:

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 
    } 
} 

Будет ли компилятор оптимизировать вызовы Test.OptionOne.ToString() или он будет называть его по каждому пункту в testValues коллекции?

Answer 1

Ваш вопрос является одним из анализа циклов-инвариантов - может ли компилятор обнаружить некоторое выражение в цикле, которое не зависит от состояния цикла для его оценки и не имеет si де-эффекты?

Есть веские основания надеяться, что компилятор сможет удовлетворить оба предложения - компилятор может быть достаточно умным, чтобы знать, что вызов ToString() на перечисление не меняется, когда-либо; и что вызов ToString() на перечисление не имеет ощутимых побочных эффектов.

Могут быть причины, по которым компилятор будет активно решать не поднимать инвариант - возможно, вызывать функцию как-то быстрее, чем хранить дополнительную переменную в стеке.

Вопрос сводится к тому, делает.

Я скомпилировал следующую программу, используя VS2012, нацеленную на .Net 4.6 и скомпилированную с включенными оптимизациями. Оказывается, что компилятор не выбрал водрузить инвариант из цикла:

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 
    } 

Вот сырой IL от программы, которую я получил с помощью ILSpy 2.3.1. Обратите внимание на вызов ToString(), прямо в середине цикла.

.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 

Я также получил любопытно увидеть, если среда выполнения JITer бы водрузить инвариант, но это тоже, кажется, не.Я изменил код к следующему, чтобы сделать уборщика сборки:

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

А затем используется отладчик VS, чтобы получить сборку, соблюдая осторожность, чтобы убедиться, что VS позволило JITer оптимизировать. Он все еще не поднял вызов 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

Нет, но вы можете значительно уменьшить сложность, делая что-то вроде этого:

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 
} 

поиска словаря значения имеет сложность O (1).

Я думаю, что альтернатива HashSet, так как у вас есть только ключи. Интересный вопрос и ответы относительно построения HashSet из списка можно найти here.

[править] После комментария Скотта, я буду включать опцию использования HashSet (также в O (1)):

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

основе btlog «с правильным наблюдения, например, код потерпит неудачу дубликатов , Это может быть обойдено путем:

• сборки Непосредственно HashSet при выборке данных (во избежание список в первой очереди)
• получение второго списка, имеющий различные значения с помощью Distinct

Однако, второй подход raises the complexity to O(N)