型推論
型推論の動作
型推論とは入力の型から他の値の型を導出する処理のことです。Julia が採用する型推論のアプローチはブログ記事 Inference Convergence Algorithm in Julia と Inference Convergence Algorithm in Julia - Revisited で説明されています1。
compiler.jl のデバッグ
Julia セッションを開始してから compiler/*.jl を編集 (例えば print を挿入) したときは、base ディレクトリに移動して include("compiler/compiler.jl") を実行することで現在のセッションの Core.Compiler を新しいバージョンで置き換えることができます。このテクニックを使えば編集ごとに Julia を再ビルドするよりもずっと高速な開発が可能です。
あるいは Revise.jl パッケージのコマンド Revise.track(Core.Compiler) をセッションの最初で実行して、コンパイラに対する変更を監視させることもできます。Revise のドキュメントで説明されるように、こうするとファイルを編集して保存した瞬間にコンパイラに対する変更が反映されます。
型推論のコードを見ていくときに最初に見るべき関数は typeinf_code です。convert(Int, UInt(1)) に対する推論を実行するデモを示します:
# メソッドの取得
atypes = Tuple{Type{Int}, UInt} # 引数の型
mths = methods(convert, atypes) # メソッドが唯一であることは確認しなければならない。
m = first(mths)
# typeinf_code を呼ぶために必要な変数を作成する。
params = Core.Compiler.Params(typemax(UInt)) # 引数は世界時を表す。
# typemax(UInt) -> 「最も最近の」
sparams = Core.svec() # このメソッドは型パラメータを持たない。
optimize = true # 型推論時の最適化を全て実行する。
# types = Tuple{typeof(convert), Type{Int}, UInt}
types = Tuple{typeof(convert), atypes.parameters...}
Core.Compiler.typeinf_code(m, types, sparams, optimize, params)
デバッグ中に MethodInstance が必要になったときは、上のコードに含まれる変数を使って Core.Compiler.specialize_method を呼んでください。CodeInfo オブジェクトは次のようにすると取得できます:
# convert(Int, ::UInt) に対する CodeInfo を取得する:
ci = (@code_typed convert(Int, UInt(1)))[1]
インライン化アルゴリズム (inline_worthy)
インライン化の主な処理は ssa_inlining_pass! で行われます。一方で「この関数がインライン化されないのはなぜ？」という疑問を持っているなら、見るべきは isinlineable とそれが呼び出す inline_worthy です。isinlineable は様々な特殊ケースを持ちます (性能のために重要な +, *, min, max, iterate, cconvert といった関数など2)。主たるインライン化の判定は inline_worthy で行われ、インライン化すべきであればこの関数から true が返ります。
inline_worthy はコストモデルを実装し、コストの "安い" 関数がインライン化されます。正確に言うと、インライン化しないで呼び出しを行うのにかかる時間と比較したときに期待される実行時間が大きすぎないときにインライン化が起こります。このコストモデルはこの上なく単純であり、重要な情報をいくつも無視しています: 例えば全ての for ループは一度だけ実行されるものとして解析され、if ... else ... end のコストは全ての分岐の和となります。さらに、このコストモデルが実際の実行時コストをどの程度正確に予測しているかをテストするための関数スイートが現段階では存在しないことも知っておくに値する情報です。ただしインライン化アルゴリズムを変更したときの実行時間の変化については、BaseBenchmarks.jl が間接的な情報を大量に提供します。
インライン化の判断で使われるコストモデルの基礎となるのがルックアップテーブルです。このテーブルは add_tfunc 関数を使って推定コスト (単位は CPU サイクル) を Julia の組み込み命令関数にそれぞれ割り当てることで構築されます。この推定コストは一般的なアーキテクチャにおける値を元にしています (詳細は Agner Fog による解析を参照してください)。
この低水準なルックアップテーブルは多くの特殊ケースで補強されます。例えば :invoke 式 (入力と出力の型が事前に推論されている関数呼び出し) には固定コスト (現在 20) が割り当てられますが、:call 式 (組み込み命令関数でも組み込み関数でもない、多重ディスパッチを必要とする関数呼び出し) には Params.inline_nonleaf_penalty によって設定される値 (現在 1000) が割り当てられます。なお、この値は多重ディスパッチの生のコストを "真面目に" 推定した値ではなく、多重ディスパッチのコストが非常に高いことを反映させるためのヒューリスティックに過ぎません。
statement_cost という関数が関数内の文をそれぞれ解析し、関数全体のコストが計算されます。この関数を自分で試す方法の概略を次に示します。ここで f は任意の関数であり、tt は f の引数の型を表すタプルにしたものです:
# fill(3.5, (2, 3)) に対するコストを計算するデモ
f = fill
tt = Tuple{Float64, Tuple{Int,Int}}
# コンパイラと対話するために必要なオブジェクトを作成する。
params = Core.Compiler.Params(typemax(UInt))
mi = Base.method_instances(f, tt)[1]
ci = code_typed(f, tt)[1][1]
opt = Core.Compiler.OptimizationState(mi, params)
# 全ての文のコストを計算する。
cost(stmt::Expr) = Core.Compiler.statement_cost(stmt, -1, ci, opt.sptypes,
opt.slottypes, opt.params)
cost(stmt) = 0
cst = map(cost, ci.code)
# 出力
31-element Array{Int64,1}:
0
0
20
4
1
1
1
0
0
0
⋮
0
0
0
0
0
0
0
0
0
出力は Vector{Int} であり、それぞれの要素が ci.code の各文の推定コストを表します。ci に対してはインライン化処理が行われるので、その結果が推定コストにも影響することに注意してください。