ホーム » Juliaの速さの核心に迫る〜インタプリタ、コンパイラ、JITコンパイラ〜

Juliaの速さの核心に迫る〜インタプリタ、コンパイラ、JITコンパイラ〜

このエントリーをはてなブックマークに追加

新星プログラミング言語Julia。

Rubyの動的さとC言語の速度を両立させた、公認会計士の資格を取得したジャニーズJr.みたいな、そんなのアリかよって感じの言語だ。

Juliaの宣伝文句はすごい。引用してみよう。

僕らが欲しい言語はこんな感じだ。まず、ゆるいライセンスのオープンソースで、Cの速度とRubyの動的さが欲しい。Lispのような真のマクロが使える同図象性のある言語で、Matlabのように分かりやすい数学の記述をしたい。Pythonのように汎用的に使いたいし、Rの統計処理、Perlの文字列処理、Matlabの線形代数計算も要る。シェルのように簡単にいくつかのパーツをつなぎ合わせたい。チョー簡単に習えて、超上級ハッカーも満足する言語。インタラクティブに使えて、かつコンパイルできる言語が欲しい。

（そういえば、C言語の実行速度が必要だってのは言ったっけ？）

こんなにもワガママを言った上だけど、Hadoopみたいな大規模分散コンピューティングもやりたい。もちろん、JavaとXMLで何キロバイトも常套句を書きたくないし、数千台のマシンに分散した何ギガバイトものログファイルを読んでデバッグするなんて論外だ。幾層にも重なった複雑さを押しつけられるようなことなく、純粋なパワーが欲しい。単純なスカラーのループを書いたら、一台のCPUのレジスターだけをブン回す機械語のコードが生成されて欲しい。A*Bと書くだけで千の計算をそれぞれ千のマシンに分散して実行して、巨大な行列の積をポンと計算してもらいたい。

型だって必要ないなら指定したくない。もしポリモーフィックな関数が必要な時には、ジェネリックプログラミングを使ってアルゴリズムを一度だけ書いて、あとは全ての型に使いたい。引数の型とかから自動的にメソッドを選択してくれる多重ディスパッチがあって、共通の機能がまったく違った型にも提供できるようにして欲しい。これだけのパワーがありながらも、言語としてシンプルでクリーンなものがいい。

これって、多くを望みすぎてるとは思わないよね？

https://www.geidai.ac.jp/~marui/julialang/why_we_created_julia/index.html

さて、今回はJuliaの速さに注目する。JuliaはC言語並みに速い。なぜそんなに速いのだろうか？

私はぼんやりと、JuliaがJITコンパイルを採用しているからだと思っていた。だって、JITコンパイルというのはJavaやC#でお馴染みだ。JavaやC#は速い。C言語と同じくらいのオーダーの速度だ。オーダーが同じというのは同じくらいの桁という意味だ。私は言語間の速度の比較で2倍違うとかいう議論はあまり意味がないと思う。[1]もちろん、個々のアプリとしては2倍差が非常に重要になることはありうる。だから、CもJavaもC#もJuliaも同じくらいの速度だとみなす。

一方、PythonやRubyは遅い。C言語より1桁とか2桁遅い。これはオーダーが違うので明確に遅い。そしてそれは彼らがインタプリタ方式だからだ。そうだよね？

JuliaはインタプリタではなくJITコンパイルを採用しているから速いのだと、そう思っていた。

しかし、よく考えたら事はそう簡単ではないと思えてきた。PythonやRubyの開発者は、散々速度が遅いと文句を言われ続けてきたのだ。私ですらPythonやRubyが遅いという話は耳にタコができるほど聞いている。言語設計者はさぞうんざりしていることだろう。JITコンパイルにしてC言語並みに速くなるのであれば、PythonもRubyもとうの昔にそうしているのではないか。「うるさい速度マニアどもめ、恐れ入ったか！ガッハッハ！」

しかし、そうはなっていないのだ。

それに、よく考えたらJuliaって動的型付け言語なのだ。Javaや.NETは静的型付け言語だ。静的言語は、いきなり機械語にすることもできるが、あえて中間コードで一旦止めておいて、実行時に機械語にする。これは静的言語のJITコンパイルだ。これはよくわかる。

しかし、動的言語のJITコンパイルってなんだろう？考えてみたがよく分からない。それってインタプリタと何が違うの？本当にそれがJuliaが高速な秘訣なんだろうか？

そこで、今日はコンパイラ、インタプリタあたりの話題を踏まえながら、Juliaの速度の核心に迫る。最初に言っておくが、迫るだけで到達するとは言っていない。個人的にここが重要かなという結論は出すが、それが答えだと言い切る自信は全くない。

だいたい、自分の書いたアプリだって、速度の改善は当てずっぽうでやるな、プロファイリングしろボトルネックを計測しろと口を酸っぱくして言われるのだ。ある言語が別の言語より速い理由など、簡単にわかるはずもない。設計思想も言語仕様もアーキテクチャもユーザーの文化も全然違うのだ。

言い訳も終わったので本題に入ろう。

機械語への翻訳

ソースコードをコンパイルすると実行ファイルができる。ソースコードは文字列だ。実行ファイルは機械語だ。ソースコードから何をどうやったら機械語に翻訳できるのだろうか。

ソースコード から機械語へ変換するには、一般的に次のような工程を踏む。

  1. ソースコードに対して、字句解析・構文解析と呼ばれる工程を経て、抽象構文木を生成する。
  2. 抽象構文木から、機械語を生成する。

今回の主題は2の機械語の生成である。まずは抽象構文木について簡単に説明する。その後、機械語の生成の方式について代表的な数パターンを説明する。

抽象構文木

以前の記事でも触れたが、ここでも簡単に触れておく。ちなみに以前の記事の丸コピーである。共通部分としてくくりだした方がいいかと思ったが、面倒なので見送る。こうやってソースコードは汚れていくのだ。

例えば、 “x = 1 + 2” という式を考える。「変数xに1+2の結果を代入する」という意味である。この式はプログラムコードとして与えられる。文字列の”x = 1 + 2″である。このままではただの文字の並び(‘x’, ‘=’, ‘1’, ‘+’, ‘2’)である。ここから何かの意味を抽出したデータ構造に変換する必要がある。意味を抽出して初めて、機械語に翻訳できてコンピュータで実行できるのである。ここで言う、「意味を抽出したデータ構造」が抽象構文木である。

さて、”x = 1 + 2″という文字の並びから、どのような工程を経て、「変数xに1+2の結果を代入する」という意味を持つ抽象構文木に変換するかは重要な問題である。重要な問題ではあるが、私の手には余るので解説しない。興味のある方は、「構文解析」と言う単語で検索されるとよい。人によっては人生が変わるくらい広く深い世界が広がっている。私はその後の人生は保証しない。入門書としては「Go言語でつくるインタプリタ」という本がおすすめである。

ともかく、構文解析という工程を終えると、”x = 1 + 2″という文字の並びから、「変数xに1+2の結果を代入する」という意味の抽象構文木となる。これを図示したのが下記のイメージである。assignというのは、代入を意味するとしておく。この情報があれば、どの順番で何の演算を行えば、所望の結果が得られるのか一目瞭然である。

静的コンパイル方式

いわゆる「コンパイル」と呼ばれる処理だ。ソースコードを書き、コンパイルし、実行ファイルを作成する。例えばC言語がこの方式を採用している。実行時の情報(ソフトウェア起動時の引数や設定データ、画面からの入力情報など)がない状態で、ソースコードのみから機械語への変換を行う。

静的コンパイル方式の重要な特徴の一つに、対象言語が静的型付けであることが挙げられる。なぜなら通常、機械語のレベルでは、同じような演算であっても型によって命令語が異なるからだ。同じ数値であっても、整数値と浮動小数点値では、コンピュータの取り扱いが全く異なる。そのため、同じ加算であっても、整数と浮動小数点小数の加算は全く異なる命令となるのだ。静的に機械語に翻訳できるためには、プログラムを書いた時点で、それぞれの文や式がどのような型を持っているかわかっている必要がある。

動的型付けの言語だと、静的コンパイル方式はやりたくてもできない。

静的型付けの言語は、静的コンパイル方式によって直接機械語に翻訳できるし、後述するインタプリタ方式で間接的に翻訳することもできる。

インタプリタ

上で述べた静的コンパイル方式と対比させるべきは動的コンパイル方式なのだが、先にインタプリタ方式を解説する。

インタプリタ方式に対しては誤解が多いので、ここで一度整理しておく。インタプリタ方式は「ソースコードを逐次機械語へ変換しながら実行すること」を意味すると考えられていることが多いが、これは正確ではない。この説明はどちらかというと動的コンパイルの説明に近い。インタプリタ方式と(静的/動的)コンパイル方式では、機械語を生成する主体が違うのだ。

インタプリタ方式の場合は、処理対象のソースコード (例えばRuby)の処理を模倣する仮想機械を作成する。仮想機械は普通は処理対象のソースコードとは別の言語(例えばC言語)で書かれる。仮想機械が請け負う仕事の範囲は言語によって微妙に異なるが、計算処理そのものを実行するところだけは共通している。それがインタプリタ方式の定義と言ってもいい。

何のことだかよく分からないかもしれないので、簡単な例を出そう。

極小のインタプリタ

今から極めて簡単な仮想の言語とその言語処理系をインタプリタ方式で作る。仮想の言語の前は作者の私の名前をとってmuu言語としよう。インタプリタはPythonで作ることにしよう。

muu言語は2つの数の足し算しかできないとても可愛らしい言語だ。”1 + 2″とか”5 + 10″とかいった感じのソースコードとなる。変数は使えない。このソースコードを構文解析すると、2つのノードを持つ抽象構文木となる。それぞれのノードには与えられた数字が入っている。

#muu言語の構文解析器
def parse(src):
    left_str, right_str = src.split("+")
    left = int(left_str.strip())
    right = int(right_str.strip())
    return Add(left, right)

#muu言語の抽象構文木
class Add:
    def __init__(self, left, right):
        self.left = left
        self.right = right

muu言語には2つの数の足し算しか存在しないので、抽象構文木として考える必要があるのもAddクラスだけだ。さて、仮想機械はmuu言語に依頼された足し算を実行する必要がある。作成時に抽象構文木を受け取り、evaluateというメソッドで足し算を実行する、そんな仮想機械を考えてみよう。

#muu言語の仮想機械
class MuuMachine:
    def __init__(self, add):
        self.__add = add

    def evaluate(self):
        return self.__add.left + self.__add.right

muu言語がインタプリタによってどのように処理されるかのイメージが下記になる。

#muu言語の処理の流れ
src = "5 + 10"  #ソースコード 
a = parse(src) #aにAdd(5, 10)が入る
m = MuuMachine(a) #仮想機械の作成
result = m.evaluate() #仮想機械の実行
print(result) #結果の表示。15となる。

やれ抽象構文木だの仮想機械だの大それた名前はついているが、中身はてんで大したことはない。言語処理系とは何事だと言いたい気持ちはわかる。どうか石を投げないで欲しい。一応最低限のことはやっているのだ。説明させて欲しい。

Addクラスは抽象構文木の役割を果たしている。非常に大きな制約があり、leftとrightの2本しかノードがないし、ノードには数値しか入れられない。しかしまあ、最低限の抽象構文木ではある。

MuuMachineクラスは仮想機械の役割を果たしている。Addクラス以外の抽象構文木が入ってくることに全く対応していないが、何らかの抽象構文木を評価するという意味で、最低限の仮想機械ではある。その証拠に、evaluateするとちゃんと加算の結果を返してくれるのだ。

どうだろうか？だんだん立派な言語処理系という気がしてきただろう。友人のお子さんの小学校の入学祝いに贈ってあげるといい。

さて、この言語処理系が拍子抜けするほど簡単だった理由は、下記の部分にある。

#仮想機械
class MuuMachine:
    ...
    def evaluate(self):
        return self.__add.left + self.__add.right

加算の評価を丸ごとPythonに渡している。「えー、それはずるいよ」と言っているそこの君ね、よく聞きなさい。これがインタプリタの本質なのだ。

確かに、muu言語は何もしていないに等しい。足し算しかできない言語なのに、足し算すらPythonに任せているのだ。とんでもないぐうたら言語だ。みじめで、しみったれた、負け犬言語だ。足も臭いに違いない。きっと作者に似たのだろう。

しかし、待ってほしい。muu言語は今後、飛躍的に発展していくことになる。Addクラスだってノードを任意の数持てるようになるだろうし(“1 + 2 + 3 + 4″みたいに書きたいよね？）、ノードに別のAddクラスを入れられるようにだってなるだろう(“(1 + 2) + 3 + (4 + (5 + 6))”みたいに書きたいよね？)。何と立派な言語だろうか。その勇姿は大空を駆け巡る美しいペガサスのようだ。きっと作者に似たのだろう。

そうしたら、構文解析器は複雑になるだろうし、MuuMachineだってきっと忙しく働くはずだ。ノードを巡回しながら、入っているのが数値なのかAddクラスなのか判断しながら、正しい結果が計算されるように調整しながら加算をしていくことになる。

しかし、最後の最後、数値の加算を行う部分に関しては、やはり基層の言語(この場合はPython)に任せるしかないのだ。それをどうしても自分でやるというのであれば、自前で機械語を生成することになる。それはもはやインタプリタではなく、コンパイラだ。

となると、インタプリタ方式では、実際の計算処理を行う機械語はどこへ行ったのか？基層の言語で書かれた仮想機械のコードが機械語に翻訳されているのだ。

仮に足したい2つの数が5と10だったとしても、pythonで書かれた下記の式は、おそらく実行時に単なる 5 + 10 以上のことを実行している。

self.__add.left + self.__add.right
  • MuuMachineのメンバ変数に__addがあるか？
  • __addはleftとrightというメンバを持っているか？
  • それらがあったとして、leftとrightに入っている値の型は？
  • どちらも整数なら整数同士の加算を行おう。
  • どちらも小数なら小数同士の加算を行おう。
  • 一方が整数で一方が小数なら整数を小数に変換してから小数同士の加算を行う処理を行おう。

Pythonに処理を任せる以上、それは仕方のないことだ。いくら今から計算する足し算は整数同士の足し算で小数を考慮する必要はないと分かっていたとしても、Pythonにそれを伝える手段は存在しない。

このように、インタプリタ方式では、どのような機械語が生成されるかは基層の言語に直接的に依存している。インタプリタの基層の言語としてC言語が採用されていることが多いのは、C言語が指示された以上の余計な機械語を生成しないからだろう。

ここまで見てきたように、インタプリタ方式のメリット・デメリットは明白である。

インタプリタ方式は基層の言語にお任せできる部分が多いため、コンパイル方式より作るのが簡単である。また、基層の言語が動く環境なら動作するのも嬉しい。これがメリットだ。

一方で、速度性能は基層の言語で頭打ちになる。頭打ちになるどころか、だいたいずっと遅くなる。これがデメリットだ。他にもいろいろあるだろうが、代表的なのはこんなところだ。

動的コンパイル方式

動的コンパイル方式とは、実行時に機械語を生成する方式のことだ。JITコンパイルは動的コンパイル方式の一種と言われるようだ。JITコンパイル以外の動的コンパイルについてはよく知らないので、JITコンパイルについて話すことにする。

JITコンパイルとは、Just In Timeコンパイルの略だ。実行時に機械語を生成する。Javaや.NET Frameworkでもお馴染みの方式だ。

Javaや.NET Frameworkの言語は、静的型付きの言語である。そのため、静的コンパイルは可能である。しかし、あえて最後までコンパイルを行わずに、静的なコンパイルでは中間言語で書かれた中間コードを生成するにとどめているのだ。

中間言語とは、文字通りソースコードと機械語の中間に位置する言語だ。よくILと略される。Intermediate Languageの略だ。ソースコードは人間が読むものだ。機械語はCPUが読むものだ。では中間コードを読むのは誰だろうか？

中間言語を読むのは仮想機械だ。中間言語で書かれた中間コードを読むためのプログラムだ。Javaの場合、JVM(Java Virtual Machine)と略されることが多い。Javaの中間コードはJVMが読む。.NETの中間コードは.NETの仮想機械であるCLR(Common Language Runtime)が読む。仮想機械は中間コードを実際のCPUに対応した機械語に翻訳する。

おや、仮想機械だって？インタプリタにも登場したぞ？そう、JITコンパイル方式は、静的コンパイル方式とインタプリタ方式のいいとこ取りなのだ。もっと言うと、静的コンパイル方式の利点を取り込んだインタプリタ方式がJITコンパイル方式なのだ。

Javaを例に出すのがわかりやすいだろう。Javaの主要な目標の一つに、“Write Once, Run Anywhere”、「一度書けば、どこでも動く」というものがある。一度Javaコードを書くと、WindowsでもMacでもLinuxでも、はたまた電化製品の組み込み環境でも、同じように動いて欲しい。素晴らしい目標だ。

そうなると、静的コンパイル方式では厳しい。ターゲットのCPUが違うとなると、当然命令も違う。存在する全てのCPUで条件分岐して、適切な機械語が実行されるような実行ファイルを作ると言うのも一つのアイデアだが、破綻は目に見えている。

そのようなわけでJavaでは当初インタプリタ方式がとられたようである。各実行環境には、Javaのインタプリタをインストールしてもらう。その上で、Javaコードをインタプリタで動かす。Javaインタプリタは、実行環境に合った適切な機械語にコンパイルされているため問題なくJavaコードの動きを模倣できる。これで万事解決だ。

ところがこれには実行速度が遅いという問題があったようだ。それでインタプリタではなく、実行時に機械語を生成するJITコンパイル方式に変えたことで、速度の向上に計算したらしい。このおかげで、インタプリタ方式のメリットである「実行環境から独立したポータビリティ」と、静的コンパイル方式の「実行速度」を手に入れることができたのだ。

なお、Microsoftの.NET Frameworkも同様に中間言語を使った仮想機械方式だが、こちらはJavaとは目的が異なる。Javaは複数のCPUをターゲットにしていたが、.NETはWindowsのみをターゲットにしていた。[2]最近はマルチプラットフォーム対応にも力を入れている

.NET Frameworkがサポートしていたのは、複数の言語だ。C#、VB.NET、F#、J#などなど。これらの.NETファミリー言語は、同じ中間コードに翻訳される。別の言語で書かれたメソッドもdll経由で簡単に呼び出せるように設計されている。.NET Frameworkの巨大なライブラリが簡単に再利用可能なのだ。

他に、JITコンパイルの別の利点として、機械語の生成を実行時まで遅らせることで、まさに実行時の環境に最適な機械語を生成するということが可能になる。CPUの特性に応じて機械語を変えることができるし、CPUの使用率やメモリの空き状況に応じて、生成する機械語を変えるということも可能である。もちろん、実行時の処理のため機械語の生成にあまり時間をかけるわけにはいかないので、制約は大きいが、原理的にはそのようなメリットもある。

このように、JITコンパイルには様々なメリットがある。JuliaはLLVMというツールを使って、この方式を実現している。

LLVMというのは、Juliaとは独立したツールだ。LLVMはLLVM用の中間コードを受け取り、機械語を出力する。Juliaの評価器はプログラムの実行時に、Juliaのソースコード からLLVMへの入力となる中間コードを生成している。LLVMは中間コードを受け取り即座に機械語を出力する。その機械語は即座に実行される。これがJuliaのJITコンパイルだ。

Juliaはなぜ速いのか

そろそろ基礎知識も出揃ってきたので、Juliaがなぜ速いのかについて本腰を入れて考えよう。とはいえ、どこから考えればいいかよく分からない。

過去にJuliaを遅くする試みがなされていれば、何が原因で速くなっているかの切り分けができるのだが、生憎のところ速い言語を遅くする試みは人気がない。

そこで、Julia以外の言語の試行錯誤の事例を手掛かりにしよう。遅い言語を速くしようという試みはたくさんあるからだ。

今から、速い言語の代表としてJavaを考える。遅い言語の代表としてはRubyを考える。

さて、JavaとRubyとJuliaの比較をしてみよう。

JavaRubyJulia
静的型付け動的型付け動的型付け
JITコンパイル方式インタプリタ方式JITコンパイル方式
速い遅い速い

これを見たら、静的型付けか動的型付けは速度に依存せず、JITコンパイル方式なのかインタプリタ方式なのかが重要なように見える。本当だろうか？

Javaの事例

先ほど、Javaは当初インタプリタ方式だったが、速度の問題でJITコンパイル方式に変えて速くなったという話をした。ここを少し深掘りしよう。

一口にインタプリタ方式と言っても、いろいろな方式がある。最も素朴な方式は、抽象構文木を直接評価する方式のインタプリタだった。これは実装が非常にシンプルなのだが、あまり効率的ではないという問題がある。抽象構文木を巡回しながら値を評価するので、時間がかかるのだ。抽象構文木を巡回するということのイメージはわくだろうか？

足し算の抽象構文木を考えよう。muu言語が少し成長して、入れ子になった足し算をサポートしたとしよう。(1 + (2 + 3)) + ((4 + (5 + 6)) + 7) みたいな形だ。この時、抽象構文木は次のようになる。

これは一例だが、このような足し算構文木の計算を実行するためには、どのようにすればいいだろうか？

少し用語のを導入する。丸の部分をノードという。てっぺんのノードをルートノードといい、枝分かれした分岐の先端のノードをリーフノードという。

まず、ルートノードには、「+」という記号があり、これは足し算の構文木だということを示している。次に子ノードを見てみる。このとき、両方の子ノードに数値が入っていればそれでOKだ。足してあげればそれでおしまいだ。muu言語がこれだ。

しかし、子ノードを見ると、またしても「+」記号があるとする。そうすると、これは子ノードが抽象構文木だということなので、子ノードに潜る必要がある。そこからさらに子のノードを見ると、数値だったり「+」記号だったりする。「+」記号であれば、それは抽象構文木ということで、さらに潜る必要がある。延々と潜って行って、両方のノードが数値になる先端(リーフノード)まで行き当たると、ようやく足し算が実行できる。足し算の結果を手土産に上のノードに戻る。そうすると、そのノードが計算できるかもしれない。計算できればさらに上に戻る。しかし、もう一方のノードが抽象構文木であれば計算できないので、今度はそちらを下に辿っていく。先端に辿り着いたら計算し上に戻っていく。

こうして、計算できるまで下のノードに下りていき、下のノードの計算ができればその計算結果を引っ下げて上のノードに戻るということを、繰り返しやっていき、ルートノードの計算が終わると、最終的には元々やりたかった足し算が完了する。

このように、実行時にいろいろな判断をしながら抽象構文木を行ったり来たりして計算するのはいかにも効率が悪そうということがわかるだろう。

これを改善した方式として、抽象構文木からバイトコードと呼ばれる中間コードを生成して、インタプリタはバイトコードを解釈するという方式である。バイトコードというのは抽象構文木とは違い、一直線に並んだ命令と数値の列である。命令と数値が適切な順番で並べられているため、端から順に何も考えずに命令を実行すれば所望の結果が得られるというものになっている。こうしておくと、命令の実行時に条件判断が入らないし、行ったり来たりもないため、高速なのだ。

私は最初、インタプリタ方式のJavaが遅かったと聞いて、ソースコードから逐次変換していたために遅かったのだと勘違いしていた。ソースコードからインタプリタ渡すまでの、字句解析、構文解析、抽象構文木の作成あたりに時間がかかったと思っていたのだ。しかし、この特徴は動的コンパイルの特徴であり、静的コンパイル可能なJavaでその必要はない。

実際にはインタプリタ方式のJavaは、そのあたりの処理は全て行い、なおかつバイトコード形式の中間コードを事前に生成するところまで行っていたようである。それを実行環境で解釈するという方式がとられていたようなのだ。インタプリタ方式では考えられる最高の方式だ。それでも遅かったようなのだ。

そして、最後の最後、中間コードを仮想機械が実行するのではなく、仮想機械が機械語を生成・実行する。これが必要だったようなのだ。

おそらくJITコンパイル方式に変更するという決断を下す前に、バイトコード設計やインタプリタの最適化は相当入念に行われたことだろう。それでも越えられない壁がそこにはあったようなのだ。

なるほど、インタプリタ方式とJITコンパイル方式には大きな差があるようである。しかし、それだけなのだろうか？

Rubyの事例

最初の方で話したが、インタプリタ方式からJITコンパイル方式に変えるだけで高速化するのであれば、Rubyだってとっくにそうしているだろう。動的言語だからJITコンパイルできないのだろうか？いや、そんなことはない。動的言語はコーディング時に型を指定する必要はないが、実行時にはきちんと型を持つのだ。値そのものが型を持つからだ。なので、実行時に機械語に変換できない道理はないのだ。

ではなぜ、RubyはJITコンパイルを行わないのか？

実はRubyはJITコンパイルを行っているのだ。Ruby2.6でMJITという仕組みが導入された。これは面白い仕組みで、中間コードとしてC言語を使う。Javaや.NETの中間コードはかなり機械語チックだが、MJITはC言語なのだ。Rubyのバイトコードを解釈するRubyのインタプリタは、何度も実行される処理に対してはバイトコードと同じ動作をするC言語のソースコード を吐き出し、それを機械語にする。公式によるとRuby2.5と比べて1.7倍の高速化が実現されたそうだ。素晴らしい。

https://www.ruby-lang.org/ja/news/2018/12/25/ruby-2-6-0-released/

しかし、C言語やJavaのレベルには程遠いのは確かだ。こうなってくると、JITコンパイル「だから」高速だというのは怪しくなってくる。JITコンパイルは高速化の大きな要因の一つだが、それだけではなさそうなのだ。

ここでMJITが何をしているかを紹介している面白い記事があるので紹介しよう。

Rubyの新しいJIT「MJIT」で早速遊んでみた（翻訳）

原文はこちらだそうである。

簡単に抜粋すると、筆者は

a = a * 16807 % 2147483647

というコードを含むrubyプログラムを書き、MJITがどのようなC言語を生成するかを観察したようである。

最初の乗算で行われるすべての内容を以下のセクションに示します。

ローカル変数aを取得する（スタックにpushされている）

被乗数16807をスタックにpushする（object_id 0x834fで表されている）

スタック上の2つの値を引数としてvm_opt_multを呼び出す

上記のような処理を実行するC言語コードが出力されるようである。気になるのは、乗算を実行してくれるvm_opt_multというものが何者かということだ。

ruby 2.6.3のソースコードからvm_opt_multを抜粋すると次のような処理になっている。じっくり読む必要はないが、if文の条件式に注目してほしい。FIXNUMだとか、FLONUMだとか書いている。これは変数の型を判定しているのだ。乗算の引数の型を判定し、処理を振り分けるようになっている。

static VALUE
vm_opt_mult(VALUE recv, VALUE obj)
{
    if (FIXNUM_2_P(recv, obj) &&
    BASIC_OP_UNREDEFINED_P(BOP_MULT, INTEGER_REDEFINED_OP_FLAG)) {
    return rb_fix_mul_fix(recv, obj);
    }
    else if (FLONUM_2_P(recv, obj) &&
         BASIC_OP_UNREDEFINED_P(BOP_MULT, FLOAT_REDEFINED_OP_FLAG)) {
    return DBL2NUM(RFLOAT_VALUE(recv) * RFLOAT_VALUE(obj));
    }
    else if (SPECIAL_CONST_P(recv) || SPECIAL_CONST_P(obj)) {
    return Qundef;
    }
    else if (RBASIC_CLASS(recv) == rb_cFloat &&
         RBASIC_CLASS(obj)  == rb_cFloat &&
         BASIC_OP_UNREDEFINED_P(BOP_MULT, FLOAT_REDEFINED_OP_FLAG)) {
    return DBL2NUM(RFLOAT_VALUE(recv) * RFLOAT_VALUE(obj));
    }
    else {
    return Qundef;
    }
}

ここがあまりRubyのパフォーマンスが向上しない部分なのではないかと思う。機械語にしているとは言え、この関数が生成する命令文は単なる乗算の命令文よりもはるかに長大なものになるだろう。

型による実行時の条件分岐が足を引っ張っているのではないか、ということが、Rubyの事例からの推測だ。動的言語であるという点も、無視できないポイントのようだ。

Pythonの事例

Rubyでの推測を補強するべく、Pythonの事例を引用しよう。

PythonにもJITコンパイルを行うという試みがある。本家の処理系であるCPython以外に、PyPyという処理系やnumbaというライブラリがあり、これはJITコンパイルを行うのだ。これは本家のCPythonよりも圧倒的に速いという。数十倍速いこともあるらしい。これは文句なしに速いと言っていいだろう。

PyPyは、Pythonの機能制限版であるRPythonというものを対象にした処理系だ。RPythonの特徴は、型推論が可能な機能に絞っているということだ。型推論・・・Juliaでも聞いたことあるだろう。プログラマが明示的に型を指定しなくても、実行時に与えられた値が持つ型から、論理的に各パーツの型を特定していく機能のことである。推論であって推測ではないので、厳密に定まる。Pythonの一部機能がこの型推論と相性が悪いらしいので、そのあたりの機能を取っ払ったのがRPythonで、RPythonの処理系の1つが型推論を行うPyPyであるという。

numbaも同様に型推論を行う。PyPyと違い別の処理形ではなく、本家のPythonで利用できるライブラリだ。関数に@jitというデコレータをつけると型推論してJITコンパイルをしてくれるという優れものだ。まあ、いろいろ注意点もあるようだが、あまり深掘りはしない。numbaの適用範囲もまた、PyPyと同じくPythonの一部機能に限られている。

さらにはCythonというものもある。Cythonというのは型宣言できるPythonとでも言うべき言語で、基本的にはPythonと同様に型宣言せずにコーディングできるのだが、高速化したいところに関しては型を宣言することができると言うものだ。Cythonの処理系はPythonで書かれているらしいので、Pythonにできることは何でもできる(はずだ)。Cythonも高速化に型を利用している。

そう、型なのだ。型を演算時に判定する必要があるかどうかが、実行速度に大きく影響しているようなのだ。型宣言や型推論など、型に関する支援があるかどうかが分かれ目なのだ。

上の方に書いた表を見直す必要がある。速い言語になるには、型支援とJITコンパイルが必要なようだ。

Java(旧)JavaRuby(2.6)Julia
静的型付け静的型付け動的型付け動的型付け
型支援あり型支援あり型支援なし型支援あり
インタプリタ方式JITコンパイル方式JITコンパイル方式JITコンパイル方式
遅い速い遅い速い

Juliaの型推論と最適化

Juliaの型推論と最適化について見てみよう。Juliaの非常に優れた特徴の一つに、低レイヤのコードを容易に確認できるというものがある。Juliaコードが、どのような過程で機械語に変換されていったかわかる機能が、標準でついているのだ。使うのは次の4つ、@code_lowered、@code_typed、@code_llvm、@code_nativeだ。後のほうに行くほど機械語に近付いていく。

試しに、次のような極めて簡単な関数doubleがどのような機械語に変換されるか見てみよう。

[
function double(x)
    return 2 * x
end

ここからのサンプルを実行する際、Replならそのまま打ち込めば良いが、スクリプトファイルに記述して実行するときには、

using InteractiveUtils

を忘れるとエラーになるので注意してほしい。

@code_lowered

@code_loweredは、コードを「低レベル」な呼び出しに変換してくれる。低レベルというのは程度が低いという意味ではなく、機械語に近いという意味だ。

ソースコード上でdouble(3)と書いたものが、@code_loweredでどのように変換されるか見てみよう。

@code_lowered double(3)
CodeInfo(
1 ─ %1 = 2 * x
└──      return %1
)

2とxをかけた結果を%1という入れ物に入れて、%1をreturnする、と読める。これはまあそんなものかな、くらいのものだろう。ひとまず次に移ろう。

@code_typed

@code_typedから、俄然面白くなる。この時点でJuliaは型を推論するのだ。

@code_typed double(3)
CodeInfo(
1 ─ %1 = Base.mul_int(2, x)::Int64
└──      return %1
) => Int64

先ほどとの違いは、mul_intという呼び出しが現れていることだろう。::Int64と書いているので、これが整数の掛け算だということがわかる。

一方、引数に小数である3.0を渡すとどうなるか？

まず、@code_loweredは何も変わらない。

@code_lowered double(3)
CodeInfo(
1 ─ %1 = 2 * x
└──      return %1
)

しかし、@code_typedの結果は変わる。

@code_typed double(3.0)
CodeInfo(
1 ─ %1 = Base.sitofp(Float64, 2)::Float64
│   %2 = Base.mul_float(%1, x)::Float64
└──      return %2
) => Float64

sitofpという処理で、2をFloat64に変換して、その後、小数の掛け算を行う処理になっている。このように、同じ関数呼び出しであっても、引数に入ってきた値の型に応じて、@code_typedの時点で、どの型の命令を呼び出せば良いか判明しているのだ。

@code_llvm

@code_llvmは、LLVMコンパイラへの入力である、LLVM中間コードを表示する。

@code_llvm double(3)

結果は次のようになる。デバッグ情報は消している。この規模だと逆に邪魔だからだ。

define i64 @julia_double_802(i64) {
top:
   %1 = shl i64 %0, 1
  ret i64 %1
}

かなり機械語のようになってきた。ここで注目すべきは、

   %1 = shl i64 %0, 1

だ。%0は引数で、この場合は3が来ることになる。shlとは何かというと、シフト演算だ。シフト演算とは、メモリ上の数値を1ビット右や左にずらすことだ。なぜこんな演算が登場したか。

これは、整数の掛け算/割り算を高速に行う手法なのだ。左に1ビットシフトすると2倍の数値になる。右に2ビットシフトすると、2で割った数値になる。ビット演算は掛け算よりも高速なので、与えられている数値が整数で、かつ、掛ける数か割る数が2の倍数のときには高速化に有効な手法なのだ。こんな芸当は型が整数であると分かっていなければ絶対にできない。

次に引数が小数のケースを見てみよう。

@code_llvm double(3.0)

結果は次のようになる。

define double @julia_double_809(double) {
top:
   %1 = fmul double %0, 2.000000e+00
  ret double %1
}

今度はfmulという命令になった。小数の掛け算の命令だ。fmul直後のdoubleは関数名のdoubleではなく型名のdoubleだ。%0は同じく引数、掛ける数は2を小数に変換した数だ。普通は整数の掛け算だと、これに似た mul という命令になるが、先ほどは一方の数が2だったので、気を利かせてさらに高速な shl にしてくれたわけだ。

@code_native

@code_nativeはLLVMが生成する機械語を表示してくれる。これに関しては雰囲気だけ見ておこう。JuliaというよりはLLVMの領域の話だからだ。

@code_native double(3)
.section        __TEXT,__text,regular,pure_instructions
leaq    (%rdi,%rdi), %rax
retq
nopw    %cs:(%rax,%rax)
nop

leaqというのは、メモリ操作のためのアドレス演算命令で、普通は計算には使われないが、うまく利用することである種の算術演算が高速化されるというものだ。わかりやすそうな日本語の文献として下記のサイトを見つけたので興味があれば参照してほしい。ちなみに私は理解していない。

https://ocaml.org/learn/tutorials/performance_and_profiling.ja.html

(訳注: ここは一見わかりやすい add 命令(普通の整数演算)でなく lea 命令(メモリ操作のためのアドレス計算を転用して演算する) 使っていることを指している。が、 もっと古い CISC マシンである メインフレームでも lea 相当の命令(LA)で 加算をするのは普通なので、 x86 設計チームもこういう使いかたは知っているだろう。 実際に add も lea も Pentium 以降は1サイクルで動作する最速動作の命令であり、 一命令で加算と定数減算をやっている lea 命令を使わない場合、 add した後に別途1を引かないといけない (sub命令も必要)分遅くなるのだ)

面白いのは、Juliaは型推論の末にビットシフトをしろとLLVM中間コードで命令していたが、LLVMがさらに気を利かせて、こっちの方が速いぜと別の命令を下していることである。それぞれの層で最適化を行っているのだ。

@code_native double(3.0)
.section        __TEXT,__text,regular,pure_instructions
vaddsd  %xmm0, %xmm0, %xmm0
retq
nopw    %cs:(%rax,%rax)
nop

vaddsdというのは小数の足し算の命令だ。自分同士の足し算を行って、自分自身に代入している。自分自身との足し算ということはジャスト2倍ということだ。Juliaが生成したLLVM中間コードでは、整数の2倍ではなくて小数の2.0倍だったが、LLVMの内部では、再度整数の2とみなして掛け算より足し算したほうが速いと判定されたらしい。

このように、型の情報をフル活用して非常に高速な機械語が生成されたことがわかる。さらにLLVMも気を利かせて色々な最適化を施してくれている。

Juliaは引数からどこまでの情報を判定しているか？

Juliaは引数の型の情報を使って型推論していることはわかった。では、Juliaは引数の情報をどこまで使って最適化するのだろうか？

次の例を見てみよう。先ほどのdoubleと違い、引数を2つとる。

function multiply(x, y)
    return x * y
end

次のように引数を与えると、doubleとmultiplyは同じ計算をする。

double(3) #6
multiply(2, 3) #6

@code_typedの結果は次のようなもので、大した違いはない。

#@code_typed double(3)
CodeInfo(
1 ─ %1 = Base.mul_int(2, x)::Int64
└──      return %1
) => Int64

#@code_typed multiply(2, 3)
CodeInfo(
1 ─ %1 = Base.mul_int(x, y)::Int64
└──      return %1
) => Int64

ただ、@code_llvmを見ると、差が出ていることがわかる。doubleでは高速なshl命令が使われているが、multiplyでは通常の掛け算の mul命令だ。

;@code_llvm double(3)
define i64 @julia_double_817(i64) {
top:
   %1 = shl i64 %0, 1
  ret i64 %1
}

;@code_llvm multiply(2, 3)
define i64 @julia_multiply_818(i64, i64) {
top:
   %2 = mul i64 %1, %0
  ret i64 %2
}

いずれのケースでも2 * 3を計算するが、2という情報を活かしたのは、前者のみだったことがわかる。このことは、Juliaは引数の値の型は考慮するが、引数の値まで考慮した最適化はしないということを示している。一方、コード中の即値としてして書かれた値は最適化に活用するようである。

しかし、私はここは声を大にして言いたいが、だからと言って関数に定数を埋め込みまくれと言いたいわけでは決してない。もっと言うと、常に機械語を意識してプログラムを書けと言いたいわけでもない。

関数で何を引数として受け取り、何をハードコーディングするかは、速度を基準として決めるべきではない。まずはこう言った速度のあれこれは忘れよう。関数として最も自然なインターフェースが何かを考えよう。使いやすくて読みやすい関数を作ろう。独立性が高くて柔軟な関数を作ろう。その上でプログラムを動かし、遅いようであればボトルネックを特定しよう。

Juliaには非常に便利な@timeマクロや@profileマクロがある。これはもう信じがたいくらいに手軽で便利だ。これを使ってボトルネックを特定したら、初めて低レベルのコードを見てみよう。順序を間違えてはならない。

とはいえ、何かの役に立つかもしれないから知っておいても損はないだろう。

Juliaのその他の最適化

Juliaの賢い最適化をもう少し鑑賞してみよう。

最適化手法の代表的なものの一つに、機械語にするよりも前の段階で、できる部分の計算はやってしまおうと言うものがある。たとえば、コード中に 2 * 3 * 4 という掛け算があるとき、CPUで物理的に乗算命令を実行するのではなく、 2 * 3 * 4 = 24 だと論理的に計算してしまったほうが速いと言うテクニックのことである。これを定数の畳み込みという。

次のようなコードを考えよう。squareは引数を2乗する関数、sum_squaredは2乗した結果を100回ループして合計する関数である。

function square(x)
    return x * x
end

function sum_squared(n)
    s = 0
    for i = 1:100
        s += square(n)
    end
    return s
end

これに対して、sum_squared(5)と呼び出すと、5 * 5 = 25を100回足し合わせるので2500になる。このsum_squared(5)の低レベルコードを見てみよう。

@code_lowered と @code_typed はそこまで変わったところはない。ループは条件分岐とgotoに置き換えられているが、100回ループしたら処理を終わるのだな、というあたりは変わっていない。

#@code_lowered sum_squared(5)
CodeInfo(
1 ─       s = 0
│   %2  = 1:100
│         @_4 = Base.iterate(%2)
│   %4  = @_4 === nothing
│   %5  = Base.not_int(%4)
└──       goto #4 if not %5
2 ┄ %7  = @_4
│         i = Core.getfield(%7, 1)
│   %9  = Core.getfield(%7, 2)
│   %10 = s
│   %11 = Main.square(n)
│         s = %10 + %11
│         @_4 = Base.iterate(%2, %9)
│   %14 = @_4 === nothing
│   %15 = Base.not_int(%14)
└──       goto #4 if not %15
3 ─       goto #2
4 ┄       return s
)

#@code_typed sum_squared(5)
CodeInfo(
1 ─       goto #7 if not true
2 ┄ %2  = φ (#1 => 0, #6 => %5)::Int64
│   %3  = φ (#1 => 1, #6 => %11)::Int64
│   %4  = Base.mul_int(n, n)::Int64
│   %5  = Base.add_int(%2, %4)::Int64
│   %6  = (%3 === 100)::Bool
└──       goto #4 if not %6
3 ─       goto #5
4 ─ %9  = Base.add_int(%3, 1)::Int64
└──       goto #5
5 ┄ %11 = φ (#4 => %9)::Int64
│   %12 = φ (#3 => true, #4 => false)::Bool
│   %13 = Base.not_int(%12)::Bool
└──       goto #7 if not %13
6 ─       goto #2
7 ┄ %16 = φ (#5 => %5, #1 => 0)::Int64
└──       return %16
) => Int64

ところが、@code_llvmは面白い。ループが消え失せて、%0の引数を2乗した次は、それに100を掛けているだけだ。100回足し算するなら、100を掛けたらいいんでしょうというスマートな判断だ。

;@code_llvm sum_squared(5)
define i64 @julia_sum_squared_815(i64) {
top:
    %1 = mul i64 %0, %0
  %2 = mul i64 %1, 100
  ret i64 %2
}

次に、sum_squaredに少し手を加えて、square(n)の部分を square(i * n)としてみよう。適当に変えてみただけで、何か深い意味のある計算というわけではない。

function sum_squared(n)
    s = 0
    for i = 1:100
        s += square(i * n)
    end
    return s
end

@code_loweredと@code_typedはあまり変わらないので割愛する。@code_llvmは次のようになる。

;@code_llvm sum_squared(5)
define i64 @julia_sum_squared_815(i64) {
top:
  %1 = mul i64 %0, %0
  %2 = mul i64 %1, 338350
  ret i64 %2
}

338350というのは、1から100までの数字を2乗して足し上げた数である。square(i * n) = square(i) * square(n)で、後者square(n)はiのループ内で定数なので外に出されて、iのループを計算した結果338350と掛け算されたのだ。

さらに、square(i * n)の部分をsquare(i + n)に変えてみよう。これは先ほどみたいに簡単にはくくり出せないはずだ。

function sum_squared(n)
    s = 0
    for i = 1:100
        s += square(i + n)
    end
    return s
end

@code_llvmを見ると、次のようになっている。

;@code_llvm sum_squared(5)
define i64 @julia_sum_squared_815(i64) {
top:
  %1 = add i64 %0, 1
  %2 = mul i64 %1, %1
  %3 = mul i64 %2, 100
  %4 = mul i64 %0, 9900
  %5 = add i64 %3, %4
  %6 = add i64 %5, 338250
  ret i64 %6
}

(i + n) * (i + n) = i*i + 2*i*n + n*n を i を1から100にわたって足し上げると、上記コードの定数の部分が出てくるのだろう。定数の畳み込みにより、ループがただの四則演算に変わってしまった。型推論とは関係ないが、Juliaが強力な最適化機構を持っていることがわかる。

型推論できないとき

型推論ができないときの動きを見てみよう。Juliaには、const指定されていないグローバル変数については型推論ができないという仕様がある。ということは、const指定されていないグローバル変数にアクセスする関数を作ってみれば、型推論できない時にどのような低レベルコードを生成するかわかるだろう。

次のような関数を考える。

a = 0

function assign_a(x)
    global a = x
end

この上なく簡単だ。assign_a(1)はどのような低レベルコードを出すだろうか？

@code_typedはおとなしい。::Anyは型推論が効いていないことを示している。

#@code_typed assign_a(1)
CodeInfo(
1 ─     (Main.a = x)::Any
└──     return x
) => Int64

そしてこれが@code_llvmだッ！！！

;@code_llvm assign_a(1)
define i64 @julia_assign_a_763(i64) {
top:
  %gcframe = alloca %jl_value_t*, i32 3, align 16
  %1 = bitcast %jl_value_t** %gcframe to i8*
  call void @llvm.memset.p0i8.i32(i8* align 16 %1, i8 0, i32 24, i1 false)
  %2 = call %jl_value_t*** inttoptr (i64 4553897056 to %jl_value_t*** ()*)() #4
  %3 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 0
  %4 = bitcast %jl_value_t** %3 to i64*
  store i64 4, i64* %4
  %5 = getelementptr %jl_value_t**, %jl_value_t*** %2, i32 0
  %6 = load %jl_value_t**, %jl_value_t*** %5
  %7 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %8 = bitcast %jl_value_t** %7 to %jl_value_t***
  store %jl_value_t** %6, %jl_value_t*** %8
  %9 = bitcast %jl_value_t*** %5 to %jl_value_t***
  store %jl_value_t** %gcframe, %jl_value_t*** %9
  %10 = call %jl_value_t* @jl_box_int64(i64 signext %0)
  %11 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 2
  store %jl_value_t* %10, %jl_value_t** %11
  call void @jl_checked_assignment(%jl_value_t* nonnull inttoptr (i64 4654483200 to %jl_value_t*), %jl_value_t* %10)
  %12 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %13 = load %jl_value_t*, %jl_value_t** %12
  %14 = getelementptr %jl_value_t**, %jl_value_t*** %2, i32 0
  %15 = bitcast %jl_value_t*** %14 to %jl_value_t**
  store %jl_value_t* %13, %jl_value_t** %15
  ret i64 %0
}

うぎゃぎゃぎゃー！と叫びたくなるようなコードだ。先ほどまでの美しいLLVM中間コードを返しておくれ。

機械語の例は出さないが、雰囲気は似たようなものだ。この例を見ることで、型推論が高速なコードにいかに寄与しているか想像できると思う。

おわりに

長々と書いてきたが、ようやく終わりである。おさらいしよう。

Juliaの速さを支えているのは、型推論とJITコンパイルだ。おそらくどちらが欠けてもいけないのだが、より言語仕様に深く影響するのは型推論だ。

PythonやRubyは型推論と相性の悪い機能があるため、今一つ速度が出せていない。それはPythonにおいて、言語機能を制限すれば型推論と高速化に成功しているという事例からもうかがえる。Juliaは言語設計の段階から型推論と相性の悪い機能を注意深く排除してきたのだろう。

では、PythonやRubyにあって、Juliaには存在しない機能はあるのだろうか？PythonとRPythonの機能の差分に答えはあるはずだ。それが型推論を実現するために捨て去られた機能だからだ。それが何なのか、私にはよくわかっていない。私はPythonの高度な機能についてはよくわからないのだ。

しかし、Juliaには極めて強力なマクロ機能がある。私はなんとなく、そういった機能もマクロが解決してくれるのではないかとぼんやり思っている。思っているというよりは願っていると言ったほうが正確だ。どうなんだろう？誰か知っていたら教えて欲しい。

References

References
↑1 もちろん、個々のアプリとしては2倍差が非常に重要になることはありうる。
↑2 最近はマルチプラットフォーム対応にも力を入れている