再帰関数のスタックオーバーフローを倒す話 その2

F# IL

連載目次

はじめに

再帰関数のスタックオーバーフローを倒す話 その1の続きです。 前回はCPS変換することでスタックオーバーフローが回避できるよやったー！という話でした。 今回は、CPS変換じゃスタックオーバーフロー回避できない場合もあるよ、という話をします*1。 前提知識は、その1の記事を理解していることと、ILがなんとなくわかることです。 その1.5に対する深い理解は不要ですが、 読んでいるに越したことはありません。

CPS変換のおさらい

非末尾再帰の関数を末尾再帰化できる、というのがCPS変換でした。 そして、末尾呼び出しの最適化によってスタックが食いつぶされなくなるので、 スタックオーバーフローが起きなくなるようにできる、というものでした。

2種類の末尾呼び出しの最適化

さて、実はF#では末尾呼び出しの最適化は2つのパターンがあります。 一つ目はジャンプ命令への書き換えで、もう一つはtail.プレフィックスの付与です。

ジャンプ命令への書き換え

ジャンプ命令への書き換えは、呼び出しをbr系のIL命令に書き換えてしまうものです。 例えば、

let rec fact acc n =
  if n = 0 then acc
  else fact (acc * n) (n - 1)

このようなアキュムレータ変数を使った末尾再帰関数をコンパイルすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.1          // 1番目の引数(n)のload
IL_0002: brtrue.s IL_0006 // loadした値が0以外(0: false, 0以外: true)ならIL_0006にジャンプ

IL_0004: ldarg.0          // 0番目の引数(acc)のload
IL_0005: ret              // loadした値を返して関数終了

IL_0006: ldarg.0          // 0番目の引数(acc)のload
IL_0007: ldarg.1          // 1番目の引数(n)のload
IL_0008: mul              // loadした2つの値を乗算(acc * n)・・・(1)
IL_0009: ldarg.1          // 1番目の引数(n)のload
IL_000a: ldc.i4.1         // 定数1をload
IL_000b: sub              // loadした2つの値を減算(n - 1)・・・(2)
IL_000c: starg.s n        // (2)の結果を引数nにstore
IL_000e: starg.s acc      // (1)の結果を引数accにstore
IL_0010: br.s IL_0000     // 無条件でIL_0000にジャンプ

このコードには、call系の命令がないことが分かります。 その代わりに、最後に無条件で先頭にジャンプしており(br.s IL_0000)、これが元のコードだと再帰呼び出し部分に相当します。

ILでは分かりにくい、という人向けに、上記ILをF#風言語で表現してみました。

let fact acc n =
  while n <> 0 do
    let tmp = acc * n
    n <- n - 1
    acc <- tmp
  acc

このように、末尾再帰呼び出しをジャンプ命令に置き換えることで、ループと等価になりました*2。

自分自身を末尾で呼び出す再帰関数*3の場合、関数から戻ってきた後にすることがないということは、(引数の状態を更新してから)関数の先頭にジャンプしてもいいと言うことです。

tail.プレフィックスの付与

tail.プレフィックスの付与は、末尾呼び出しされているcall系の呼び出し命令にtail.というプレフィックスを付けることで、 JITコンパイラの最適化によってスタックフレームを消費しないようにしてもらうものです。 例えば、

let rec fact n cont =
  if n = 0 then 1 |> cont
  else fact (n - 1) (fun pre -> pre * n |> cont)

このような継続渡しスタイルの関数を「末尾呼び出しの生成」オプションをオンにしてコンパイルすると、以下のようなILが吐かれます。

IL_0000: nop
IL_0001: ldarg.0          // 0番目の引数(n)をload
IL_0002: brtrue.s IL_000e // loadした値が0以外(0: false, 0以外: true)ならIL_000eにジャンプ

IL_0004: ldarg.1          // 1番目の引数(cont)をload・・・(1)
IL_0005: ldc.i4.1         // 定数1をload・・・(2)
IL_0006: tail.            
// (1)でloadした関数値に(2)でloadした値を渡して実行
IL_0008: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000d: ret              // 実行した結果を返して関数終了

IL_000e: ldarg.0          // 0番目の引数(n)をload
IL_000f: ldc.i4.1         // 定数1をload
IL_0010: sub              // loadした2つの値を減算(n - 1)・・・(3)
IL_0011: ldarg.0          // 0番目の引数(n)をload・・・(4)
IL_0012: ldarg.1          // 1番目の引数(cont)をload・・・(5)
// (4)でloadした値と(5)でloadした値を渡してfact@22オブジェクトを生成
IL_0013: newobj instance void class Sample/fact@22<!!a>::.ctor(int32, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !0>)
IL_0018: starg.s cont     // 生成したオブジェクトを引数contにstore
IL_001a: starg.s n        // (3)の結果を引数nにstore
IL_001c: br.s IL_0000     // 無条件でIL_0000にジャンプ

基本的な構造は同じですが、少し複雑になっています。 アキュムレータ変数による末尾再帰関数の例と同様にF#風の言語で表現してみるとこうなります。

let fact n cont =
  while <> 0 do
    let tmp = n - 1
    cont <- fact@22(n, cont)
    n <- tmp
  cont 1

ループの中でcontをネストさせていき、関数の最後でcontに1を渡していることが分かります。 再帰部分の処理は、fact@22というクラス*4に行ってしまい、 このコードだけでは読み取れなくなりました。 fact@22というクラスをまずはF#風の言語で表現してみます。

type fact@22<'a> (n: int, cont: int -> 'a) =
  inherit FSharpFunc<int, 'a>()

  override __.Invoke(pre) = cont (pre * n)

このように、本体の処理はInvokeメソッド内に移動しています。 InvokeメソッドのILはこのようになっています。

IL_0000: nop
IL_0001: ldarg.0 // 0番目の引数(this)をload
// loadしたオブジェクト(this)のフィールドcontをload・・・(1)
IL_0002: ldfld class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !0> class Sample/fact@22<!a>::cont
IL_0007: ldarg.1 // 1番目の引数(pre)をload
IL_0008: ldarg.0 // 0番目の引数(this)をload
// loadしたオブジェクト(this)のフィールドnをload
IL_0009: ldfld int32 class Sample/fact@22<!a>::n
IL_000e: mul     // loadした2つの値を乗算(pre * this.n)
IL_000f: tail.
// (1)でloadした関数値(this.cont)に乗算結果を渡して実行
IL_0011: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, !a>::Invoke(!0)
IL_0016: ret     // 実行した結果を返して関数終了

さて、ここでfact本体のIL_0006とInvokeのIL_000fを見てみましょう。 tail.というILが発行されていることが分かります。

このILが発行された後に続くcall系の呼び出しは、 JITコンパイラによって現在のスタックフレームを再利用*5するようにして実行されるようになります。

2つの最適化の違い

なぜ末尾呼び出しの最適化に2種類の方法があるのでしょうか？ それは、両者の性質が大きく異なるためです。

まず、前者のジャンプ命令に変換する方法ですが、 br系の命令はメソッド内の移動にしか使えません。 そのため、メソッドをまたぐようなジャンプはできず、CPSで現れるようなラムダ式を表すクラスのメソッドへのジャンプはできません。

それに対して、tail.プレフィックスを付与する方法は、 call系のメソッドが末尾で呼び出されていれば別のクラスのメソッド呼び出しであろうが有効です。 しかし、tail.プレフィックスはJITコンパイラ任せなため、 本当に呼び出しが最適化されるかどうかの保証をF#の処理系レベルで担保することができません*6。

また、その1.5でみましたが、コンストラクタ呼び出し(newobj)は末尾呼び出しの最適化対象ではありません*7。 そのため、ループごとにコンストラクタ呼び出しが走ることになります。 これは、F#ではtail.プレフィックスを用いた最適化よりもジャンプ命令に変換する最適化の方が効率が良いことを意味します。

まとめると、

最適化方法 適用可能場所 処理系での保証
ジャンプ命令での置き換え 自己末尾再帰 できる
tail.プレフィックスの付与 末尾再帰一般 できない

となります。

tail.プレフィックスでスタックオーバーフローになる場合

tail.プレフィックスが付いているコードであっても、スタックオーバーフローを起こす場合があります。 まだ原因はわかっていないのですが、

  • (式木の変換のような)それなりに大きい再帰関数をCPS変換
  • 64bitのIIS上で実行

というような状況で、リビルド後の初回のアタッチでスタックオーバーフローが起きました。 2回目以降のアタッチではスタックオーバーフローが起きませんし、 小さくて単純な再帰関数をCPS変換してもオーバーフローは起きませんでした。

また、32bitのIISでは試していませんが、 一般的に32bit環境ではスタックフレームのサイズが64bit環境よりも小さくなるため、 スタックオーバーフローを起こしにくくなる可能性はあります。

ということで、特定の条件下ではCPS変換によってスタックオーバーフローを防ぐことができない場合もあるため、 F#においてはCPS変換したからと言って完全に安全とは言い切れない、という話でした。 「特定の条件」がまだ定かではないので、調査は継続しますが、今のところIISでホストしない場合には再現しませんので、非Webアプリであれば問題ないかもしれません。 次回の「その3」がおそらく最後で、ではどうやってスタックオーバーフローを倒せばいいか、の予定です。

*1:その1で「その2はコンピュテーション式の話になる予定です」と書きましたが、その話は2.5で使用と思います

*2:ちなみに、コンパイラの最適化オプションがオンでもオフでも、ジャンプ命令への書き換えは行われるようです

*3:以降、自己末尾再帰と呼ぶことにします

*4:F#のラムダ式はクラスとして実現されています

*5:現在のスタックフレームを破棄して新しいスタックフレームをそこに作る

*6:ジャンプ命令への書き換えはコンパイル時の最適化であり、tail.プレフィックスの付与はランタイム時の最適化と言えるでしょう

*7:実際に、IL_0013の直前にはtail.プレフィックスが付いていません