42

出于好奇，我试图使用 C# 生成尾调用操作码。Fibinacci 是一个简单的方法，所以我的 c# 示例如下所示：

    private static void Main(string[] args)
    {
        Console.WriteLine(Fib(int.MaxValue, 0));
    }

    public static int Fib(int i, int acc)
    {
        if (i == 0)
        {
            return acc;
        }

        return Fib(i - 1, acc + i);
    }

如果我在发行版中构建它并在没有调试的情况下运行它，我不会得到堆栈溢出。在没有优化的情况下调试或运行它，我确实得到了堆栈溢出，这意味着在发布优化时尾调用正在工作（这是我所期望的）。

用于此的 MSIL 如下所示：

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x205e
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

我本来希望看到一个尾部操作码，每个msdn，但它不存在。这让我想知道 JIT 编译器是否负责将它放在那里？我尝试对程序集进行生成（使用ngen install <exe>，导航到 Windows 程序集列表以获取它）并将其加载到 ILSpy 中，但对我来说它看起来相同：

.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x3bfe
    // Code Size 17 (0x11)
    .maxstack 8
    L_0000: ldarg.0 
    L_0001: brtrue.s L_0005
    L_0003: ldarg.1 
    L_0004: ret 
    L_0005: ldarg.0 
    L_0006: ldc.i4.1 
    L_0007: sub 
    L_0008: ldarg.1 
    L_0009: ldarg.0 
    L_000a: add 
    L_000b: call int32 [ConsoleApplication2]ConsoleApplication2.Program::Fib(int32,int32)
    L_0010: ret 
}

我还是没看到。

我知道 F# 可以很好地处理尾调用，所以我想比较 F# 所做的与 C# 所做的。我的 F# 示例如下所示：

let rec fibb i acc =  
    if i = 0 then
        acc
    else 
        fibb (i-1) (acc + i)


Console.WriteLine (fibb 3 0)

为 fib 方法生成的 IL 如下所示：

.method public static int32 fibb(int32 i, int32 acc) cil managed
{
    // Method Start RVA 0x2068
    // Code Size 18 (0x12)
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { int32[](Mono.Cecil.CustomAttributeArgument[]) }
    .maxstack 5
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: brtrue.s L_0006
    L_0004: ldarg.1 
    L_0005: ret 
    L_0006: ldarg.0 
    L_0007: ldc.i4.1 
    L_0008: sub 
    L_0009: ldarg.1 
    L_000a: ldarg.0 
    L_000b: add 
    L_000c: starg.s acc
    L_000e: starg.s i
    L_0010: br.s L_0000
}

根据 ILSpy，这相当于：

[Microsoft.FSharp.Core.CompilationArgumentCounts(Mono.Cecil.CustomAttributeArgument[])]
public static int32 fibb(int32 i, int32 acc)
{
    label1:
    if !(((i != 0))) 
    {
        return acc;
    }
    (i - 1);
    i = acc = (acc + i);;
    goto label1;
}

那么 F# 使用 goto 语句生成尾调用？这不是我所期待的。

我不想在任何地方依赖尾调用，但我只是好奇该操作码到底是在哪里设置的？C# 是如何做到这一点的？

4

3 回答 3

51

C# 编译器不对尾调用优化提供任何保证，因为 C# 程序通常使用循环，因此它们不依赖尾调用优化。因此，在 C# 中，这只是一种可能会发生也可能不会发生的 JIT 优化（您不能依赖它）。

F# 编译器旨在处理使用递归的函数式代码，因此它确实为您提供了有关尾调用的某些保证。这是通过两种方式完成的：

  • 如果您编写一个调用自身的递归函数（如您的fib），编译器会将其转换为在主体中使用循环的函数（这是一个简单的优化，生成的代码比使用尾调用更快）

  • 如果您在更复杂的位置使用递归调用（当使用函数作为参数传递的连续传递样式时），则编译器会生成一条尾调用指令，告诉 JIT 它必须使用尾调用。

以第二种情况为例，编译如下简单的 F# 函数（F# 在 Debug 模式下不这样做，以简化调试，因此您可能需要 Release 模式或添加--tailcalls+）：

let foo a cont = cont (a + 1)

该函数只是调用函数cont，第一个参数加一。在延续传递风格中，您有很长的此类调用序列，因此优化至关重要（如果不处理尾调用，您根本无法使用这种风格）。生成的 IL 代码如下所示：

IL_0000: ldarg.1
IL_0001: ldarg.0
IL_0002: ldc.i4.1
IL_0003: add
IL_0004: tail.                          // Here is the 'tail' opcode!
IL_0006: callvirt instance !1 
  class [FSharp.Core] Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000b: ret
于 2013-04-07T17:01:35.510 回答
28

.Net 中尾调用优化的情况相当复杂。据我所知，是这样的：

  • C# 编译器永远不会发出tail.操作码，它也永远不会自己进行尾调用优化。
  • F# 编译器有时会发出tail.操作码，有时会通过发出非递归的 IL 来自行进行尾调用优化。
  • 如果操作码存在， CLR 将遵守tail.操作码，即使操作码不存在，64 位 CLR 有时也会进行尾调用优化。

因此，在您的情况下，您没有看到tail.C# 编译器生成的 IL 中的操作码，因为它没有这样做。但是该方法是尾调用优化的，因为即使没有操作码，CLR 有时也会这样做。

在 F# 案例中，您观察到 f# 编译器自己进行了优化。

于 2013-04-07T17:15:23.520 回答
10

与 .NET（Roslyn 语言）中执行的所有优化一样，尾调用优化是由抖动而不是编译器执行的工作。其理念是，将工作放在抖动上是有用的，因为任何语言都会从中受益，而编写和调试代码优化器通常很困难的工作只能在每个架构中完成一次。

您必须查看生成的机器代码才能看到它正在完成，Debug + Windows + Disassembly。进一步要求您通过查看使用工具 + 选项、调试、常规、抑制 JIT 优化生成的发布构建代码来执行此操作。

x64 代码如下所示：

        public static int Fib(int i, int acc) {
            if (i == 0) {
00000000  test        ecx,ecx 
00000002  jne         0000000000000008 
                return acc;
00000004  mov         eax,edx 
00000006  jmp         0000000000000011 
            }

            return Fib(i - 1, acc + i);
00000008  lea         eax,[rcx-1] 
0000000b  add         edx,ecx 
0000000d  mov         ecx,eax 
0000000f  jmp         0000000000000000              // <== here!!!
00000011  rep ret

注意标记的指令，跳转而不是调用。这就是工作中的尾调用优化。.NET 中的一个怪癖是 32 位 x86 抖动不执行此优化。只是他们可能永远无法解决的待办事项。这确实要求 F# 编译器编写者不要忽略该问题并发出 Opcodes.Tailcall。您会发现此答案中记录的抖动执行的其他优化。

于 2013-04-07T16:56:06.083 回答