Julia コードの実行

Julia がコードを実行する方法を理解する上で最も難しいのが、コードブロックを実行するときに様々な処理がどのように組み合わさるかを理解する部分です。

通常コードチャンクは様々な処理を通して最終的な結果となります。例えば flisp・AST・C++・LLVM・evaltypeinfmacroexpand・sysimg (システムイメージ)・ブートストラップ・コンパイル・パース・実行・JIT・インタープリタ・ボックス化・ボックス化解除・組み込み命令関数・プリミティブ関数といった処理や概念が登場します。中には聞きなれない名前もあるでしょう。

用語の定義
  • REPL

    REPL は Read-Eval-Print Loop (読み込み・評価・出力ループ) の略です。私たちが普段「コマンドライン環境」と呼んでいるものです。

  • AST

    AST は Abstract Syntax Tree (抽象構文木) の略です。AST はコード構造のデジタル表現であり、操作や実行がしやすいように意味ごとにコードをトークン化したものです。

Julia の実行

10,000 フィート上空から Julia の実行を眺めると次のようになります:

  1. ユーザーが julia を開始します。
  2. ui/repl.c にある C 関数 main() が呼ばれます。この関数はコマンドライン引数を処理して jl_options 構造体を埋め、Julia 変数 ARGS を設定します。その後 src/task.cjulia_init が呼ばれて Julia が初期化されます (このとき以前にコンパイルされた sysimg が読み込まれる可能性があります)。そして最後に Base._start() を呼ぶことで制御を Julia に渡します。
  3. _start() に制御が移った後の処理はコマンドライン引数によって異なります。例えばファイル名が与えられたなら、そのファイルの実行が開始されます。そうでなければ、対話 REPL が開始されます。
  4. REPL とユーザーの対話の詳細は飛ばして、プログラムが何らかのコードブロックを実行することになったとします。
  5. コードブロックがファイルにあるなら jl_load(char *filename) が呼び出され、ファイルの読み込みとパースが行われます。
  6. パースされたコード片 (AST) は eval() に入力され、計算結果に変換されます。
  7. eval() はコード片を受け取り、jl_toplevel_eval_flex() で実行を試みます。
  8. jl_toplevel_eval_flex() は受け取ったコードが "トップレベル" のアクション (usingmodule など) かどうかを判定します。こういったコードは関数の中で使うことができないので、もしコードがトップレベルのアクションなら、jl_toplevel_eval_flex() はコードをトップレベルのインタープリタに渡します。
  9. jl_toplevel_eval_flex() はコードを展開してマクロを取り除き、実行しやすいようコードを "低水準" の AST に変換します。
  10. jl_toplevel_eval_flex() は単純なヒューリスティックを使って AST を JIT コンパイルするか直接解釈するかを決めます。
  11. コードを解釈する処理は大部分が src/interpreter.ceval_value() で行われます1
  12. コードが解釈されるのではなく JIT コンパイルされる場合には、大部分の処理が codegen.cpp にあるコードで行われます。Julia 関数が特定の引数型の組に対して初めて呼ばれると、その関数に対する型推論が実行されます。この情報はコード生成ステップで高速なコードを生成するために利用されます。
  13. いずれユーザーによって REPL が終了されるか、プログラムが終端に達します。すると _start() が返ります。
  14. main() は実行を終える直前に jl_atexit_hook(exit_code) を呼び出します。この関数は Base._atexit() を呼び、Julia から atexit() を使って登録された関数が呼び出されます。その後 jl_atexit_hookjl_gc_run_all_finalizers() を呼び、最後に libuv ハンドルを綺麗に片づけて libuv がフラッシュとクローズを完了させるのを待ちます。

パース

Julia のパーサーは femtolisp (flisp) で書かれた小さな lisp プログラムです。flisp は Julia と一緒に配布されており、ソースコードは src/flisp にあります。

flisp に対するインターフェース関数は jlfrontend.scm で定義されます。この関数を Julia 側で受け取るのは ast.c のコードです。

このステージに関連する他のファイルは julia-parser.scmjulia-syntax.scm です。julia-parser.scm は Julia コードのトークン化と AST への変形を行い、julia-syntax.scm は複雑な AST 表現を解析と実行がしやすい "低水準の" AST 表現に変形します。

Julia を全て再ビルドすることなくパーサーをテストしたいときは、次のようにすればフロントエンドを実行できます:

$ cd src
$ flisp/flisp
> (load "jlfrontend.scm")
> (jl-parse-file "<filename>")

マクロの展開

eval() がマクロに遭遇すると、マクロを含む AST ノードは式の評価が始まる前に展開されます。マクロの展開では主に Julia で書かれた jl_invoke_julia_macro() 関数がマクロの評価を行い、その結果に対して flisp で書かれた低水準形式への変換関数が呼び出されます2

通常マクロの展開は Meta.lower() あるいは jl_expand() の呼び出しにおける最初のステップとして間接的に起動されますが、macroexpand() あるいは jl_macroexpand() を呼び出して直接起動することもできます。

型推論

型推論は compiler/typeinfer.jltypeinf() 関数として Julia で実装されます。型推論 (type inference) とは Julia 関数を詳しく調べることで変数 (および関数の返り値) の型の上界と下界を決定する処理のことです。型推論により後のステージで様々な最適化が可能になります。例えば既知の可変値のボックス化を解除したり、フィールドオフセットや関数ポインタの計算といった実行時操作をコンパイル時に巻き上げることができます。定数伝播やインライン化といった他の処理も型推論時に行われる可能性があります。

用語の定義
  • JIT

    Just-In-Time コンパイルのことです。ネイティブマシン用のコードを必要になった瞬間にメモリ上に生成する処理を言います。

  • LLVM

    低水準仮想機械 (Low-Level Virtual Mathine) というコンパイラの名前の省略形です。Julia は JIT コンパイラに libLLVM というプログラム/ライブラリを使います。Julia の「コード生成 (codegen)」には Julia AST を LLVM 命令に変換する Julia の処理と LLVM 命令をネイティブのアセンブリ命令に変換する LLVM の処理の両方が含まれます。

  • C++

    LLVM が実装されるプログラム言語です。LLVM が C++ で実装されるので、コード生成も C++ で実装されなければなりません。コード生成を除いた Julia ライブラリは C で実装されますが、これは機能を少なくすることで言語をまたいだインターフェースレイヤーとして Julia を使いやすくするためです。

  • ボックス化 (boxing)

    値をラップするデータをアロケートして、ガベージコレクタが追跡するためのデータと型を表すタグを値に付ける処理のことです。

  • ボックス化解除 (unboxing)

    ボックス化の逆です。データの型が (型推論を通して) コンパイル時に分かっているときは、ボックス化解除によってデータの操作が高速に行えるようになります。

  • 総称関数 (generic function)

    複数の「メソッド」から構成される Julia 関数です。メソッドの選択には引数の型シグネチャを使った動的ディスパッチが使われます。

  • 無名関数 (anonymous function)

    名前を持たず、型を使ったディスパッチを行えない Julia 関数のことです。「メソッド」とも呼ばれます。

  • プリミティブ関数 (primitive function)

    C で実装された関数であって名前の付いた関数の「メソッド」として公開されるものを言います (ただし無名関数と同様に、プリミティブ関数は総称関数が持つディスパッチの機能を持ちません)。

  • 組み込み命令関数 (intrinsic function)

    Julia に関数として公開される低水準操作です。組み込み命令関数は関数のようなものであり、加算や符号拡張といった直接表す方法が一つしか存在しない生のビットに対する操作を実装します。ビットを直接操作するので、組み込み命令関数は関数としてコンパイルされた上で値に型情報を割り当てる Core.Intrinsics.box(T, ...) の呼び出しで囲われる必要があります。

JIT によるコード生成

コード生成 (codegen) とは Julia AST をネイティブの機械語に変換する処理のことです。

JIT 環境は src/codegen.cppjl_init_codegen で初期化されます。

Julia のメソッドは emit_function(jl_method_instance_t*) でオンデマンドにネイティブ関数へ変換されます (注意: LLVM バージョン 3.4 以降で MCJIT を使うときは、各関数を新しいモジュールに JIT する必要があります)。この関数は emit_expr() を関数が終わるまで繰り返し呼びます。

codegen.cpp の残りの大部分には特定のコードパターンに対する様々な個別の最適化が書かれています。例えば emit_known_call() は多くのプリミティブ関数を引数型の組み合わせに応じてインライン化する方法を知っています3

コード生成の他の部分は様々なヘルパーファイルで処理されます:

ブートストラップ

新しいシステムイメージを作成する処理を「ブートストラップ (bootstrap)」と呼びます。

この単語の語源は「自力でやり遂げる (pulling oneself up by the bootstraps)」という慣用句です。ブートストラップはごく少数の関数や定義が利用できる状態から始めて完全な機能を持った環境を作り上げるというアイデアを指します。

システムイメージ

システムイメージはいくつかの Julia ファイルを事前コンパイルしてまとめたアーカイブです。Julia に付属する sys.jl というファイルがシステムイメージの例であり、このファイルは sysimg.jl を実行して出来上がる環境 (型・関数・モジュールといった定義された全ての値) をファイルに書き込むことで作成されます。つまり sys.jl には特定の固定されたバージョンにおける Main, Core, Base モジュール (およびブートストラップの終了時点で環境内に存在したもの全て) が含まれます。このシリアライザ/デシリアライザは src/staticdata.cjl_save_system_image/jl_restore_system_image で実装されます。

システムイメージファイルが存在しない (jl_options.image_file == NULL) なら、コマンドライン引数に --build が渡されたということであり、このとき実行の最終的な結果が新しいシステムイメージファイルとなります。Julia の初期化では最低限の Core, Main モジュールだけが作成され、現在のディレクトリにある boot.jl という名前のファイルがまず評価されます。その後 Julia はコマンドライン引数に渡されたファイルを最後まで実行し、最終的に出来上がった環境を将来の Julia の実行で開始地点として使うためのシステムイメージファイルとして保存します。


  1. 訳注: 関数の名前を修正した (参照: コミット c47aa)。[return]

  2. 訳注: 英語版には「fl_invoke_julia_macro 関数を使って flisp でマクロが評価される」と書いてあるが、現在のバージョンではこうなっていない (参照: コミット d7169)。現在のバージョンの処理に合うよう本文を修正した。[return]

  3. 訳注: 現在のバージョンに emit_known_call 関数は存在しない (参照: コミット a1ee8)。[return]

広告