RyuJITのお仕事(1/2)

# TL;DR

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

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

```csharp
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`が飛んできた。

```csharp
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[^2]
* プラットフォームターゲットはx64で固定[^5]
* Releaseビルド[^5]



# 先行する知見

[@acple@github](https://qiita.com/acple@github)さんが、[.NET4.6で末尾再帰するとしぬかもな話](https://qiita.com/acple@github/items/6147b2460c19334362e1)と言うエントリを上げてるので、ご覧頂ければと思います。

また、先日本件をTwitterにてTweetしたところ、ご本人様から[このような](https://twitter.com/acple/status/996036201370005505)リプライを頂いたので、これを参考にしつつ色々とわかったことをユルくまとめようって言うさむしんぐです。

# やってみた試行錯誤

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

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

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



```csharp
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`がやっぱりダメなのか、切り分けるため、冗長だけど以下のようなコードを書いてみた。

```csharp
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[^6]意外の値型を利用した場合は末尾再帰の最適化が行われず、`StackOverflowException`が発生してしまうのではと仮定して、`class`にしてた`Envelope`を`struct`にして挙動を見てみた。

```csharp
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型[^6]意外の値型を利用した末尾再帰は最適化されない。
2. 単純に参照型のメンバにしてもダメ。
3. Primitive型[^6]に関しては参照型のメンバにしても最適化される。
4. Primitive型[^6]を含んだ値型を利用しても最適化されない。



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

[次回](https://qiita.com/NetSeed/items/ff2da14e2254b53278b7)は、末尾再帰の最適化が行われる条件を検証してみようかと思います。

### 余談
これ書いてるウチに、藤井聡太七段になってた。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/9662/b77e6b29-74f3-d081-877a-52772b58cbfe.png)


[^1]: 当然、桁があふれてWraparoundする。ここではStackOverflow起こらない予定度に見て頂ければ。
[^2]: ただ、C#のVersionはあんまり今回関係ないと思う。
[^5]: Ryujitでの挙動なので、この条件は割と必須。
[^6]: `typeof(T).IsPrimitive`が、`true`の型と言うことで一つ。