翻訳: Elmコンパイラの出力を改善する

この記事は"Improving Elm's compiler output"を原著者の承諾を得た上で日本語に翻訳したものです。原著者はElmの開発チームの1人なので、記事で紹介されている変更が将来的に取り込まれる可能性は高いと思われます。

なお、脚注は全て訳者によるもので原文には存在しません。以下本文。

---

Elmは速い。

これはコンパイラに何か革新的なものがあるからではない。実際、Elmコンパイラはほとんど何の最適化も行っていない。

Elmが速いのはJavaScriptにコンパイルされるからだ。JavaScriptは、熱意と才能を携えた世界中のエンジニア達が10年以上にわたって最適化を続けてきたものだ。

しかしここで疑問がわく。Elmコンパイラはブラウザーが最適化しやすいJavaScriptを出力しているのだろうか？また、仮にそうでないならば、出力するJavaScriptを変更すればパフォーマンスは向上するのだろうか？

ちょっと覗いてみよう。

隠れクラス

JavaScriptは動的言語だ。JavaScriptにおいて、オブジェクトはいつでも形状(shape)^[1]を変えることができる。変数やデータ構造はいつだって様々な型の様々な値を持つことが可能だ。しかし、現実には大抵のプログラムは割と静的な作りをしているし、ブラウザーも可能ならばそれを利用する。

Chromeではオブジェクトリテラルとクラスは形状として扱われる。プロパティが動的に追加・削除されるという具合に、オブジェクトやクラスの形状が変化するとChromeはそれを新しい形状と見なすし、それらを相互に変換しようとする。正格な形状を把握するのが難しい場合、Chromeはオブジェクトをハッシュマップとして扱うこともある（ElmのDictのように）。私達はこれらの形状を隠れクラスと呼んでいる^[2]。

最もパフォーマンスに優れるのは、JavaScriptのコードが見たところ複数の異なる形状を一度に扱っていないときだ。幸運にもElmは静的言語なので、ほとんどいつもそうなっているはずだ。ただ、Elmが異なる形状を同じ型として作る場合もある。1つ例を見てみよう。

type Maybe a
  = Just a
  | Nothing

これはElmのMaybeの定義だ。これは次のようなJavaScriptにコンパイルされる（--optimizedを使っている）。

var elm$core$Maybe$Just = function (a) {
    return {$: 0, a: a};
};

var elm$core$Maybe$Nothing = {$: 1};

読めばわかるように、JustとNothingに対するJavaScriptのオブジェクトリテラルは形状が違っている。こうしてMaybeを扱うJavaScriptのコードは、2つの異なる形状を取り扱えなければならなくなった。しかしこれはコストなのだろうか？

影響を測るために私が行ったことは2つ。

1. パフォーマンスに差異が出ると期待してベンチマークを取り、2つのバージョンを作る。うち1つはオーバーヘッドを避けるため手で修正する。
   
2. Nodeが出力するアセンブリを読む（NodeとChromeはどちらもJSエンジンとしてV8を使っている）
   

この実験のためのコードはgithubで読める。

私はElm組み込みのList型に着目した。この型はほとんどのプログラムで使われているからだ。この部分でパフォーマンスを改善できれば、全てのElmユーザーが大きな恩恵にあずかることになる。

次のベンチマークを見てみよう。

benchmark "int +" <|
  \_ -> foldl (+) 0 intList

単純な全要素の左畳み込みで、要素を全部を足し合わせている。ここでのパフォーマンスの変化は、リストをどれだけ速く走査できるかを示してくれる。理論的には、複数の隠れクラスを扱うことによるオーバーヘッドを取り除けばパフォーマンスは向上するはずだ。

ベンチマークをコンパイルしよう。コンパイルされたJSを見ると、こんなコード片が見つかる。

var _List_Nil = { $: 0 };
function _List_Cons(hd, tl) { return { $: 1, a: hd, b: tl }; }

空リストはリストの要素とは違った見た目をしている（Listの動きが気になるなら、Elm Europe 2017で詳しく説明したので見てほしい）。

JSファイルをコピーし、こんなふうに修正する。

var _List_Nil = { $: 0, a: null, b: null };
function _List_Cons(hd, tl) { return { $: 1, a: hd, b: tl }; }

Listはもはや（複数の形状の）多相^[3]ではない。

結果はこうだ。

• Firefox, 修正前: 75,843 ops/sec
• Firefox, 修正後: 84,549 ops/sec
• Safari, 修正前: 248,531 ops/sec
• Safari, 修正後: 248,530 ops/sec
• Chrome, 修正前: 294,434 ops/sec
• Chrome, 修正後: 302,569 ops/sec

つまり、Safariでは違いが無かったけれど、ChromeとFirefoxではかなりの改善が見られた。Firefoxでは~11%、Chromeでは~4%の改善だ。注意してもらいたいが、これはコンパイラで実装できることで、Elmのコードを変える必要は全くなく、アプリケーション開発者側は何も頑張る必要がないパフォーマンス向上なのである。

次のスクリプトを実行すればV8が生成したコードも見られる。

node --print-opt-code --code-comments index.js > jit_log

修正無し版のベンチマークのjit_logを読むとこんな結果が見つかる。

--- Optimized code ---
optimization_id = 1
source_position = 48049
kind = OPTIMIZED_FUNCTION
name = $List$foldl
stack_slots = 10
compiler = turbofan
address = 0x28bd2bd6e9a1
Body (size = 2292)
Instructions (size = 2012)
<Assembly code>

修正したコードのログはこちら。

--- Optimized code ---
optimization_id = 0
source_position = 48067
kind = OPTIMIZED_FUNCTION
name = $List$foldl
stack_slots = 10
compiler = turbofan
address = 0x2081135eec01
Body (size = 1848)
Instructions (size = 1600)
<Assembly code>

期待通り、多相を扱う必要が無い場合の方が生成コードが少ない。

しかし、両方のログに残るある記述が私を戸惑わせてた。

Inlined functions (count = 1)
 0x3f2705632551 <SharedFunctionInfo A2>

ログのこのセクションはいくつの関数がインライン化されたかを列挙している。今回のケースだと、関数の引数を評価する関数だけがインライン化されていた（この意味についてはすぐに説明する）。実はこれはそんなに驚くようなことではない。foldl内部には関数呼び出しは1つしかない。これはループの度に一度だけ実行される^[4]。中で呼ばれる関数は大抵同じものではないので、インライン化されていなくても不思議な話ではない。しかし、最適化された関数を見ていくとわかるように、インライン化されているのは引数を1つ取る関数（1引数関数とも呼ばれる）か、A2, A3, A4などと呼ばれる関数かのどちらかだけなのである。

どういうことだろう？

インライン化^[5]

関数呼び出しのインライン化（関数呼び出しをその関数の実装に置き換えること）はコンパイラができる最も重要な最適化の1つだ。これが重要であるのは、関数呼び出しが総じてハイコストであるから、というわけでは必ずしもない。むしろ、インライン化によってコンパイラはコードが何をしているかをよりよく理解し、それに基づいて最適化を実行できるようになるからだ。

もう一度ベンチマークを見よう。

benchmark "int +" <|
  \_ -> foldl (+) 0 intList

インライン化されなければこのコードはfoldlを呼び出す。foldlはリストの各要素に対して関数を呼ぶループである。foldlはどんな関数でも受け付けるので、（たとえスタックに保存できたとしても）中間結果の数値は参照として保持され、関数呼び出しの度にメモリへのルックアップが走る^[4:1]。整数以外を畳み込むときなどはそうだが、中間結果が整数でない場合、オプティマイザーは全ての値をfoldlの中で使えるハッシュマップのように扱う。

しかし、インライン化されればこの関数は単なるjavascriptのループにコンパイルされる。そこには関数呼び出しが1つもない代わりに、ループ内で実際に使われている型に特化したコードが展開されているのだ。実際にはコンパイラは関数呼び出しを単相にはしないのだけどその恩恵をうけられる、みたいな話だ^[6]。

ではなぜ多くの関数がインライン化されないままなのか？そしてA2って一体何なんだ？

カリー化

Elmにはカリー化という概念がある。以下の関数があるとする。

add : Int -> Int -> Int
add a b =
  a + b

こんな新しい関数を作ることが出来る。

add2 : Int -> Int
add2 =
  add 2

つまり、引数を全て渡して関数を呼び出せば実行され、一部のみ渡して呼び出せば足りない関数を受け取る新しい関数が返される。

上のadd関数はこんな感じにJSにコンパイルされる。

function F(arity, fun, wrapper) {
  wrapper.a = arity;
  wrapper.f = fun;
  return wrapper;
}

function F2(fun) {
  return F(2, fun, function(a) { return function(b) { return fun(a,b); }; })

var author$project$Main$add = F2(function(a, b) {
  return a + b;
});

私達のadd関数も他のElmの関数はどれも、あるオブジェクトにラップされている。このオブジェクトは元の関数、関数が期待する引数の数、そしてカリー化された関数からなる。関数呼び出しにはA2が必要で、以下はその実装だ。

function A2(fun, a, b) {
  return fun.a === 2 ? fun.f(a, b) : fun(a)(b);
}

A2はF2オブジェクトを受取り、受け取った関数が事実引数を2つ取るならばそれを直接呼び出す。そうでなければカリー化関数を部分適用する。

javascriptエンジンから見ればこれは大きな問題だ。プログラム全体の解析（これはとてもコストが高い）が終わるまで、元の関数が呼び出されるのか、カリー化関数が呼び出されるのか知る術がないのだ。A2自体はインライン化できるが、それ以上は無理だ。

じゃあElmコンパイラをもっと賢くしたら？もしElmコンパイラが関数が求める引数の数を知っていれば、これを

A2(author$project$Main$add, 1, 2)

こう書き換えられる。

author$project$Main$add.f(1, 2)

ベンチマークをコピーして、ベンチマークとそこから呼ばれる全ての関数呼び出しを手で修正する。

今回焦点を当てるのは次の関数。

benchmark "* 2" <|
  \_ -> map (\a -> a * 2) intList

結果はこうなった。

• Firefox, 修正前: 24,291 ops/sec
• Firefox, 修正後: 50,927 ops/sec
• Safari, 修正前: 35,723 ops/sec
• Safari, 修正後: 49,029 ops/sec
• Chrome, 修正前: 39,253 ops/sec
• Chrome, 修正後: 58,491 ops/sec

かなりよい。Firefoxでは2倍、ChromeとSafariでは~30%のパフォーマンス向上だ。

修正前のコードのインライン化の結果はこう。

Inlined functions (count = 1)
 0x13f84c332341 <SharedFunctionInfo A2>

修正版ではいくらか変化が見られる。

Inlined functions (count = 5)
 0x1f31bec396e1 <SharedFunctionInfo $map>
 0x1f31bec395a9 <SharedFunctionInfo $foldr>
 0x1f31bec39541 <SharedFunctionInfo $foldrHelper>
 0x1f31bec32049 <SharedFunctionInfo F2>
 0x1f31bec31fe1 <SharedFunctionInfo F>

しかし、生成されたアセンブリを見ると多くの行に以下の記述が見られた。

call 0x1e5fad48abe0  (Call_ReceiverIsNotNullOrUndefined)

someObject.f(args)というかたちで関数を呼ぶとき、ChromeはsomeObjectがnullやundefinedではないことを確かめなければならない。

もう一度ベンチマークを取った。今度はFラッパーから関数を取り出し直接呼ぶようにした。

結果。

• Firefox, 修正前: 50,927 ops/sec
• Firefox, 修正後: 59,632 ops/sec
• Safari, 修正前: 49,029 ops/sec
• Safari, 修正後: 43,695 ops/sec
• Chrome, 修正前: 58,491 ops/sec
• Chrome, 修正後: 63,619 ops/sec

ChromeとFirefoxではいくらかの速度向上が見られた。それぞれ~8%と~16%の改善だ。Safariは遅くなったが理由は不明。ベンチマークを何回か走らせたところ結果は大きくばらついたがこれも原因はよくわからない。

結論

Elmは速いがまだ高速化の余地はある。Elmコンパイラの出力を変えれば、Elmプログラムのパフォーマンスは有意なレベルで向上する。

参考文献

Chromeが如何にしてJavascriptを高速化しているかを知りたければ、以下の2つが私が知りうる中で最良だ。

Whats up with monomorphism
V8 Kinds

---

翻訳は以上になります。Elmコンパイラの出力については以下のScrapboxにも情報を載せていく予定です。

https://scrapbox.io/read-elm-js/

最後に訳文のチェックや励ましなどでご協力いただいた方へスペシャルサンクス

• https://twitter.com/y047aka
• https://twitter.com/nikueaters

脚注

1. どんなフィールドを持つかということ。定訳があるかは不明。

2. 主語はweなので「私達」と訳したが、"hidden class"自体はV8の開発サイドも使っている用語。

3. ここでの「多相」は「1つの型で異なった複数の形状を使っている」というような意味で使われており、パラメトリック多相とか部分型付けなどとは無関係。詳しくは"Inline Caching"で検索するか参考文献を参照。

4. ここはfoldlのコンパイル結果を読むと話がはやい。なお、foldlの定義がwhileループになっているのはElmコンパイラが末尾再帰の最適化を行っているため。末尾再帰については検索したらすぐに解説が見つかるだろうが、例えばこれを参照されたし。

5. V8は頻繁に呼び出される関数を自動でインライン展開してくれる。ベンチマークでは同じ関数を膨大な回数呼び出すのでインライン展開されていてほしい、という前提があるように思われる。またこれは機械語レイヤーの話であり、ElmがJSのコードをインライン展開するという話ではないことには注意されたし。

6. 本文中の"polymorphic"や参考文献での"monomorphism"の使い方をみると勘違いしそう（訳者は思い切りした）だが、ここで"monomophising"は「多相で定義された関数の呼び出しを、呼び出し時の引数の型に特化したコードに変換する」という、人によってはよく慣れ親しんだ意味で使われている。原著者が挙げてくれたコード例を使って具体的に説明する。listmapは(a -> b) -> List a -> List bと型付けられる多相関数で、引数にどんな型が来るかはわからないとする。しかし"monomorphising compiler"はlistmap String.fromInt [ 1, 2, 3 ]をIntやStringに最適化されたコードに変換してくれる。なお、訳文はこの理解のもとに言葉を補っている。