読者です 読者をやめる 読者になる 読者になる

tail. prefix internal returns

.NET

自動 tail. call 化の話 を 64 bit 環境で実験してみました.
Windows XP Professional x64 Edition + .NET Framework 2.0 で実験したところ,以下のコードで stack level はずっと 2 のままになりました.

using System;
using System.Runtime.CompilerServices;
using System.Diagnostics;

static class Program
{
    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int Odd(int i)
    {
        if (i <= 0)
            return 0;

        // Console.WriteLine("Odd:  {0}", i); だと box 化がおきる
        // その場合どうも自動 tail call 化が起きないっぽい (要検証)

        Console.Write("Odd:  ");
        Console.Write(i);

        StackTrace st = new StackTrace();
        Console.Write("\t stack level: ");
        Console.WriteLine(st.FrameCount);

        return Even(i - 1);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int Even(int i)
    {
        if (i <= 0)
            return 0;

        Console.Write("Even: ");
        Console.Write(i);

        StackTrace st = new StackTrace();
        Console.Write("\t stack level: ");
        Console.WriteLine(st.FrameCount);

        return Odd(i - 1);
    }

    public static int OddOrEven(int i)
    {
        if (i % 2 == 0)
            return Even(i);
        else
            return Odd(i);
    }

    static void Main(string[] args)
    {
        Console.WriteLine(OddOrEven(1000000000));
    }
}

ポイント.

  • これは C# コンパイラレベルの最適化ではなく CLR レベルでの最適化である.
  • tail. prefix 無しの自動 tail. call 化発動条件は結構厳しい.
    • 上記プログラムでも明示的にインライン展開を抑制していることに注意.
    • というか tail. prefix があっても結構厳しい気がする.
  • 自動 tail. call 化を前提としてプログラムを書くのは悪.

より詳しく知りたい方は,前回も紹介しましたが,こちらの記事がおすすめです.