Julie に、本物の Julia を食べさせてみた

Julie（まだ公開していない、手元だけの子です）という、OCaml で書いたおもちゃの Julia 実装があります。多重ディスパッチ、抽象型の階層、struct、クロージャ —— Julia らしさの芯のところを、小さなインタプリタでどこまで再現できるか試した子で、wasm_of_ocaml で本物の WasmGC にまでコンパイルできます。

ここまでは、ずっと自分で書いたデモプログラムで確かめてきました。struct を作って、クロージャを作って、ディスパッチが正しく解決するのを見て、「動いている」と思っていました。

でも自分で書いたテストは、自分が想像できる壊れかたでしか壊れません。

そこで、本物の Julia のコードを持ってくることにしました。JuliaLang/Microbenchmarks —— Julia のチーム自身が、言語の速さを他言語と比べるために使っている、あのベンチマーク集です。マクロ（@test や @timeit）だけ剥がして、アルゴリズムの本体はそのまま Julie に食べさせてみました。

見つかった、本物のバグ

fib（再帰フィボナッチ）は、すぐに動きました。

quicksort は、動きませんでした。二つ、足りないものがありました。>>>（論理右シフト）という演算子がそもそも存在していなかったこと。それから、a[i], a[j] = a[j], a[i] という、配列の要素どうしを入れ替える構文——分割代入の対象が変数名しか受け付けていなくて、添字への代入という発想がまるごと抜けていました。

両方直して、動くようにはなりました。けれど、直したあとにもう一段、ぞっとする発見がありました。

quicksort は再帰関数です。関数の中で i, j = lo, hi のようにローカル変数を作ります。ここで、Julie の「代入」の実装を見直してみたら——存在しない変数名への代入が、いちばん外側のグローバルスコープまで歩いていって、そこに作られていたのです。つまり、quicksort が自分の中で「ローカル」だと思っていた i や j は、実は全部ひとつの共有されたグローバル変数でした。再帰呼び出しどうしが、気づかないまま互いの i を踏みつぶしていたことになります。

自分の書いたデモは再帰しなかったので、このバグに一度も触れませんでした。本物のコードを持ってきて、初めて表面化した不具合です。「ああ、そうか」と、直しました。新しいローカル変数は、いちばん外側にではなく、代入が書かれたそのスコープに作る——直してみれば当たり前のことでした。

遅い。じゃあ、直そう

三本とも動くようになったところで、速さを測ってみました。素朴な木を歩くだけのインタプリタなので、当然、実 Julia より圧倒的に遅い。フィボナッチで実に約 400 倍、円周率の級数和（500万回のループ）にいたっては約 5,300 倍でした。

ここから、六段階の最適化をしました。どれも「動的な挙動は一切変えない、安全な高速化」だけを選びました。

• 演算子（+ や < など）の呼び出し箇所ひとつひとつに、前回見た引数の型と、解決済みの実装を覚えておくインラインキャッシュ。同じ型で呼ばれ続ける限り、候補探索も特異度の計算も、二度とやらない。
• 名前つき関数の呼び出しにも、同じキャッシュ。
• for ループが 1 回まわるたびに Hashtbl を新規に割り当てていたスコープを、軽い連想リストに置き換え。
• キャッシュが当たっているのに、比較のために毎回新しいリストを作っていた無駄を消す。
• 変数の読み書きそれぞれに、「前回、スコープチェーンを何回たどって見つかったか」を覚える、もうひとつの小さなキャッシュ。

六段階を積み重ねて、フィボナッチは約 12 倍、円周率の級数和は約 15 倍速くなりました。まだ実 Julia の 30〜300 倍遅いけれど、正直に言えば、これは想定の範囲でした。

プロファイラが教えてくれたこと

ここまでは全部、コードを読んで、頭の中で「たぶんここが重い」と推理して直してきました。最後にもう一段だけ、推理をやめて、V8 の実際のプロファイラ（node --prof）を回してみました。

eval_expr          31.0%
call_cached        25.3%
caml_string_equal    7.6%
compare_val          7.0%   ← これは、何だろう
assoc_opt            5.4%
bind                 5.1%

compare_val という、見覚えのない名前が 7.0% も居ました。調べてみると、変数のスコープを検索するのに使っていた OCaml 標準ライブラリの List.assoc_opt は、多相関数でした。キーがいつも文字列だとわかっていても、この関数自身はそれを知らないので、実行時に「型を調べてから比較する」という汎用の経路を、律儀に毎回通っていたのです。

文字列専用の比較関数を直接使うよう、10 行ほどの関数を書いて差し替えました。もう一度プロファイルを取ると、compare_val はきれいに消えていました。ずっと「割り当てを減らせば速くなる」と思って最適化してきたのに、プロファイラは「GC の割合は最初からずっと 3% で、そこは最初からボトルネックではなかった」と、静かに教えてくれました。自分の推理だけを信じ続けていたら、たぶん見つけられなかった一段です。

複素数を食べさせる

四本目のベンチマークは、マンデルブロ集合でした。これは複素数を必要とします——Julie にはまだ、複素数がありませんでした。

complex(re, im) を作って、real / imag を作って、+ - * ^ を複素数どうしで定義して。マンデルブロの本体（脱出判定のループ）は、これらさえ揃えば一行も書き換える必要がありませんでした。動かしてみたら sum(mandelperf()) == 14791——本物の Julia の @test が確かめている値と、ぴったり一致しました。

途中で、Julie の Range が整数専用で、-1.0:0.1:1.0 のような浮動小数点の範囲が書けないことにも気づきました。今回はスケールした整数レンジで回避しましたが、直したわけではありません。comprehension が for 節をひとつしか取れないことも、同じベンチマークで見つかりました。

おわりに

自分で書いたテストは、優しすぎます。想像できる壊れかたしか、再現してくれません。

本物のコードを持ってきて、初めてわかったことがいくつもありました。再帰の中で共有されていたグローバル変数。存在すら知らなかった >>> という演算子。標準ライブラリの奥に隠れていた、多相のコスト。どれも、自分のデモだけを眺めていたら、気づかないまま次の機能を足し続けていたと思います。

「動いている」というのは、たぶん「自分が試した範囲では壊れていない」という意味でしかありません。次に何かを作ったときも、自分のテストで満足する前に、一度くらいは本物のコードを連れてきて、食べさせてみようと思います。

つづきは、また、そのときに。