C#编译器会优化循环内对同一方法的调用吗？

Question

Consider the following code:

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集合中的项都要调用一次？

- Rat Salad

---

如何进行优化？当然，它会为每个项调用！ - Backs

@Backs Test.OptionOne.ToString() 是一个固定的字符串，永远不会改变。可以通过生成一个单一的 const 字符串并与之比较来进行优化，而不是在每个循环中生成一个新的字符串。 - Scott Chamberlain

@Backs - 这并不是真正有帮助的，毕竟这正是发帖者在此质疑的确切命题。你所做的只是断言一个立场，而没有提供任何证据或理性。 - antiduh

它不会优化调用。你必须手动将调用提升出循环。 - InBetween

这样的优化是Jitter的工作，而不是C#编译器的工作。ToString()是一个虚方法，Jitter优化器不会尝试猜测具体要运行的方法是什么。也不是很美观，必须找出是否应用了[Flags]属性。框架使用缓存来分摊相当大的成本。 - Hans Passant

Answer 1

您的问题涉及到循环不变式分析——编译器能否检测到循环中某个表达式的计算不依赖于循环状态，且没有副作用？

有理由期待编译器能够满足这两个条件——编译器可以足够智能地知道在枚举上调用 ToString() 方法永远不会改变，而且在枚举上调用 ToString() 方法没有任何显著的副作用。

也许有原因使得编译器 actively 决定不提升不变式——或许调用该函数比在堆栈上存储额外变量更快。

问题归结为它是否实现了。

我使用 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
    }

以下是我使用ILSpy 2.3.1获得的程序原始IL代码。请注意，在循环中间调用了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

我也很好奇运行时JIT编译器是否会提取不变量，但它似乎并没有。为了使汇编代码更清晰，我将代码更改为以下内容：

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

- antiduh

---

当然，这并不表明JIT编译器是否会将其提升。 - pm100

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的有趣问题和答案可以在这里找到。

[编辑] 根据Scott的评论，我将包括使用Hashset的选项（也是O(1)）：

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

根据btlog的正确观察，示例代码对于重复项将失败。可以通过以下方式规避：

• 在获取数据时直接构建HashSet（避免首先使用列表）
• 使用Distinct获得具有不同值的第二个列表

然而，第二种方法将复杂度提高到O(N)。

- Alexei - check Codidact

---

还有一个没有 .ToHashSet() 的原因是你可以直接使用 new HashSet<string>(testValues)。 （我本来会选择哈希集而不是字典） - Scott Chamberlain

这两种方法都存在一个假设，即原始列表中没有重复项，因为如果有重复项，ToDictionary将抛出异常；或者假设重复项不重要，因为HashSet不能有重复值。 - btlog

构建字典的时间复杂度最好为O(N)，因此对于一个搜索词，复杂度无法降低。实际上，它会增加，内存消耗也会增加。 - Antonín Lejsek