JavaScriptの高速化をやってみた

概要

JavaScriptは今やさまざまな場面で使われているメジャーなプログラミング言語のひとつです。

そうなると、どうしても興味が出てくるのはその実行速度です。昔node.jsはC10K問題への解決策としてもてはやされた時代もありました。node.jsはたった1スレッドで秒間1万ものクライアントからの接続を処理するというのです。

しかし、闇雲に遅いプログラムを書いていてはそんなことは到底成し得ないでしょう。そのため、巷にはJavaScript高速化は関心の集まるところとなり、世の中には高速化に関する記事があふれています。

これまでそんなに速度を気にしたことがなかったので自分で試してみることにしました。この記事はその結果分かったことをまとめたものです。

結論

関数をインライン化すると速い。あとオブジェクトを作らない

対象プログラム

今回高速化の対象としたプログラムはここにあります(TypeScriptで書かれていますが気にしないでください)。

github.com

このプログラムはある種の機械語に対するインタプリタです。一応説明しておくと、背景にあるのは自分の大学にあるCPU実験と呼ばれる演習です。この実験では学生はグループに分かれて独自の機械語を策定し、それを実行するCPUをFPGA上に実装したり、その機械語をターゲットとするコンパイラを実装したりします。機械語に対するインタプリタはこの実験の一環として作られるものです。なお、自分がCPU実験を受講したのは2年前です。今回使用する機械語や入力等は自分が受講していた当時の自分の班のものを使用しています。

よって、今回のプログラムで主となるのはメモリ上の操作や四則演算・ビット演算になります。JavaScriptといってもDOMの操作とかそういうのとは趣が異なりますがご了承ください。

実行環境はnode.js v8.7.0です。入力される機械語は26億命令程度のもので、1億命令にかかる実行時間を測りました。

github.com

↑このファイルに高速化の各過程での測定結果がまとめてあります。1から6まであり、1が最初で6が最後です。一番上のCというのはC言語の実装(実験当時に使っていたもの)の測定結果です。今回は自分の最適化力の不足により、C言語には勝てませんでした(C言語版のほうが機能が豊富でJS側に有利な比較なのですが)。

JS1からJS6のプログラムは前述のリポジトリにタグとしてマークしてあります。

以下ではやってみた高速化を順に解説します。上にも結論が書いてありますが、高速化が進むにつれてプログラムが汚くなります。

%は結構遅い

当然ですね。

どういうことかというと、実は上のプログラムでは1億命令実行するごとにデバッグ出力を行います。皆さんならこれをどう実装するでしょうか。

当初の実装 (JS1)はこれまでの総実行命令数を数えて、それを1億で割って0ならデバッグ出力を行うようになっていました。ここで%による余りの演算が登場します。

高速化にために、総実行命令数とは別にカウンタを毎回1ずつ増やしていき、それが1億になったらデバッグ出力を行いカウンタは0にリセットするように変更しました。この方法なら、1億と===による比較を行えばよいため%を消すことができます。処理としては1ループごとに%の処理が消えて代わりにカウンタ変数に対するインクリメントが増えたことになります。これにより1億命令あたり0.6秒実行時間が減り、3.8秒から3.2秒になりました。結構大きい割合ですね。%は結構遅い処理だったようです。当該のコミットはこれです。

github.com

関数を毎回作らない

今回のプログラムは機械語インタプリタでした。機械語なので、「2つのレジスタから値を読み込み、何らかの計算を行って結果をレジスタに格納する」という命令が多く登場します。

これらの命令に対する処理は、どんな計算を行うか以外は共通したものになるはずです。となると、計算部分を関数として抜き出して抽象化したくなります。今回のプログラムでもそのような設計になっており、共通部分をまとめた関数がいくつかありました。例えば足し算命令 (add)と引き算命令 (sub)は同じop関数を使っています(下記に引用)。

    case 0b000000:
        // add
        op(inst, registers, (x, y)=>x+y);
        break;
    // 中略
    case 0b000010:
        // sub
        op(inst, registers, (x, y)=>y-x);
        break;

命令によって処理が異なる部分を関数として抜き出していることが分かります。

ところが、これが問題です。このような関数リテラルがあると、毎回関数オブジェクトが作られます。ということは、1命令を処理するごとに1つの関数オブジェクトが作られることになります。

最近のJavaScriptエンジンならこれくらいうまいこと最適化してくれるやろ〜〜〜〜〜と思っていたのですが、別にそんなことはなかったようです。ループの外で関数オブジェクトを作ってそれを引数として渡すようにすると速くなりました(3.2秒→2.45秒)。当該のコミットはこれです。

github.com

インライン化の効果は絶大

インライン化はプログラムに対する基本的な高速化手法です。関数呼出があるとき、その関数の中身を全部ベタ書きしてしまいます。これにより、関数呼び出しの処理のオーバーヘッドが削減されます。

しかしこれは人の手でやるようなことではありません。インライン化は、せっかく処理を関数にまとめたのにその関数を使わないことに相当します。多くはコンパイラにより行われるものです。

JavaScriptでも、最近のエンジンは高度に進化しているのでインライン化くらい自動的に行ってくれるだろ〜〜〜〜〜と思っていたのですが、手でインライン化してみたら速くなってしまいました。ということは、速度が欲しかったら時には手でインライン化することも必要ということですね。とても残念な結果です。

インライン化は2回のコミットに分けて行いました。ループ内での関数呼び出しの大部分を排除したところ、1億命令あたりの実行時間は2.4秒から1.4秒となりました。当該のコミットはこれです。ソースがいよいよ汚くなってきました。

github.com

switch文も遅いかも

このプログラムでは、読み込んだ命令がどの命令かの判定をswitch文で行っていました。コンパイルする言語では、switch文はジャンプテーブルにコンパイルされたり二部探索にコンパイルされたりします。そういった最適化がなければswitch文の処理は上から順に見ていくしかありません。

もしかしてJavaScriptではswitch文の最適化が難しいのではないかと思い、手で6段の二部探索(命令コードが6ビットなので)を書いてみたところ少し速くなりました(1.4秒→1.3秒)。

github.com

少し速くなりましたが、コードは爆発しました。

このあたりで嫌になったので今回の高速化は以上です。なお、デバッグ出力を全部消すとさらに1億命令あたり0.2秒くらい速くなるようです。

結論

今回試した中で特に大きな効果を示したのは、関数をインライン化することと何回もオブジェクトを作らないことです。

後者はともかく、前者はもうちょっとどうにかならないものかと思います。JavaScriptは自由な言語ですから色々難しいということも理解していますが。

自分はプログラミングの素人なので分かる人がやればもう少し違うのかもしれません。もし思い違いをしているようならコメントなどで指摘していただけると助かります。