42

好奇心から、C# を使用してテール コール オペコードを生成しようとしました。フィビナッチは簡単なので、私の 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 しようとしました (を使用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# コンパイラは、再帰を使用する関数コードを処理するように設計されているため、末尾呼び出しについて一定の保証を提供します。これは、次の 2 つの方法で行われます。

  • 自分自身を呼び出す再帰関数 (あなたの などfib) を書くと、コンパイラはそれを本体でループを使用する関数に変換します (これは単純な最適化であり、生成されたコードは末尾呼び出しを使用するよりも高速です)。

  • より複雑な位置で再帰呼び出しを使用する場合 (関数が引数として渡される継続渡しスタイルを使用する場合)、コンパイラーは末尾呼び出しを使用する必要があることを JIT に伝える末尾呼び出し命令を生成します。

2 番目のケースの例として、次の単純な F# 関数をコンパイルします (F# は、デバッグを簡素化するためにデバッグ モードでこれを実行しないため、リリース モードまたは追加が必要になる場合があります--tailcalls+)。

let foo a cont = cont (a + 1)

この関数contは、最初の引数を 1 だけインクリメントして関数を呼び出すだけです。継続渡しスタイルでは、このような呼び出しの長いシーケンスがあるため、最適化が重要です (末尾呼び出しを処理しないと、このスタイルを使用することはできません)。生成された 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 に答える