RyuJITのお仕事(1/2)

TL;DR

RYUJitが、末尾再帰の最適化をどのように行うのか行わないのか調べてみた。

下記のようなコードはWraparoundして結果は正しくないけど。とりあえず動く。¹

static long Factorial(long current, long accum)
{
    if (current == 0) return accum;
    return Factorial(current - 1, accum * current);
}


static void Main()
{
	var ret = Factorial(1_000_000, 1);
	Console.WriteLine(ret);
}

で、これを桁あふれ対策で下記のように書き換えたらStackOverflowExceptionが飛んできた。

static void Main()
{
    var ret = Factorial(1_000_000, 1);
    Console.WriteLine(ret);
}

static BigInteger Factorial(BigInteger current, BigInteger accum)
{

    if (current == 0) return accum;
    return Factorial(current - 1, accum * current);
}

ので、その条件とどーすれば回避できるかユルくまとめていこうかと思いますので、お付き合い頂ければ幸い。

実行環境

は、以下の通り

• .NET Core 2.0
• C# 7.3²
• プラットフォームターゲットはx64で固定³
• Releaseビルド³

先行する知見

@acple@githubさんが、.NET4.6で末尾再帰するとしぬかもな話と言うエントリを上げてるので、ご覧頂ければと思います。

また、先日本件をTwitterにてTweetしたところ、ご本人様からこのようなリプライを頂いたので、これを参考にしつつ色々とわかったことをユルくまとめようって言うさむしんぐです。

やってみた試行錯誤

色々と試行錯誤してみたのは以下の通り

BigIntegerをクラスメンバにしてみる(失敗)

先のやりとりで、クラスやインターフェース使えばうまく行く的なアドバイスを頂いたので、以下のように書き換えてみた。

public class Envelope
{
    public BigInteger Integer { get; set; }

    public Envelope(BigInteger integer)
    {
        Integer = integer;
    }
}

class Program
{
    static void Main()
    {
        var ret = Factorial(new Envelope(100_000), new Envelope(1));
        Console.WriteLine(ret.Integer);
    }

    static Envelope Factorial(Envelope current, Envelope accum)
    {
        if (current.Integer == 0) return accum;
        return Factorial(new Envelope(current.Integer - 1), new Envelope(accum.Integer * current.Integer));
    }
}

メンバにしてしまえばうまく行くかと思ったけど。。。結果はあえなくProcess is terminating due to

StackOverflowException.がDumpされて終了。どーもこー言うことじゃないらしい。

Integerをlongにしてみる(動く)

なので、次に、そもそも、Envelopeがダメなのか、それともメンバのBigIntegerがやっぱりダメなのか、切り分けるため、冗長だけど以下のようなコードを書いてみた。

public class Envelope
{
    public long Integer { get; set; }

    public Envelope(long integer)
    {
        Integer = integer;
    }
}

class Program
{
    static void Main()
    {
        var ret = Factorial(new Envelope(100_000), new Envelope(1));
        Console.WriteLine(ret.Integer);
    }

    static Envelope Factorial(Envelope current, Envelope accum)
    {
        if (current.Integer == 0) return accum;
        return Factorial(new Envelope(current.Integer - 1), new Envelope(accum.Integer * current.Integer));
    }
}

これは、結果は正しくないけど、StackOverflowExceptionが飛んでくることもなく、普通に動いた。

このことから、Envelopeが問題ではなく、メンバのBigIntegerがどーも悪さしてるかなぁって仮定した。

Envelopeをstructにしてみる(予想通りこける)

で、上記の結果と、頂いたアドバイス、先行する知見から、Primitive⁴意外の値型を利用した場合は末尾再帰の最適化が行われず、StackOverflowExceptionが発生してしまうのではと仮定して、classにしてたEnvelopeをstructにして挙動を見てみた。

public class Envelope
{
    public long Integer { get; set; }

    public Envelope(long integer)
    {
        Integer = integer;
    }
}

class Program
{
    static void Main()
    {
        var ret = Factorial(new Envelope(100_000), new Envelope(1));
        Console.WriteLine(ret.Integer);
    }

    static Envelope Factorial(Envelope current, Envelope accum)
    {
        if (current.Integer == 0) return accum;
        return Factorial(new Envelope(current.Integer - 1), new Envelope(accum.Integer * current.Integer));
    }
}

結果は、予想通りStackOverflowExceptionでこけた。

今回のまとめ

てことで、今回わかったことは以下の通り。

1. Primitive型⁴意外の値型を利用した末尾再帰は最適化されない。
2. 単純に参照型のメンバにしてもダメ。
3. Primitive型⁴に関しては参照型のメンバにしても最適化される。
4. Primitive型⁴を含んだ値型を利用しても最適化されない。

大体、こんな感じじゃないかと思います。

次回は、末尾再帰の最適化が行われる条件を検証してみようかと思います。

余談

これ書いてるウチに、藤井聡太七段になってた。

1. 当然、桁があふれてWraparoundする。ここではStackOverflow起こらない予定度に見て頂ければ。 ↩

2. ただ、C#のVersionはあんまり今回関係ないと思う。 ↩

3. Ryujitでの挙動なので、この条件は割と必須。 ↩ ↩²

4. typeof(T).IsPrimitiveが、trueの型と言うことで一つ。 ↩ ↩² ↩³ ↩⁴