より大きなフローグラフ言語の例
トレーシングと部分評価の比較 Part4
このエントリは部分評価とトレーシングの比較シリーズの四つ目、そして最後のエントリです。
長い道のりを歩んでいます。
シリーズの最初では小さなフローグラフ言語のインタプリタとその部分評価器をお見せしました。
二つ目では同じ言語にトレーサがどのように動作するかと、部分評価とどのように関係するかについてお見せしました。
三つ目ではトレースのためのオプティマイザについて説明しました。
この最後のエントリでは、トレーシングと部分評価の二つの別々のアプローチの例を挙げ、その意味から比較と対比します。
フローチャート言語のプログラムは、これまで見てきたものはかなり小さいのですが、今回は大きなプログラムの例で示したいと思います。それは非常に単純なバイトコードセットのインタプリタです。
部分評価器がインタプリタにどのような処理を行うかを見ていきます。そして、トレーサが同様に何を行うかも見ていきます。
このシリーズで使われている全てのコードはこちらにあります:
http://paste.pocoo.org/show/550282/ (トレースをプリントするよりよい方法などのいくつかの小さなプログラムを追加しています。)
バイトコードインタプリタ
フローグラフ言語でプログラムを記述することは痛みを伴いますが、今まで見てきた小さなものよりもう少し興味深い例を与えるためにまだ書かなければいけません。例は、非常に簡単なレジスタマシンのバイトコードインタプリタで、その一つであるアキュムレータは実際に全ての操作が実行されます。
この言語のオペコードは;
- jump_if_a: アキュムレータが非ゼロの場合、ターゲットアドレスにジャンプします
- mov_a_r0, mov_a_r1, mov_a_r2: アキュムレータの値をそれぞれのレジスタに移します
- mov_r0_a, mov_r1_a, mov_r2_a: レジスタの値をアキュムレータに移します
- add_r0_to_a, add_r1_to_a, add_r2_to_a: レジスタの値をアキュムレータに加算します
- decr_a: アキュムレータの値をデクリメントします
- return_a: アキュムレータの値をプリントしてプログラムを終了します
インタプリタは現在のプログラムカウンタの一にあるオペコードを読み、if 文までの一連の(長い)バイトコードをディスパッチし正しいオペコードを行するメインループを持ちます。
その後、次のオペコードに対しても同様の処理を行います。
擬似コードとしてのフローグラフ言語のソースコードの一部です:
bytecode_loop:
opcode = bytecode[pc]
pc = pc + 1
c = opcode == 'jump_if_a'
if c goto op_jump_if_a else goto not_jump_if_a
# select the right bytecode via a long series of if statements
not_jump_if_a:
c = opcode == 'mov_a_r0'
if y goto op_mov_a_r0 else goto not_mov_a_r0
not_mov_a_r0:
c = opcode == 'mov_a_r0'
if y goto op_mov_a_r1 else goto not_mov_a_r1
...
# bytecode implementations
op_mov_a_r0:
r0 = a
goto bytecode_loop
op_jump_if_a:
c = a == 0
target = bytecode[pc]
pc += 1
if c goto bytecode_loop else goto op_jump_if_a_jump
op_jump_if_a_jump:
pc = target
goto bytecode_loop
...
そして実際に Prolog の fact として動きます。(完全な実装は上記リンクを辿ると見つけられます):
% bytecode dispatch loop
block(bytecode_loop,
op2(opcode, readlist, var(bytecode), var(pc),
op2(pc, add, var(pc), const(1),
op2(c, eq, var(opcode), const(jump_if_a),
if(c, op_jump_if_a, not_jump_if_a))))).
% select the right bytecode via a long series of if statements
block(not_jump_if_a,
op2(c, eq, var(opcode), const(mov_a_r0),
if(c, op_mov_a_r0, not_mov_a_r0))).
block(not_mov_a_r0,
op2(c, eq, var(opcode), const(mov_a_r1),
if(c, op_mov_a_r1, not_mov_a_r1))).
...
% bytecode implementations
block(op_jump_if_a,
op2(c, eq, var(a), const(0),
op2(target, readlist, var(bytecode), var(pc),
op2(pc, add, var(pc), const(1),
if(c, bytecode_loop, op_jump_if_a_jump))))).
block(op_jump_if_a_jump,
op1(pc, same, var(target),
promote(bytecode, bytecode_loop))).
block(op_mov_a_r0,
op1(r0, same, var(a), jump(bytecode_loop))).
...
ブロックはメインのディスパッチループです。
バイトコードリストからプログラムカウンタの一にあるオペコードを読み出し、
現在のオペコードを様々な既存のオペコードと比較する長い一連の if 文を持ちます。
インタプリタの完全なコードは上のリンクを辿るとあります。
インタプリタのバイトコードは実際には非常に複雑なプログラムを許可しませんが、以下のように数値を二乗するプログラムを書くことに使えます:
mov_a_r0 # r0 = a
mov_a_r1 # r1 = a
# 2:
mov_r0_a # r0--
decr_a
mov_a_r0
mov_r2_a # r2 += a
add_r1_to_a
mov_a_r2
mov_r0_a # if r0!=0: goto 2
jump_if_a 2
mov_r2_a # return r2
return_a
バイトコードインタプリタの部分的な評価
最初のエントリの部分評価器は、簡単にバイトコードインタプリタを部分評価できます。
静的な入力は、上記のように二乗の計算を行うバイトコードとプログラムカウンタの初期値です。
動的な入力はアキュムレータの内容(二乗する値)です。これは次のように行えます:
?- bytecode_square(B),
Env = [bytecode/B, pc/0],
do_pe(bytecode_loop, Env, Label),
REnv = [a/16, r0/0, r1/0, r2/0],
interp(jump(Label), REnv), listing(block).
256
:- dynamic block/2.
<lots of generated code>
部分評価器が処理した結果生成されたコードは若干読みづらいです。
以下のように様々なパスを含んでいるためです:
...
block(op_return_a1, print_and_stop(var(a))).
block(not_decr_a1, jump(op_return_a1)).
block(not_add_r2_to_a2, jump(not_decr_a1)).
block(not_add_r1_to_a2, jump(not_add_r2_to_a2)).
block(not_add_r0_to_a3, jump(not_add_r1_to_a2)).
block(not_mov_r2_a3, jump(not_add_r0_to_a3)).
block(not_mov_r1_a5, jump(not_mov_r2_a3)).
block(not_mov_r0_a5, jump(not_mov_r1_a5)).
block(not_mov_a_r27, jump(not_mov_r0_a5)).
block(not_mov_a_r18, jump(not_mov_a_r27)).
block(not_mov_a_r09, jump(not_mov_a_r18)).
block(not_jump_if_a11, jump(not_mov_a_r09)).
block(bytecode_loop12, jump(not_jump_if_a11)).
block(op_mov_r2_a2, op1(a, same, var(r2), jump(bytecode_loop12))).
...
すなわち、何もせずに別のブロックにジャンプするブロックが沢山あるということです。
散在するいくつかのブロックは実際のオペレーションを含んでいます。
手動で出力されたコードを綺麗にし、以下のようなものができあがりました。
(このクリーンアップの手順は、良い部分評価システムであれば部分評価の後に評価器自身が行うでしょう):
block(bytecode_loop1,
op1(r0, same, var(a),
op1(r1, same, var(a),
op1(a, same, var(r0),
op2(a, sub, var(a), const(1),
op1(r0, same, var(a),
op1(a, same, var(r2),
op2(a, add, var(a), var(r1),
op1(r2, same, var(a),
op1(a, same, var(r0),
op2(c, eq, var(a), const(0),
if(c, bytecode_loop11, op_jump_if_a_jump1)))))))))))).
block(bytecode_loop11,
op1(a, same, var(r2),
print_and_stop(var(a))).
block(op_jump_if_a_jump1,
op1(a, same, var(r0),
op2(a, sub, var(a), const(1),
op1(r0, same, var(a),
op1(a, same, var(r2),
op2(a, add, var(a), var(r1),
op1(r2, same, var(a),
op1(a, same, var(r0),
op2(c, eq, var(a), const(0),
if(c, bytecode_loop11, op_jump_if_a_jump1)))))))))).
このコードから何が見えてくるのでしょうか?
部分評価器は 最初のオペコード
mov_a_r0 と
mov_a_r1 に対応する
bytecode_loop1 ブロックを生成し、一回のループの反復で一緒に処理されます。
そして、メインループのコピー(
op_jump_if_a_jump1 ラベル)か、結果を出力して停止する
bytecode_loop1 へとジャンプします。
バイトコードを処理した結果の残留コードを実行します:
アキュムレータの値を二乗し、出力します。
使われる全てのバイトコードとプログラムカウンタはなくなります。
何故部分評価器は同じように見えるメインループの二つのコピーを生成したのでしょうか?
その理由は二つ目のコピーにある追加の静的情報
target = 2 がわかったためです。
target はインタプリタのソースにあるジャンプ先を指定する変数ですが、この処理の間はとても簡単です。
この追加の静的情報は残留コードに何の影響も及ぼしませんが、同じコードが無駄に生成されます。
これは、過剰な特殊化の例です。
インタプリタをトレースする
このセクションでは、インタプリタのトレースを試みたときに何が起こるかをお見せします。
一回の反復で停止してしまうため、トレースを生成する自然な方法有用ではありません。
この問題を回避する方法に注目しました。
このセクションで説明している問題は、
Tracing the meta-level: PyPy's tracing JIT compilerというペーパーのコアとなっています(ペーパー中では例より少し高度なバイトコードインタプリタを使っています)。
インタプリタのトレースするために
bytecode と
pc の二つの変数を常にプロモートすることは、上記のコードから
bytecode_loop ブロックを置き換えるのに有用です。
それらを知らずにトレースを生成することはあまり意味がなく、面白みもありません。
これは、上記の部分評価の例で静的にそれらの変数を作ることと似ています:
block(bytecode_loop,
promote(bytecode, bytecode_loop_promote_bytecode)).
block(bytecode_loop_promote_bytecode,
promote(pc, bytecode_loop_promote_pc)).
block(bytecode_loop_promote_pc,
op2(opcode, readlist, var(bytecode), var(pc),
op2(pc, add, var(pc), const(1),
op2(c, eq, var(opcode), const(0),
if(c, op_jump_if_a, not_jump_if_a))))).
...
インタプリタの残りの部分は変更していません。
インタプリタのトレースするために、 単純な
bytecode_loop ラベルから開始します。
インタプリタ中の
bytecode_loop ラベルは一番高い頻度で飛び先として使われるためです。 (プロファイラは簡単に確立する可能性があります):
?- bytecode_square(B),
A = 16, Env = [bytecode/B, pc/2, a/A, r0/A, r1/A, r2/0],
do_trace(bytecode_loop, Env).
trace
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
guard_value(pc,2,[],bytecode_loop_promote_pc)
op2(opcode,readlist,var(bytecode),var(pc))
op2(pc,add,var(pc),const(1))
op2(c,eq,var(opcode),const(jump_if_a))
guard_false(c,[],op_jump_if_a)
op2(c,eq,var(opcode),const(mov_a_r0))
guard_false(c,[],op_mov_a_r0)
op2(c,eq,var(opcode),const(mov_a_r1))
guard_false(c,[],op_mov_a_r1)
op2(c,eq,var(opcode),const(mov_a_r2))
guard_false(c,[],op_mov_a_r2)
op2(c,eq,var(opcode),const(mov_r0_a))
guard_true(c,[],not_mov_r0_a)
op1(a,same,var(r0))
loop
opttrace
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
guard_value(pc,2,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]],bytecode_loop_promote_pc)
op1(a,same,var(r0))
op1(bytecode,same,const([mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]))
op1(pc,same,const(3))
op1(opcode,same,const(mov_r0_a))
op1(c,same,const(1))
loop
256
B = [mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a, mov_a_r2, mov_r0_a|...],
A = 16,
Env = [bytecode/[mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a|...], pc/2, a/16, r0/16, r1/16, r2/0]
生成されたこれらのトレースはとても短いです。
bytecode と
pc のプロモートとともに開始し、続いてバイトコードの 2 番目に位置する命令であるオペコード
mov_r0_a を実行します。
そして
pc をインクリメントし、ループの開始に戻ります。
最適化されたトレースを見ると、本質的に役に立たないことは明らかです。
それらは一回の反復でのみ実行されます。二回目の反復では
pc は 3 になり、
guard_value が冒頭で失敗してしまうためです。
この問題はバイトコードディスパッチループのトレースを一回以上行うことで解決できます。
この手法はメタトレーシングと呼ばれます。
この挙動を得るために、このシンプルな例では、開始するのに十分な (かつ終了する) トレースを別のラベル
op_jump_if_a_jump で行っています。
このラベルは、インタプリタが
jump_if_a バイトコードを実行し、ジャンプしたときにヒットします。
実行されたバイトコードプログラム上のレベルのループでは、一つのジャンプにすぎません。
従って、このラベルからトレースすることでバイトコード上の全てのループがトレースされます。
全てのループとは、制御フロー言語のバイトコードディスパッチループに潜在的に含まれる多くの反復です。
生成結果は以下のとおりです:
?- bytecode_square(B),
A = 16, Env = [bytecode/B, pc/11, a/A, r0/A, r1/A, r2/0, target/2],
do_trace(op_jump_if_a_jump, Env).
trace
op1(pc,same,var(target))
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop)
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
guard_value(pc,2,[],bytecode_loop_promote_pc)
op2(opcode,readlist,var(bytecode),var(pc))
op2(pc,add,var(pc),const(1))
op2(c,eq,var(opcode),const(jump_if_a))
guard_false(c,[],op_jump_if_a)
op2(c,eq,var(opcode),const(mov_a_r0))
guard_false(c,[],op_mov_a_r0)
op2(c,eq,var(opcode),const(mov_a_r1))
guard_false(c,[],op_mov_a_r1)
op2(c,eq,var(opcode),const(mov_a_r2))
guard_false(c,[],op_mov_a_r2)
op2(c,eq,var(opcode),const(mov_r0_a))
guard_true(c,[],not_mov_r0_a)
op1(a,same,var(r0))
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
guard_value(pc,3,[],bytecode_loop_promote_pc)
op2(opcode,readlist,var(bytecode),var(pc))
...
lots of operations ommitted
...
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop_promote_bytecode)
guard_value(pc,9,[],bytecode_loop_promote_pc)
op2(opcode,readlist,var(bytecode),var(pc))
op2(pc,add,var(pc),const(1))
op2(c,eq,var(opcode),const(jump_if_a))
guard_true(c,[],not_jump_if_a)
op2(c,eq,var(a),const(0))
op2(target,readlist,var(bytecode),var(pc))
op2(pc,add,var(pc),const(1))
guard_false(c,[],bytecode_loop)
loop
opttrace
op1(pc,same,var(target))
guard_value(bytecode,[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],[],bytecode_loop)
guard_value(pc,2,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]],bytecode_loop_promote_pc)
op1(a,same,var(r0))
op2(a,sub,var(a),const(1))
op1(r0,same,var(a))
op1(a,same,var(r2))
op2(a,add,var(a),var(r1))
op1(r2,same,var(a))
op1(a,same,var(r0))
op2(c,eq,var(a),const(0))
guard_false(c,[bytecode/[mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a],pc/11,opcode/jump_if_a,target/2],bytecode_loop)
op1(bytecode,same,const([mov_a_r0,mov_a_r1,mov_r0_a,decr_a,mov_a_r0,mov_r2_a,add_r1_to_a,mov_a_r2,mov_r0_a,jump_if_a,2,mov_r2_a,return_a]))
op1(pc,same,const(11))
op1(opcode,same,const(jump_if_a))
op1(target,same,const(2))
op1(c,same,const(0))
loop
256
B = [mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a, mov_a_r2, mov_r0_a|...],
A = 16,
Env = [bytecode/[mov_a_r0, mov_a_r1, mov_r0_a, decr_a, mov_a_r0, mov_r2_a, add_r1_to_a|...], pc/11, a/16, r0/16, r1/16, r2/0, target/2] .
よくなったように見えます。
トレースはインタプリタで実行する、上記例で示した二乗関数のループの中の全てのバイトコードに対応します。
最適化されたコードは二つの(
bytecode がまだ二乗関数のなかの一つであるかと、
pc が 2 であるかどうかをチェックする)ガードから始まります。そして、実際に計算するオペレーションのみ行います。
バイトコードディスパッチは行われず、従ってインタプリタ実行のオーバヘッドは全て取り除かれます。二つの
guard_value オペレーションから離れて開始されます。
トレースの中のたくさんの割り当ては不要です。
例えば
r0,
r1,
r2 レジスタと加算器
a 間のコピーなどです。
これらは SSA 形式を利用したより賢い最適化を用いることで簡単に解決できます。
インタプリタに関する結論
部分評価とメタトレーシングのどちらも例で用いた二乗を計算するバイトコードをインタプリタオーバヘッドのない、本質的なな計算でお見せした形式に変換する際に使われます。
素直な部分評価器はジャンプを行うだけのような沢山の追加のブロック生成しますが、後処理工程で解決可能です。
トレーサそのものは無駄に短いトレースを生成しますが、別の地点からトレースを開始する簡単なトリックを施すことでかなり良くなります。
実際のメタとレーシングシステムでは、メタトレーサはインタプリタの作者のために、どのバイトコードがバックエンドのジャンプに対応するかをマークするためのの方法が必要になります。
また、トレースをキャッシュするだけでなく自動的にトレースが開始されるように良く統合されている必要があります。
加えて、よく失敗するガード対処するしたり、失敗したガードに新しいトレースを接続する必要があります。
ただし、それらの全てはこの一連のプログエントリで発表した机上の空論に過ぎません。
高度な結論
トレーシングと部分評価の類似点に関するいくつかの高レベルな結論:トレーシングと部分評価は、自動的にインタプリタのオーバヘッドを減らすという似た問題に対処しようとしました。これらのアプローチはわずかに異なります。
トレーシングはいくつかの追加の情報をプロセスに保持するのみで、通常の評価機構にとても近いです。
しかし、トレーサの中で使われるオプティマイザは部分評価器ととても似た構造をとっています。
オプティマイザの仕事は、とても単純でオペレーションを線形リストにするのみです。制御フロー全てに対処する必要はありません。
トレーシングの検出は部分評価器の一部を利用し、 (「それらの中の評価できるものを評価するのみで、それ以外は残す」ということです)、部分評価されなかった(展開を制御する)パーツをより実用的なメカニズムによって置き換えます。
そのメカニズムは、実際のプログラムで実行される典型的な制御フローパスの選択を観測します。
同時に、トレーサの焦点はループに当たっています。
それらはプログラムの実行時間の殆どを占めているためです。
トレーシングの別の視点では、どのパスを見ているかの情報を提供する神託(実際に実行されたプログラム)によって部分評価器の制御コンポーネントを置き換えます。
ここ示したような非常に簡単なインタプリタでは既に効果が現れています。
単純な部分評価器は二つの全く同じループを生成するなどの過剰な特殊化を行います。
トレーサはそのような挙動をせず、初期化するオペコードではないループ自体のコードだけを生成します。
このシリーズでは、以上のようなものを作りました。お付き合いありがとうございます。
また、ここにこれらのPostをする前に一貫して良いフィードバックをくれた Samuele と Sven に感謝を示します。
