元ネタはこちら
TCOと例外ハンドル | κeenのHappy Hacκing Blog
これを機械語レベルで理解したく、OCamlで検証してみることにしました。
同じベンチマークコードではなく機械語を読みやすくするためにシンプルな例にしてます。
ちなみになんか当たり前の結果になったので分かってる人は読まなくていいと思います :)
元ネタを振り返ると、末尾再帰の気持ちで書いてたコードの最後の末尾再帰呼び出しのところに例外ハンドラを書くとすごくパフォーマンスが落ちた原因を考えたら多分末尾再帰呼び出し最適化がかからないからだ、というものでした。
SMLで書いていると機械語が読めないのでOCamlで実験します。実験コードは下のようなものです。
関数loop1とloop2は内部で再帰呼び出しによりループする関数を呼び出していて、その補助関数は引数を１つだけ受け取ってそれをインクリメントしてまた次の再帰呼び出しをします。引数の値が一定数に達したら例外を投げます。
違いはどこでその例外をキャッチするか、だけです。loop1ではループ内に例外ハンドラをかき、loop2ではループの外に書いています。
ループ回数を変えてパフォーマンスの実験もしてみたので結果を下に示します。
│ loop1:1024 │ 937.07ns │
│ loop1:2048 │ 1523.67ns │
│ loop1:4096 │ 3057.56ns │
│ loop1:8192 │ 6511.70ns │
│ loop1:16384 │ 11817.98ns │
│ loop2:1024 │ 7973.02ns │
│ loop2:2048 │ 16045.53ns │
│ loop2:4096 │ 32066.57ns │
│ loop2:8192 │ 80046.59ns │
│ loop2:16384 │ 143159.80ns │
めっちゃloop2が遅い…。ループ回数214 = 16384回の時では10倍以上かかっていますね。
更にループ回数が増えた時の傾きもスゴイことになってます。
原因はシンプルでloop1は末尾再帰呼び出しでloop2はそうじゃないから。
機械語を見てみましょう。何やっているのかはコメントに詳細に書きました。
（ちなみに例外がどういうふうに処理されているのか気になっておっかけました）
関数fではjmpで澄んでいたところが、関数gでは通常のcall命令になっていることがわかったと思います。
さらにこのケースでは全てレジスタの上の計算で完結していたものが、スタックの操作つまりメモリの方を触らないといけなくなって遅くなってることが予想されます。
まぁ例外ハンドラの位置を気を気をつけましょう。
おまけ
いつかのOCamlのアップデートで(4.02の時だったかな？)例外をキャッチするための構文try-withはパターンマッチのシンタックスシュガーになりましたね。
したのプログラムの意味はだいたい一緒です。
try exp with Ex -> ()
match exp with exception Ex -> ()
これはmatch文のなかで、expで発生した例外はキャッチしたいけど、expの計算が終わったあとの計算中の例外はキャッチしたくない時があるため導入されました。
let r = ref 0
let rec loop1 n =
match 100 / n with
| m -> incr r; loop1 (n - 1)
| exception Division_by_zero -> !r
let r = ref 0
let rec loop2 n =
try
match 100 / n with
| m -> incr r; loop2 (n - 1)
with Division_by_zero -> !r
同じように見えますがloop1は末尾再帰でloop2は違います。
# loop1 1000000000;;
- : int = 1572523814
# loop2 1000000000;;
Stack overflow during evaluation (looping recursion?).
という話がJaneStreetのブログに載ってますね :)
Pattern matching and exception handling, unite! :: Jane Street Tech Blogs
