泥庭

2011年3月6日

C#と末尾再帰と末尾最適化

Filed under: .NET — タグ: , , — yone64 @ 11:45 AM

実践 F# 関数型プログラミング入門で「末尾再帰」とか「末尾最適化」というものを知りました。

作者様のブログによると、C#には末尾最適化はないそうだ。

よく訓練された C# 使いならばご存じの通り、C# に末尾最適化はない。より正確に言い換えるなら、C# 4.0 コンパイラは ‘tail.’ プリフィックスを付与しない。このことによって、C# プログラミングにおいては、再帰はおよそ避けるべきものとして認識されている。
http://igeta.cocolog-nifty.com/blog/2011/02/tailcall.html

でも、x64版だと末尾最適化が行われるよと聞いたのと、ちょっと気になる書き方をしているので調べてみました。

とりあえず、普通の再帰

class Program
{
    public static void Main(string[] args)
    {
        Console.WriteLine("Result:{0}", Sum(10)); 
    }

    public static long Sum(long seed)
    {
        Console.WriteLine("Frame:{0}", new StackTrace().FrameCount);
        if (seed == 0) return 0;
        return seed + (Sum(seed - 1));
    }
}

FrameCountが増加しているのがわかります。

image

で、次にこれを末尾再帰に書き換えてみます。

class Program
{
    public static void Main(string[] args)
    {
        Console.WriteLine("Result:{0}", Sum(10, 0)); 
    }

    public static long Sum(long seed, long temp)
    {
        Console.WriteLine("Frame:{0}", new StackTrace().FrameCount);
        if (seed == 0) return temp;
        return Sum(seed - 1, seed + temp);
    }
}

で、実行結果。FrameCountは増加していきません。なお、Release & x64ビルドでの実行です。

image

ちなみに、x86やDebugでのビルドだとFrameCountが増加していきます。

image

この結果をみると、x64 & Release ビルドでは末尾最適化が行われているように見えます。

さらにふみこんで、ILをみてみました。

.method public hidebysig static int64 Sum(int64 seed, int64 temp) cil managed
{
    .maxstack 8
    L_0000: ldstr "Frame:{0}"
    L_0005: newobj instance void [mscorlib]System.Diagnostics.StackTrace::.ctor()
    L_000a: callvirt instance int32 [mscorlib]System.Diagnostics.StackTrace::get_FrameCount()
    L_000f: box int32
    L_0014: call void [mscorlib]System.Console::WriteLine(string, object)
    L_0019: ldarg.0 
    L_001a: ldc.i4.0 
    L_001b: conv.i8 
    L_001c: bne.un.s L_0020
    L_001e: ldarg.1 
    L_001f: ret 
    L_0020: ldarg.0 
    L_0021: ldc.i4.1 
    L_0022: conv.i8 
    L_0023: sub 
    L_0024: ldarg.0 
    L_0025: ldarg.1 
    L_0026: add 
    L_0027: call int64 ConsoleApplication1.Program::Sum(int64, int64)
    L_002c: ret 
}

確かに、’tail.’ プリフィックスを付与していないようです。ちなみに、x86でビルドしてもILは変わりませんでした。

ということは、x64のJITコンパイラが実行時に末尾最適化を行っていると言うことなのでしょう。

おまけ

F#で等価なコードを書いてみました。(多分等価)

let rec fact n result =
    if n = 0 then result
            else fact (n-1) (result+n)

printfn "%A" (fact 10 0) 

で、コンパイル後のILがこちら

.method public static int32 fact(int32 n, int32 result) cil managed
{
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { new int32[int32(2)] { int32(1), int32(1) } }
    .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 result
    L_000e: starg.s n
    L_0010: br.s L_0000
}

すでに呼び出しがないですね。ILだとちょっとわかりにくいので、C#に変換してみます。

[CompilationArgumentCounts(new int[] { 1, 1 })]
public static int fact(int n, int result)
{
    while (n != 0)
    {
        result += n;
        n--;
    }
    return result;
}

再帰呼び出しがループに変換されているのがよくわかります。

結論

F#コンパイラは、末尾再帰呼び出しをループに変換する。

C#コンパイラは、末尾再帰呼び出しの変換は行わない。tailプリフィックスも付与しない。

x64のJITコンパイラは実行時に末尾再帰を最適化する。

といったところでしょうか。

広告

WordPress.com で無料サイトやブログを作成.