TL;DR

前回　の続きをやっていきましょうってコトで一つ。
何やってるかはこの辺見て頂ければ。

やってみた試行錯誤 Part II

前回の結果を基に、もしかしたら再帰関数内でPrimitive型¹意外の型に対して何かしらの操作をしたらダメなんじゃないかなと仮定した。

無限ループ

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

        public BigInteger Integer { get; set; }
    }

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

        private static Envelope Factorial(Envelope current, Envelope accum)
        {
            return Factorial(current, accum);
        }
    }

操作しようがないので、そのまま再帰させてるだけだから当然無限ループに陥る。けど少なくともStackOverflowExceptionが発生することはなかった。

操作の分離

ならば、操作を分離すればうまく行くんじゃなかろうかと推測して、下記のように書いた。

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

    public BigInteger Integer { get; }
}

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

    private static bool Equal(Envelope x, int y) => x.Integer == y;
    private static Envelope Sub(Envelope x, int y) => new Envelope(x.Integer - y);
    private static Envelope Mul(Envelope x, Envelope y) => new Envelope(x.Integer * y.Integer);

    private static Envelope Factorial(Envelope current, Envelope accum)
    {
        if (Equal(current, 0)) return current;
        return Factorial(Sub(current, 1), Mul(current, accum));
    }
}

これでイケると思ったけど、あえなくProcess is terminating due to StackOverflowException.吐いて死亡。。。

NoInlining

けれどここで、Equal、Sub、Mulてば、十分に単純だからJit stageでInliningされてるんじゃね?ってコトと、そもそも末尾再帰の最適化がJit stageで行われているなら、結局同一関数内で、やっちゃまずいと考えている操作を行ってることになるから、Inliningを抑止してみたらどーなるのか検証してみた。

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

    public BigInteger Integer { get; }
}

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

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static bool Equal(Envelope x, int y) => x.Integer == y;

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static Envelope Sub(Envelope x, int y) => new Envelope(x.Integer - y);

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static Envelope Mul(Envelope x, Envelope y) => new Envelope(x.Integer * y.Integer);

    private static Envelope Factorial(Envelope current, Envelope accum)
    {
        if (Equal(current, 0)) return accum;
        return Factorial(Sub(current, 1), Mul(current, accum));
    }
}

100,000の階乗なんて検証の仕様も無いけど、とりあえずそれっぽい結果が出てたし、もちろんStackOverflowExceptionだって発生しなかった。

末尾再帰の最適化が行われる条件

は以下の通りじゃないかと推察してみた。

当然大前提として、末尾再帰の条件を関数が満たしている必要がある。

また、先に書いた条件を現状有姿で検証した結果なので、フレームワークやJITの構成が変化すれば当然結果も変化すると思う。²

Primitive型

Primitive型¹は無条件で末尾再帰の最適化が行われている。

それ以外の値型

それ以外の任意の値型は、引数に存在するだけで末尾再帰の最適化が行われなくなる。

任意の参照型

任意の参照型に関しては、若干複雑で、引数に存在しているコトはこの問題に対して、透過的である。従って任意の参照型を用いた末尾再帰関数が最適化されるか否かはメンバ変数やプロパティがどのような型なのか、またどのように関数内で取り扱われるかで最適化が行われるのか否かが分かれる。

メンバ変数やプロパティがPrimitive型

の場合は、先のPrimitive型の場合と同様に、問題なく最適化がかかる。

任意の型の場合

この場合は、直接関数内でメンバに対する操作を行うと、最適化が外れる。

メンバに対する操作をバイナリコードレベルで分離すれば最適化が行われる。そのためには、関数を分割するだけでは不十分で[MethodImpl(MethodImplOptions.NoInlining)]を付与する必要がある³

また、対検証した結果string等の任意の参照型の場合も、関数内で直接操作を行ってしまうと、最適化が外れる条件になっていた。

まとめ

2回にわたって末尾再帰の最適化を割とユルく検証してみた。

結果、Primitiveを対象とした関数であれば、比較的容易に末尾再帰の最適化を行える反面、それ以外の型で行おうとすると様々な制約がかかり、やれなかないが、やる意味が無い状態になっていた。

このように、末尾再帰の挙動に関しては結構厄介なので、まとめてみたので、何かの一助になれば幸いです。

typeof(T).IsPrimitiveが、trueの型と言うことで一つ。 ↩
よく知られているけど、32bitのJITは末尾再帰の最適化を全然行わない。 ↩
付与しなくても、Inliningが発生しないのなら動くと思う。 ↩

RyuJITのお仕事(2/2)