PyPy Status Blog JA

より大きなフローグラフ言語の例

2012-02-24T12:31:00.002+09:00

より大きなフローグラフ言語の例

トレーシングと部分評価の比較 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))).
...

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 に感謝を示します。

FlowGraph 言語のトレースの最適化

2012-02-09T15:36:00.001+09:00

原文はこちら

トレーシングと部分評価の比較 Part3

これは部分評価とトレーシングを比較するシリーズの三つ目のエントリです。最初のエントリでは、小さ FlowGraph 言語をインタプリタとともに紹介し、FlowGraph 言語の部分評価器をお見せしました。二つ目のエントリでは、トレーサが同じ言語にどのように働くかと、部分評価とトレーサの二つの実行がどのように関係するのかをお見せしまし、プロモーションの機能をトレーサに追加しました。
このエントリでは、トレーサによって生成されたトレースをどのように最適化するかをお見せし、部分評価のオプティマイザの構造とトレーサのオプティマイザの構造を比較します。
このエントリで使われているソースコードはここにあります: http://paste.pocoo.org/show/547304/

トレースの最適化

前回のエントリで、どのようにスペシャルモードでの制御フローグラフプログラムの実行によるガードとともに線形化したトレースを生成するかを見ました。トレースはいつも loop 文で終わり、開始地点にジャンプします。トレーサはインタプリタが実行したオペレーションのログを取るだけなので、出力されるトレースには余計なオペレーションが含まれてしまいます。一方で、トレースはプロモーションといくつかの決定を通して、最適化に利用できるいくつかの実行時の値も含みます。以下の例は、前回のエントリのサンプルのプロモーションによって生成されたトレースです。

op2(c,ge,var(i),const(0),
guard_true(c,[],l_done,
guard_value(x,5,[],b2,
op2(x2,mul,var(x),const(2),
op2(x3,add,var(x2),const(1),
op2(i,sub,var(i),var(x3),
loop))))))

guard_value(x, 5, ...) の操作の後、 x が 5 であるとわかります。ただし 5 ではない場合、実行はインタプリタにフォールバックされます。従って、ガードの後の x に対するオペレーションは、定数に畳み込めます。定数畳み込みの並べ替えを行うために追加の最適化のステップが必要です。どの変数が定数として扱えるかと、どの値が部分環境で使われているかの情報を利用しながら最適化のステップはトレースに沿って動作します。オプティマイザは定数引数のみを持つオペレーションを取り除き、それ以外をトレースに残します。このプロセスは部分評価に実際に非常に似ていて、いくつかの分かっている変数は定数になり、定数引数のみのオペレーションは最適化によって取り去られ、残りはそのままです。
最適化を行うためのコードを以下に示します。

optimize(op1(ResultVar, Op, Arg, Rest), PEnv, NewOp) :-
    presolve(Arg, PEnv, RArg),
    (RArg = const(C) ->
        do_op(Op, C, Res),
        write_env(PEnv, ResultVar, Res, NEnv),
        NewOp = RestResidual
    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op1(ResultVar, Op, RArg, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

optimize(op2(ResultVar, Op, Arg1, Arg2, Rest), PEnv, NewOp) :-
    presolve(Arg1, PEnv, RArg1),
    presolve(Arg2, PEnv, RArg2),
    (RArg1 = const(C1), RArg2 = const(C2) ->
        do_op(Op, C1, C2, Res),
        write_env(PEnv, ResultVar, Res, NEnv),
        NewOp = RestResidual
    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op2(ResultVar, Op, RArg1, RArg2, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

部分評価と同じですね!部分評価器からのヘルパ関数 presolve と部分環境 PEnv の再利用をしています。オペレーションの引数が部分環境の中で定数だと分かっている時、オペレーションは最適化の際に実行され、トレースから取り除かれます。そうでなければオペレーションは出力のトレースに残ります。結果の変数(部分評価器内にあるもの) は部分環境から取り除くために必要です。不明な結果によって上書きされるためです。
トレースの中でガードで対処する必要があります。

optimize(guard_true(V, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C) ->
        NewOp = RestResidual
    ;
        NewOp = guard_true(V, PEnv, L, RestResidual)
    ),
    optimize(Rest, PEnv, RestResidual).

optimize(guard_false(V, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C) ->
        NewOp = RestResidual,
        NEnv = PEnv
    ;
        write_env(PEnv, V, 0, NEnv),
        NewOp = guard_false(V, PEnv, L, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

ガードされた変数が実際は定数だとわかったとき、ガードを取り除けます。
注意としては、定数のガードが失敗したときは可能ではありません。 (??)
トレーサは実際の値で実行している間のオペレーションを記録します。
従って、値のガードが成功するにはオプティマイザが定数を検出する必要があります。
guard_false は guard_true と若干違います。guard_false の後は引数が実際に 0 だとわかりますが、 guard_true の後は値がゼロではないことのみ知り、正確な値はわかりません。
別の点に注目してください。カードによる最適化で、これまでのところ常に空リストだったガードオペレーションの二つ目の引数が部分環境 PEnv に置換されます。この置換がなぜ必要なのかを掘り下げて論じます。
変数の関係に関する本当に詳細な情報を提供することを除き、 guard_value の最適化はとても似ています。

optimize(guard_value(V, C, [], L, Rest), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C1) ->
        NewOp = RestResidual,
        NEnv = PEnv
    ;
        write_env(PEnv, V, C, NEnv),
        NewOp = guard_value(V, C, PEnv, L, RestResidual)
    ),
    optimize(Rest, NEnv, RestResidual).

このオペレーションは、オプティマイザが後のオペレーションで定数畳み込みのために利用する定数変数を得る主な方法です。以下が部分評価との主な違いです。

オプティマイザは開始時にいくつかの変数の値を知っています。
トレースの最適化時、最初はどの変数の値もわかりません。
いくつかの変数についての情報は、ガードの実行後後にのみ得られます。

今はループ文で何が起こるのかの情報が不足しています。原則として、再度ループ文に入るとそれになる。(それって何? トレース状態?)
ただし、ループ文でいくつかの追加のオペレーションが出力のために必要です。出力とは、最適化して取り去ったオペレーションとそれによって定数として割り当てられる変数の結果の値です。それが意味するところは、関係する可能性のある変数がいくつかの古い値を持っている可能性があるということです。ループの次のイテレーションは、明らかに間違っているこの古い値で続けます。従って、ループ文以前にいくつか割り当てた部分環境のエントリごとに一つ出力する必要があります。

optimize(loop, PEnv, T) :-
    generate_assignments(PEnv, T).

generate_assignments([], loop).
generate_assignments([Var/Val | Tail], op1(Var, same, const(Val), T)) :-
    generate_assignments(Tail, T).

どのように割り当ての生成が働くかの例としては、以下の例を見てください。部分環境が [x/5, y/10] であるときに、続く割り当てが生成されます。

?- generate_assignments([x/5, y/10], Out).
Out = op1(x, same, const(5), op1(y, same, const(10), loop)).

それらがオプティマイザのコードの全てです。一方、基本的な構造は、部分評価器とよく似ていて、複雑な部分もあまりありません。部分評価器を作るのが難しいものは、制御フローステートメントへの対処と、同じブロックが同じ定数を使って部分評価されたときはコードが再利用可能かどうかの確認と対処の両方必要です。ここでは、全ての複雑なものは置いておきます。トレーサは既に全ての制御フローを削除してガードに置換していて、一回のループオペレーションが終わっています。従って、オプティマイザは単純に 1 パスのオペレーションを実行でき、いくつかを削除します。(ループ文へのいくつかの追加のケアも行います)
この機能を使うと、前回のエントリのプロモーションの例からトレースの最適化を行えます。

?- optimize(
    guard_value(x,3,[],b2,
    op2(x2,mul,var(x),const(2),
    op2(x3,add,var(x2),const(1),
    op2(i,sub,var(i),var(x3),
    op2(c,ge,var(i),const(0),
    guard_true(c,[],l_done, loop)))))),
    [],
    LoopOut).
LoopOut = guard_value(x, 3, [], b2, op2(i, sub, var(i), const(7), op2(c, ge, var(i), const(0), guard_true(c, [x/3, x2/6, x3/7], l_done, op1(x, same, const(3), op1(x2, same, const(6), op1(x3, same, const(7), loop)))))))

より読みやすく、最適化したバージョンは以下です:

guard_value(x, 3, [], b2,
op2(i, sub, var(i), const(7),
op2(c, ge, var(i), const(0),
guard_true(c, [x/3, x2/6, x3/7], l_done,
op1(x, same, const(3),
op1(x2, same, const(6),
op1(x3, same, const(7),
loop)))))))

意図したとおり、 guard_value の後の x へのオペレーションは全て削除されます。ただし、いくつか追加された割り当て (x, x2, x3) が最終的に生成されています。この追加の変数は余分なものに見えますが、オプティマイザにはそれを簡単に認識するための十分な情報がありません。この挙動は修正できますが、より複雑にするというコストをかける必要があります。(実際のシステムでは静的単一代入形式 (static single assignment/SSA) にトレースを変換することがこの問題への解となっています)

インタプリタの再開

なぜ上記のコードは最適化できないガードのために部分環境を追加する必要があるのでしょうか? 理由は、なぜループの前に割り当てを追加しなければならないのか、ということに関連します。問題は、オプティマイザが変数の値を知るとき、オプティマイザが変数への割り当てを取り除くことにあります。それが意味することは、実行中の最適化されたトレースからインタプリタへのスイッチバックを行うときに環境の中のいくつかの変数が更新されず、インタプリタの実行が不適切に行われてしまいます。
上記の例で、これを変数 x2 と x3 に適用します。二つ目のガードが失敗したとき、最適化された場合はそれらは代入されません。従って、ガードは変数とその値(常に定数です)をリストします。
スイッチバックするとき、インタプリタ側の対応する変数に対する割り当てを作らなければいけません。従って、前回のエントリのコードに以下のように resume_interp 関数を適用する必要があります。

write_resumevars([], Env, Env).
write_resumevars([Key / Value | Rest], Env, NEnv) :-
    write_env(Env, Key, Value, Env1),
    write_resumevars(Rest, Env1, NEnv).

resume_interp(Env, ResumeVars, L) :-
    write_resumevars(ResumeVars, Env, NEnv),
    block(L, Block),
    interp(Block, NEnv).

再開時に、 ResumeVars (元の部分環境) は単に元の通常環境に追加され、インタプリタに戻ります。ガードの失敗時にトレースの実行を終了し、インタプリタの実行を再開するために必要な、ガードにアタッチされたデータは、多くの場合非常に複雑なトレースシステムの一部です。ほとんどのガードが失敗しないうちはデータは大きくなる可能性があります。従って、ほとんどの実際のシステムではアタッチされるデータの困難な圧縮を試みたりその後のガードとのデータの共有を試みたりしています。

まとめ

このエントリでは、部分環境の変数を適用してトレースを最適化方法とその原理について説明しました。

定数引数のみを持つ全てのオペレーションを実行し、それ以外を残すこと
制御フローを含まないため、トレースの最適化はとても単純であること
制御フローに関する全ての疑問はトレーシングコンポーネントによって予め解決しているということ

次の、そしてシリーズ最後のエントリでは、小さなバイトコードインタプリタを最適化できるトレーシングと部分評価のより大きな例をお見せします。

FlowGraph 言語のための単純なトレーサ

2012-02-05T01:11:00.001+09:00

原文はこちら

Part2 トレーシングと部分評価の比較

部分評価とトレーシングの比較シリーズの二つ目のエントリです。最初のエントリでは、小さな FlowGraph 言語とそのインタプリタを作り、その言語の部分評価器を示しました。このエントリでは、同じ言語のトレーサがどのように働くか、両方の実行がどのように関係するのかを示します。このエントリで使われるコードはここにあります: http://paste.pocoo.org/show/543542/

トレースの実行

トレーサのアイデア(言語の一般的な説明)は、通常の解釈を完全に行いますが、同時に実行された全ての通常のオペレーション(例: フロー制御でないオペレーションなど)のログを保持します。これは、トレーサがブロックの開始から対応する閉じたループを実行する間続けられます。その後、トレースが停止し、最後のオペレーションが開始へのジャンプによって置き換えられます。トレースが終了した後、必要に応じて最適化してトレースを実行できます。

トレーサを書くために、インタプリタのルールから始めます。述語を trace にリネームし、いくつかの引数を追加しています。従って、以下のインタプリタののルールと:

interp(op1(ResultVar, Op, Arg, Rest), Env) :-
    resolve(Arg, Env, RArg),
    do_op(Op, RArg, Res),
    write_env(Env, ResultVar, Res, NEnv),
    interp(Rest, NEnv).

interp(op2(ResultVar, Op, Arg1, Arg2, Rest), Env) :-
    resolve(Arg1, Env, RArg1),
    resolve(Arg2, Env, RArg2),
    do_op(Op, RArg1, RArg2, Res),
    write_env(Env, ResultVar, Res, NEnv),
    interp(Rest, NEnv).

トレーサの以下のルールからなります:

trace(op1(ResultVar, Op, Arg, Rest), Env, op1(ResultVar, Op, Arg, T), TraceAnchor) :-
    resolve(Arg, Env, RArg),
    do_op(Op, RArg, Res),
    write_env(Env, ResultVar, Res, NEnv),
    trace(Rest, NEnv, T, TraceAnchor).

trace(op2(ResultVar, Op, Arg1, Arg2, Rest), Env, op2(ResultVar, Op, Arg1, Arg2, T), TraceAnchor) :-
    resolve(Arg1, Env, RArg1),
    resolve(Arg2, Env, RArg2),
    do_op(Op, RArg1, RArg2, Res),
    write_env(Env, ResultVar, Res, NEnv),
    trace(Rest, NEnv, T, TraceAnchor).

実際に対応するインタプリタのルール本体が、どのようなトレースのルールなのかの唯一の違いはトレースの再帰呼び出しです。trace の引数の意味は以下の通りです。最初と二番目の引数は、インタプリタで使われるような現在実行しているオペレーションと環境です。続く引数はトレースしているオペレーションの出力先で、上の例では実際に実行されたオペレーションになっています。TraceAnchor はその時構築しているトレースに関する追加の情報です。ほとんどの時間、 trace の再帰呼び出しで渡されます。その中に何が含まれているかは後で参照します。

print_ant_stop のルール簡単に実行でき、(そのためトレースもまた) 単に停止するだけです:

trace(print_and_stop(V), Env, print_and_stop(V), _) :-
    resolve(V, Env, Val),
    print(Val), nl.

残りは jump と if の制御オペレーションのルールです。トレースはジャンプを含まないように実行パスを線形化します。ただし、最初のラベルへのジャンプに到達したとき、トレースは停止します。従って、 jump の実装は二つのケースがあります:

trace(jump(L), Env, T, TraceAnchor) :-
    (TraceAnchor = traceanchor(L, FullTrace) ->
        T = loop,
        write(trace), nl, write(FullTrace), nl,
        do_optimize(FullTrace, OptTrace),
        write(opttrace), nl, write(OptTrace), nl,
        runtrace(OptTrace, Env, OptTrace)
    ;
        block(L, Block),
        trace(Block, Env, T, TraceAnchor)
    ).

小さな単位でこのコードを解剖してみましょう。最初に、 TraceAnchor が何かを見ます。TraceAnchor は traceanchor(StartLabel, FullTrace) というフォームの用語です。StartLabel はトレースを開始したプログラムのラベルです。(ループが閉じられた時と同様に同様に終了する必要があります)FullTrace は構築している全てのトレースを保持するアキュムレータです。

ターゲットラベル L が trace anchor にストアさているかどうかをルールのチェック開始の際に確認します。もし含まれていれば、トレースを停止できます。T をトレースする残りの部分は、 loop のオペレーションが割り当てられ、トレースの最初にジャンプして戻ります。その後、プリントしてトレースを最適化します。そして、実行時に FullTrace は traceanchor の一部として使います。

ジャンプする先のラベルが StartLabel ではない場合、オペレーションを記録せずにトレースを継続します。ルールのこの部分では、再度同じようなジャンプの解釈をします。

今のところ、どのような興味深い最適化も行いません。最適化されていないトレースを返すだけです:

do_optimize(FullTrace, FullTrace).

今足りていないオペレーションは if です。if 文は特別な処理が必要です。トレースする制御フローの数が発散してしまうからです。トレースは線形です。したがって分岐する可能性のあるパスの内片方しか記録できません。実行される別のパスをトレースすることはトレースの実行時に可能です。したがって、トレース中の真偽値と、トレースの実行中に真偽値がまだ同じ条件かどうかを確認する必要があります。これは、この条件をチェックするガードオペレーションで済んでいます。続くルールを実装します:

trace(if(V, L1, L2), Env, T, TraceAnchor) :-
    lookup(V, Env, Val),
    (Val == 0 ->
        L = L2, T = guard_false(V, [], L1, NT)
    ;
        L = L1, T = guard_true(V, [], L2, NT)
    ),
    trace(jump(L), Env, NT, TraceAnchor).

これはインタプリタの if のルールにとても似ています。ルールは条件が真であれば guard_true をケース中に挿入し、条件が偽であれば guard_false を挿入します。ガードの引数は以下の通りです。

ガードを行う変数

空のリスト(この理由は後々説明します)

ガードの失敗時とトレースの残りの部分の実行を続けるために必要なラベル

トレースの開始時に便利に使える小さな述語も追加しましょう:

do_trace(L, Env) :-
    block(L, StartBlock),
    trace(StartBlock, Env, ProducedTrace, traceanchor(L, ProducedTrace)).

最初の実行によって、述語はラベルと環境を受け取り、受け取った環境とともにラベルを実行します。その後、トレースを実行し、最終的にカードが失敗するとインタプリタにジャンプして戻ります。これを、ラベル L のブロック文とコードを読むことで実行します。そして未束縛の変数 ProducedTrace とともに trace を呼び出し、トレースとトレースを開始したラベルを含むトレースアンカーを保持し、トレース変数が生成されます。

この述語とトレースを使うと、トレースの実行がないだけで前回のブログポストは既にトレースできる力のある実装です。(実行は次のセクションでおこないます):

?- do_trace(power_rec, [res/1, x/10, y/20]).
trace
op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop)))
opttrace
op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop)))
...

計算されたトレースは:


op2(res,mul,var(res),var(x),
op2(y,sub,var(y),const(1),
guard_true(y,[],power_done,
loop)))

実際 power_rec からのループの中身です。if が guard_true になると、ガードが失敗した場合 power_done にジャンプします。

実際のトレースシステムには、トレーサを開始するための方法が必要になります。例えばインタプリタの中でのプロファイリングの実行によるものや頻繁に実行されるラベルでトレーサを開始するなどです。また、同じラベルのトレースは、通常同じ経路であればキャッシュされます。これらの詳細はこの単純なモデルではそのままです。

トレースの実行

実際のトレースシステムでは、トレースはマシンコードになり、 CPU で直接実行されます。私たちの小さなモデルでは、単にこのモデルのための別のインタプリタを書き出すだけです。このインタプリタはとても単純で、インタプリタにとても似ています:

runtrace(op1(ResultVar, Op, Arg, Rest), Env, TraceFromStart) :-
    resolve(Arg, Env, RArg),
    do_op(Op, RArg, Res),
    write_env(Env, ResultVar, Res, NEnv),
    runtrace(Rest, NEnv, TraceFromStart).

runtrace(op2(ResultVar, Op, Arg1, Arg2, Rest), Env, TraceFromStart) :-
    resolve(Arg1, Env, RArg1),
    resolve(Arg2, Env, RArg2),
    do_op(Op, RArg1, RArg2, Res),
    write_env(Env, ResultVar, Res, NEnv),
    runtrace(Rest, NEnv, TraceFromStart).

これらのルールはインタプリタの op1 と op2 のルールと完全に等価です。runtrace は、自身の再帰呼び出しで常に渡される追加の引数 TraceFromStart が必要です。

トレースの最後に到達し、ループ文が検出されると単に最初から開始します:

runtrace(loop, Env, TraceFromStart) :-
    runtrace(TraceFromStart, Env, TraceFromStart).

残りの質問は、ガードが発生した時に何をするかです。このケースでは、ガード条件をチェックする必要があります。ガードが成功した場合、トレースの実行は続けられます。それ以外の場合トレースは終了し、インタプリタは実行を再開します:

runtrace(guard_true(V, ResumeVars, L, Rest), Env, TraceFromStart) :-
    lookup(V, Env, Val),
    (Val == 0 ->
        resume_interp(Env, ResumeVars, L)
    ;
        runtrace(Rest, Env, TraceFromStart)
    ).

runtrace(guard_false(V, ResumeVars, L, Rest), Env, TraceFromStart) :-
    lookup(V, Env, Val),
    (Val == 0 ->
        runtrace(Rest, Env, TraceFromStart)
    ;
        resume_interp(Env, ResumeVars, L)
    ).


resume_interp(Env, [], L) :-
    block(L, Block),
    interp(Block, Env).

どのように実行がガードオペレーションの第三引数にエンコードされたラベルとしてインタプリタに引き渡されるのでしょうか。ResumeVars が何なのかは、後のエントリで見ることにします。今のところ、それは常に空のリストであると仮定します。

トレースのためのこのインタプリタを使うことで、サンプルをトレースし、実行できます:

:- do_trace(power_rec, [res/1, x/10, y/20]).
trace
op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop)))
opttrace
op2(res,mul,var(res),var(x),op2(y,sub,var(y),const(1),guard_true(y,[],power_done,loop)))
100000000000000000000

もちろんこの例はあまり面白くありません。トレースの結果はほとんどオリジナルのコードと同じだからです。後のエントリではより面白い例を示します。

拡張機能: プロモーション

ここでは、トレーサは実際にはインタプリタにはあまり手を加えていません。しかし、この線形化コントロールフローに深く高度な動作はありません。このセクションでは、より面白いことをするためにコントロールフロー言語にトレーサを許可する、重要ですが単純な拡張機能を追加します。この拡張機能はプロモーションと呼ばれます。

プロモーションは、基本的にはプログラマがコントロールフロープログラムに追加できるヒントです。プロモーションは変数 V とラベル L を引数に取る promote(V, L) のようなオペレーションです。インタプリタがこの文を実行するとき、単にラベル L にジャンプし、変数を無視します:

interp(promote(_, L), Env) :-
    interp(jump(L), Env).

ただし、トレーサはいくつかの遙かに面白いことをします。トレーサの promote 文は V の値について知るために非常に役立つであろうヒントをトレーサに与え、残りのトレースでその値は定数として保持する必要があります。従って、トレーサがプロモーションを検出すると、特殊な種類の guard_value と呼ばれるガードを挿入します:

trace(promote(V, L), Env, guard_value(V, Val, [], L, T), TraceAnchor) :-
    lookup(V, Env, Val),
    trace(jump(L), Env, T, TraceAnchor).

guard_value は興味深いオペレーションです。変数 V の現在の値 FVal をトレースの中に凍結するからです。トレースが実行される時、ガードは変数の現在の値と凍結した値が同じかどうかをチェックします。もし同じであれば、実行は継続されます。そうでなければトレースは終了します:

runtrace(guard_value(V, FVal, ResumeVars, L, Rest), Env, TraceFromStart) :-
    lookup(V, Env, Val),
    (Val == FVal ->
        runtrace(Rest, Env, TraceFromStart)
    ;
        resume_interp(Env, ResumeVars, L)
    ).

このオペレーションはどのように使えるのでしょうか? これは、変数 V があまり変更されないことや、これにより現在の値をトレースの中に凍結するのに役立つといったようにトレーサとコミュニケーションをとる方法です。これによって毎回 V の値を知ることなく処理を進められます。

ここで、(少し考えられた)例を見てみましょう:


l:
    c = i >= 0
    if c goto b else goto l_done

l_done:
    print_and_stop(var(i))

b:
    promote(x, b2)

b2:
    x2 = x * 2
    x3 = x2 + 1
    i = i - x3
    goto l

プログラムの構文に落とし込みます:

block(l, op2(c, ge, var(i), const(0),
         if(c, b, l_done))).
block(l_done, print_and_stop(var(i))).

block(b, promote(x, b2)).
block(b2, op2(x2, mul, var(x), const(2),
          op2(x3, add, var(x2), const(1),
          op2(i, sub, var(i), var(x3),
          jump(l))))).

これは単純な x * 2 + 1 のカウントダウンを行うループです。どのような x が入力されたとしても、 i >= 0 が真である期間は長くありません。x がほとんど変更されないと仮定すると、 x * 2 + 1 が定数に畳み込みが可能なのでイテレーションごとに再実行する必要がないとプロモートする価値があります。これは x のプロモーションによって完了します (もちろんこのループは不変のループを使ったコードに最適化され、よく動くでしょう、 x はループ中では実際に変更されないためです)。

これをトレースするには、以下のクエリを実行する必要があります:

?- do_trace(b, [i/100, x/5]).
trace
guard_value(x,5,[],b2,op2(x2,mul,var(x),const(2),op2(x3,add,var(x2),const(1),op2(i,sub,var(i),var(x3),op2(c,ge,var(i),const(0),guard_true(c,[],l_done,loop))))))
opttrace
guard_value(x,5,[],b2,op2(x2,mul,var(x),const(2),op2(x3,add,var(x2),const(1),op2(i,sub,var(i),var(x3),op2(c,ge,var(i),const(0),guard_true(c,[],l_done,loop))))))
-10

トレースをより読みやすい方法で書くと:

guard_value(x,3,[],b2,
op2(x2,mul,var(x),const(2),
op2(x3,add,var(x2),const(1),
op2(i,sub,var(i),var(x3),
op2(c,ge,var(i),const(0),
guard_true(c,[],l_done,
loop))))))

guard_value の後で、 x へのオペレーションの実行は定数にたたみ込まれてなくなります。x が 5 であると実行が継続される前にガードが保証するからです。実際に定数畳み込みを実行するには、トレースを最適化するためのいくつかのコンポーネントが必要です。これは次回のエントリで言及します。

このセクションでは、どのようにトレーサにプロモーションを実装するかについて話し、何をどのように使うかについては触れていません。プロモーションは一番重要な PyPy のトレーシングのアプローチの成功のために責任のある要素の一つです。どのようにこれが動くのかは、"Runtime feedback in a meta-tracing JIT for efficient dynamic languages"で詳しく説明されています。

結論

このエントリでは、とても小さな最小限のトレーサと、生成されたトレースのためのインタプリタを見ました。トレーサはオリジナルのインタプリタにとても似ていて、それはまた実行されたオペレーションを追跡して、さらにプログラムを実行します。トレーシングの段階ではループは閉じられていて、その後トレースは最適化され、実行されます。失敗のガードがヒットしている間トレースの実行が続きます。ある時点で、実行は通常のインタプリタに戻ります (そしてこのシンプルな実装では通常のインタプリタに戻ったままになります) 。

オリジナルのプログラムで promote を呼ぶことでヒントの追加を可能にするトレーサの拡張もお見せしました。実行時の値をトレースに凍結して保持するフィードバックをトレーサに指示するものです。この拡張機能は、前回のエントリで実装した部分評価器では不可能です。部分評価は厳密に実行前に終了し、変数の値がわかっていない場合は、実行時の値は見つけられない可能性が高いです。

次のエントリでは、プログラムの実行前にトレースをどのように最適化するかと、どのようにトレースのオプティマイザが部分評価と関わるかについてお見せします。

部分評価とトレーシングの比較 Part 1

2012-01-27T13:24:00.005+09:00

原文はこちら

私の博士論文の一部として、私は今 PyPy のメタトレーシングアプローチと従来の言語処理系からの情報のみ利用する(JIT)コンパイラの様々なアイデアとの関連について考えています。これらの線に沿って一番研究されたアイデアの一つは部分評価です。部分評価は、基本的にコンパイラに付属するという PyPy と同じゴールを持っています。インタプリタを書き、コンパイラをコストなしに手に入れるということです。ゴールにたどり着く方法は、若干違います。この一連のブログポストでは、PyPy のメタトレーシングと部分評価の類似点と相違点を探してみようと思います。

Flow Graph 言語

「部分評価」が何なのかと「メタトレーシング」が何なのかの明確な理解のために両者の「実行モデル」を示します。その後、小さな命令型言語を定義し、その言語のための部分評価器とトレーサーがどのようなものなのかを示します。全てのコードは Prolog で実装されるでしょう。(パターンマッチングが使える関数型言語でも構いませんが、私が知る中では Prolog がベストです。バックトレーシングは使いませんので、単に関数型プログラムとして読めます。)このポストでは、言語とその言語の部分評価器の定義から始めます。このブログのポストに書かれた全てのコードはここにあります: http://paste.pocoo.org/show/541004/

言語は概念的には PyPy の Flow Graph に近いものです。しかし、少し制限があります。関数呼び出しを持たず、ラベルづけされた、一連の実行する命令の後に条件付き、もしくは条件なしのジャンプが付随するブロックから構成されます。全ての操作は、いくつかの演算をいくつかの引数に適用し、計算された値を変数に代入します。

x の y 乗を計算する単純なプログラムはこのようなものです:


power:
    res = 1
    if y goto power_rec else goto power_done

power_rec:
    res = res * x
    y = y - 1
    if y goto power_rec else goto power_done

power_done:
    print_and_stop(res)

Prolog のデータ構造で同じプログラムを表します。以下のような Prolog のコードです:

block(power, op1(res, same, const(1),
             if(y, power_rec, power_done))).
block(power_rec, op2(res, mul, var(res), var(x),
                 op2(y, sub, var(y), const(1),
                 if(y, power_rec, power_done)))).
block(power_done, print_and_stop(var(res))).

ブロックのそれぞれのルールは、最初にブロックのラベルを示し、コードが続きます。これで一つのブロックを宣言します。コードは op1 か op2 文が連なり、ジャンプ、 if もしくは print_and_stop によって終了します。op1 は一つの引数を受ける op1(res_variable, operation_name, argument, next_statement) のような命令です。引数は var(name) 形式の変数か const(value) 形式の定数が使えます。

この FlowGraph 言語を実行するには、最初にいくつかの補助機能を必要とします。最初のいくつかの補助機能は、インタプリタがプログラムで発生する、変数名の実行中の値とのマッピングに使うためのデータ構造で、実行環境を扱うことに関係します。Python では辞書型がこの目的で使われます。しかし、 Prolog ではキーと値のペアのリストを使ってエミュレートしなければいけません。(かなり効率は悪いですが、必要十分です):

lookup(X, [], _) :- throw(key_not_found(X)).
lookup(Key, [Key/Value | _], Value) :- !.
lookup(Key, [_ | Rest], Value) :- lookup(Key, Rest, Value).

write_env([], X, V, [X/V]).
write_env([Key/_ | Rest], Key, Value, [Key/Value | Rest]) :- !.
write_env([Pair | Rest], Key, Value, [Pair | NewRest]) :- write_env(Rest, Key, Value, NewRest).

remove_env([], _, []).
remove_env([Key/_ | Rest], Key, Rest) :- !.
remove_env([Pair | Rest], Key, [Pair | NewRest]) :- remove_env(Rest, Key, NewRest).

resolve(const(X), _, X).
resolve(var(X), Env, Y) :- lookup(X, Env, Y).

これらの関数の実装は重要ではありません。lookup 関数は環境のリストからキーを見つけ、 write_env 関数は新しいキーと値のペアを環境に追加し、 remove_env 関数はキーを削除します。resolve 関数は、定数か変数のいずれかを引数として取り、値を返す為に使います。もし定数であればその値が返され、変数であれば環境からルックアップします。注意として、
lookup と resolve の最後の引数は、実際には戻り値で、このような方法は Prolog ではよくあるアプローチです。

これまでのところ、基本演算のプログラム上の意味が定義されていません。そのため、基本演算とともに do_op 関数を定義します:

do_op(same, X, X).
do_op(mul, X, Y, Z) :- Z is X * Y.
do_op(add, X, Y, Z) :- Z is X + Y.
do_op(sub, X, Y, Z) :- Z is X - Y.
do_op(eq, X, Y, Z) :- X == Y -> Z = 1; Z = 0.
do_op(ge, X, Y, Z) :- X >= Y -> Z = 1; Z = 0.
do_op(readlist, L, I, X) :- nth0(I, L, X).
do_op(Op, _, _, _) :- throw(missing_op(Op)).

重要なことなのでもう一度言います。最後の引数は出力先の変数です。

単純な操作を実行する準備が整いました。なので、 interp という述語を定義します。これは、最初の引数が実行環境、二つ目の引数が実行する操作を表します。例では、一つか二つの引数をと共に基本演算を実行しています。:

interp(op1(ResultVar, Op, Arg, Rest), Env) :-
    resolve(Arg, Env, RArg),
    do_op(Op, RArg, Res),
    write_env(Env, ResultVar, Res, NEnv),
    interp(Rest, NEnv).

interp(op2(ResultVar, Op, Arg1, Arg2, Rest), Env) :-
    resolve(Arg1, Env, RArg1),
    resolve(Arg2, Env, RArg2),
    do_op(Op, RArg1, RArg2, Res),
    write_env(Env, ResultVar, Res, NEnv),
    interp(Rest, NEnv).

最初に、引数を値として解決します。その後、演算が実行され、結果が環境に書き戻されます。そして interp がプログラムの残りの部分とともに呼び出されます。同様に、条件なしジャンプと print_end_stop も簡単です。:

interp(jump(L), Env) :-
    block(L, Block),
    interp(Block, Env).


interp(print_and_stop(Arg), Env) :-
    resolve(Arg, Env, Val),
    print(Val), nl.

条件なしジャンプの中では、単にターゲットのブロックを取得し、その実行を継続します。print_and_stop の実行は、引数を解決し、値をプリントし、終了します。

条件付きジャンプだけはは少し難しいです:

interp(if(V, L1, L2), Env) :-
    lookup(V, Env, Val),
    (Val == 0 ->
        block(L2, Block)
    ;
        block(L1, Block)
    ),
    interp(Block, Env).

最初に変数を環境からルックアップし、変数の値がゼロであれば二つ目のブロックの実行を継続します。そうでなければ最初のブロックを継続します。

このインタプリタは、上記のサンプルを Prolog のコンソールでこのように実行できます:

$ swipl -s cfglang.pl
?- block(power, Block), interp(Block, [x/10, y/10]).
10000000000

FlowGraph 言語の部分評価

それでは、この単純な FlowGraph 言語のための部分評価器がどのようなものか見てみましょう。部分評価は特殊化とも呼ばれ、プログラム操作のテクニックです。部分評価は入力のプログラムを受け取り、(うまくいけば)シンプルで高速な出力プログラムに変換します。これは、入力プログラム中のいくつかの変数を定数であると仮定します。定数にのみ作用する全ての演算は、畳み込まれます。それ以外の全ての演算は、出力プログラムでもそのままにする必要があります。(残留プログラムと呼ばれます)従って、部分評価器は、単にいくつかの演算を実行できないだけで、殆どインタプリタのような結果をもたらします。また、出力は単なる値ではなく、最適化できなかった残りの演算のリストです。

部分評価器は通常の環境では使えません。全ての変数の値が知られているインタプリタとは異なるためです。そのために、部分的な環境の下では分かっている変数のみを保存します。これらの部分的な環境のために、いくつかの新しい補助関数が必要です:

plookup(Key, [], var(Key)).
plookup(Key, [Key/Value | _], const(Value)) :- !.
plookup(Key, [_ | Rest], Value) :- plookup(Key, Rest, Value).

presolve(const(X), _, const(X)).
presolve(var(V), PEnv, X) :- plookup(V, PEnv, X).

plookup 関数は変数と部分環境を受け取り、変数が部分環境内で見つかった場合は const(Value) を、見つからなかった場合は var(Key) を返します。同様に presolve は lookup の代わりに plookup を使う以外は resolve と同じ関数です。

これらの補助関数を使うことで部分評価器を書き始められます。下記の二つのルールは定数の畳み込みのための主な最適化で使います。部分評価器のアイデアは、定数引数のみを含む操作を見てください。それらは定数の畳み込み操作を行い、それ以外はそうではありません:

pe(op1(ResultVar, Op, Arg, Rest), PEnv, NewOp) :-
    presolve(Arg, PEnv, RArg),
    (RArg = const(C) ->
        do_op(Op, C, Res),
        write_env(PEnv, ResultVar, Res, NEnv),
        RestResidual = NewOp
    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op1(ResultVar, Op, RArg, RestResidual)
    ),
    pe(Rest, NEnv, RestResidual).

pe(op2(ResultVar, Op, Arg1, Arg2, Rest), PEnv, NewOp) :-
    presolve(Arg1, PEnv, RArg1),
    presolve(Arg2, PEnv, RArg2),
    (RArg1 = const(C1), RArg2 = const(C2) ->
        do_op(Op, C1, C2, Res),
        write_env(PEnv, ResultVar, Res, NEnv),
        RestResidual = NewOp

    ;
        remove_env(PEnv, ResultVar, NEnv),
        NewOp = op2(ResultVar, Op, RArg1, RArg2, RestResidual)
    ),
    pe(Rest, NEnv, RestResidual).

pe という述語は、部分環境を受け取り、現在の演算と行われる可能性のある新しい演算を返します。単純な演算の部分評価のために、これらの引数は部分環境からルックアップされます。もし全てのの引数が定数であれば、演算は実行できるので、新しい演算は生成されません。それ以外の場合は今見ているものと同じように動作する新しい残留演算を生成する必要があります。また、結果の変数は部分環境から削除する必要があります。不明な値によって上書きされるためです。

潜在的に生成された残留演算は NewOp の出力引数として保存されます。再帰呼び出しの出力の引数は、新しく生成された残留演算の最後の引数で、再帰的な呼び出しによって埋められます。これは Prolog では典型的なアプローチですが、 Prolog に馴染みない人には奇妙に見えるかもしれません。

注意として、これらのルールの最初のケースでは、解釈のようなことのみを行います。二つ目のケースでは、実際にはなにもしておらず、残留演算を生成しているだけです。この通常の評価と部分評価の間の関連は、とても典型的なものです。

条件なしジャンプと print_and_stop はとても簡単です:

pe(jump(L), PEnv, jump(LR)) :-
    do_pe(L, PEnv, LR).

pe(print_and_stop(Arg), Env, print_and_stop(RArg)) :-
    presolve(Arg, Env, RArg).

部分評価のために、条件なしジャンプは再度ジャンプを生成します。既存のジャンプターゲットのラベルは、残留コードを生成するために、ラベル L 渡とされた部分環境を伴って部分評価器にで評価することで計算されます。print_and_stop は単に print_and_stop を返すだけです。do_pe のコードをすぐに見てみましょう。

条件付きジャンプはより興味深いです:

pe(if(V, L1, L2), PEnv, NewOp) :-
    plookup(V, PEnv, Val),
    (Val = const(C) ->
        (C = 0 ->
            L = L2
        ;
            L = L1
        ),
        do_pe(L, PEnv, LR),
        NewOp = jump(LR)
    ;
        do_pe(L1, PEnv, L1R),
        do_pe(L2, PEnv, L2R),
        NewOp = if(V, L1R, L2R)
    ).

最初に、条件変数の値を参照します。もしそれが定数であれば、よりよいコードを生成できます。静的に一つのパスにしか到達できないことが分かるためです。従って、そのパスのへのコードを生成し、条件なしのジャンプを出力します。もし条件変数が部分評価時にわからなければ、どちらのパスに対しても部分評価を適用し、残留コードして条件付きジャンプを生成します。

部分評価器がインタプリタよりも多く作業を行う可能性がある原因のルールは一つで、 if の後でしばしば両方のパスを探索しなければいけないということです。最悪のケースでは、このプロセスは終了しません。なので、実際の部分評価器では、どのように終了するかを確認しなければいけませんそれを行うための多くのアルゴリズムがありますが、ここではこの問題を無視します。

今 do_pe という述語がなにをしているかを理解することが必要です。一番重要なタスクは、以前に部分評価されたかどうかをメモ化するコードによって、同じ作業を二回しないことを確認することです。そのために部分環境のラベルから残留コードのラベルへのマッピングを保持します:

do_pe(L, PEnv, LR) :-
    (code_cache(L, PEnv, LR) ->
        true
    ;
        gensym(L, LR),
        assert(code_cache(L, PEnv, LR)),
        block(L, Code),
        pe(Code, PEnv, Residual),
        assert(block(LR, Residual))
    ).

もしラベル L が既に部分環境 PEnv の中で部分評価されていることをコードキャッシュが示すのであれば、以前生成した残留コードのラベル LPrevious が返ります。それ以外は gensym によって新しいラベルが生成され、コードキャッシュは新しいラベルを割り当てて通知し、ブロックは部分評価され、残留コードがデータベースに追加されます。

部分評価について知るための用語集: この部分評価器は polyvariant online 部分評価器です。 "Polyvariant" の意味するところは、全てのラベル、いくつかの特殊化したバージョンのブロックを生成できるということです。"Online" の意味は、部分評価器を走らせる前の事前処理がないということです。

部分評価の例

このコードで、部分評価の古典的な例を見られます。(恐らく部分評価における "Hello, world" のようなものです) 冪乗関数について部分評価器に尋ね、指数 y が定数(例えば 5)や、ベースの x が不明であるということです:

?- do_pe(power, [y/5], LR).
LR = power1.

このようなリストのコードが生成されます。

?- listing(code_cache)
code_cache(power, [y/5], power1).
code_cache(power_rec, [y/5, res/1], power_rec1).
code_cache(power_rec, [y/4], power_rec2).
code_cache(power_rec, [y/3], power_rec3).
code_cache(power_rec, [y/2], power_rec4).
code_cache(power_rec, [y/1], power_rec5).
code_cache(power_done, [y/0], power_done1).

?- listing(block)
.... the block definition of the user program ....
block(power_done1, print_and_stop(var(res))).
block(power_rec5, op2(res, mul, var(res), var(x), jump(power_done1))).
block(power_rec4, op2(res, mul, var(res), var(x), jump(power_rec5))).
block(power_rec3, op2(res, mul, var(res), var(x), jump(power_rec4))).
block(power_rec2, op2(res, mul, var(res), var(x), jump(power_rec3))).
block(power_rec1, op2(res, mul, const(1), var(x), jump(power_rec2))).
block(power1, jump(power_rec1)).

code_cache は、部分環境の下でどのオリジナルラベルがどの残留ラベルに対応するかを教えてくれます。従って、y が 5 であるという想定のもとで power1 が power のコードに含まれます。リストのブロックを見ると、 power1 というラベルは x を全く使用せずに、単純に 5 回 x を掛けるコード対応します。オリジナルのプログラムではループであったものは、完全に展開されてループ変数の y は消えてしまいました。うまくいけばこれはオリジナルのプログラムよりも速くなります。

結論

このブログのポストで見たものは、 Prolog で作られたシンプルな Flow Graph 言語のインタプリタと、その部分評価器です。部分評価器は、本質的にはインタプリタのあらゆるルールを複製します。もし全ての処理中の引数が全て分かっているならば、それはインタプリタのように振る舞います。そうでなければ単純に残留コードに演算をコピーするだけです。

部分評価は様々なアプリケションに利用できますが、最もよく引用されて適用されるるものの一つはインタプリタです。インタプリタが走らせるプログラムは部分評価器によって定数とみなされます。したがって、特殊化されたバージョンのインタプリタは入力するプログラムを全く使用せずに生成されます。残留コードは入力プログラムのコンパイルされたバージョンであるとみなせます。

このシリーズの次のブログポストでは、同じ FlowGraph 言語の単純なトレーサを書いてみます。

PyPy 1.7 on Win32

2011-12-09T07:41:00.002+09:00

原文はこちら: PyPy 1.7 on Win32

やぁ、みんな！

We have fixed _continuation on Win32 (thanks Stakkars), and so we have now a Win32 version of PyPy 1.7.

私はWin32の_continuationを完了する（ありがとうStakkars）とともに、Win32版のPyPy 1.7をリリースしました。

（原文：Posted by Armin Rigo）
（翻訳：Tohru Ike）

PyPy 1.7 - スイートスポットの拡大

2011-11-21T23:02:00.010+09:00

原文はこちら: PyPy 1.7 - widening the sweet spot

PyPy 1.7のリリースをアナウンスできることを嬉しく思います。バージョン1.6から、いつも通り多くのバグフィックスとパフォーマンスの改善が行われました。しかしながら、以前のバージョンとは異なり、このバージョンではPyPyの"スイートスポットの拡大"に焦点を当てています。すなわち、PyPyによって高速化できるPythonコードのクラスの幅がとても広がりました。PyPy 1.7はこちらからダウンロードできます。

http://pypy.org/download.html

PyPyとはなにか

PyPyはとても素直なPythonインタプリタで、CPython 2.7とほぼ完全な互換性があります。トレーシングJITを採用したことで高速化を実現しました（pypy 1.7とCPython 2.7.1の性能比較はこちら）。

このリリースは、x86上で動作するLinux 32/64、Mac OS X 32/64、Windows 32をサポートしています。Windows 64は現在作業中ですが、ネイティブではサポートされません。

このリリースのメイントピックは、PyPyが高速化できるコードの幅が広がったことにあります。我々のベンチマークによれば、PyPy 1.7はPyPy1.6と比較して平均して30％以上、いくつかのベンチマークでは20倍以上高速化しています。

ハイライト

多くのパフォーマンスの改善。例を上げればキリがないほど高速化された部分があります。
バグフィックスと、CPythonとの互換性の確保。
Windowsにおける修正
デフォルトでスタックレスを実現しました。しかしながら、多くループはJITに割り込んでしまいます。ですから、スタックレスを基礎としたプログラムの高速化は実現していません。この制約を取り除くための情報がありましたらpypy-devまでコンタクトしてください。
PyPyにおけるNumPyの名称がnumpypyに変更されました。numpypyを試すためには、シンプルに、import numpypy as numpy と、プログラムの始めに記述してください。PyPyのnumpyは1.6と比較して飛躍的に進化しています。主な特徴はdtypeの実装にあります。
JSONのエンコーダが新しいものに置き換わっています（デコーダではありません）。これはPure Pythonで書かれていますが、CPythonのC拡張を用いたものと比較して、いくつかのケースで2倍高速になっています。これはPyPy 1.6と比較すると20倍以上高速化しています。
RPythonモジュールにおけるメモリのフットプリントがいくつか改善されています。これは暗号やtornadoなどにおいてインパクトがあります。
cpyextで動くCPython C APIにおいてさらなる進展がありました。

まだ完成していないが、1.8において期待される事項

このリリースでは完成しなかったが、次のリリース 1.8において期待してよいかもしれないこと（これはここで書くべきではないかもしれませんが）。

リストの特別な実装。整数／浮動小数／文字列のリストにおいて、array.arrayと同様のコンパクトな実装のブランチがあります。いくつかの応用において、パフォーマンス／メモリ使用量の劇的な改善が見込まれます。
NumPyにおいて進行中の成果。多次元配列はすぐ実現するでしょう。
ふたつの新しいJITアセンブラのバックエンドがあります。PowerPCとARM向けのものです。

資金調達

ここで触れるべきことではないかもしれませんが、PyPyにおけるNumPyとPython 3のプロジェクトにおいて資金調達のキャンペーンが行われています。この件について素早く情報が欲しいかたは、numpy proposalやpy3k proposalをご覧ください。PyPyの進捗に関心があり、全体としての方向性に信頼をおいているならば、genral potへの寄付もご検討ください（寄付は常に受け入れています）。

Cheers,

Maciej Fijałkowki, Armin Rigo and the entire PyPy team

（原文：Posted by Maciej Fijalkowski）

（翻訳：Kentaro Iizuka）

ソフトウェアトランザクショナルメモリが必要です。

2011-09-04T18:52:00.002+09:00

原文はこちら: We need Software Transactional Memory

Hi、みんな。ここはPythonやPythonnoような言語の実装における、現時点のソフトウェアトランザクショナルメモリについての論文の短い要約（抽出物）です。

このブログ記事をより良くしてくれたIRCの人々(lucian, Alex Gaynor, rguillebert, timonator, Da_Blitz)に感謝します。
現在の議論の目的のために、私たちはPythonとJavaのマルチスレッド化を比べています。

複雑なハイレベル言語における問題

Javaのように、Python言語は保証します: Python仮想マシンはスレッドの誤った使用が原因でクラッシュすることは受け入れられません。
Javaのプリミティブ操作は、フィールドのオブジェクトフィールドを読み書きするようなものです; 対応する保証は、方針に沿っています。
プログラムがオブジェクトのフィールドを読み取り、別のスレッドが同じオブジェクトの同じフィールドに書き込む時、プログラムは、古い値または新しい値を参照するでしょう。
しかし、全く違った値ではなく、仮想マシンはクラッシュしません。Pythonのような高級言語は、"プリミティブな操作"は、はるかに複雑であるという事実があるため、Javaとは異なります。
それは例えば、いくつかのハッシュマップでおそらくアップデートを行って見られるかもしれません。
一般的には、それはすべての操作をシングルプロセッサの命令にアトミックに必ずし、完全にマップするのは不可能である。

JYTHON: きめ細かいロック

この問題はJavaの上で動作するJythonインタプリタでは"明示的に"解決されています。
解決策は次の文の通り明示的です：Jythonインタプリタ全体を通して、一つ一つの操作は、Javaレベルのロックメカニズムを慎重に利用しています。これは、"きめ細かいロック"のアプリケーションです。例えば、属性をハッシュマップの数だけ参照する操作はロック（__getattribute__における）の獲得と解放により保護されています。

このソリューションの引っ込めは、必要な細部へのこだわりです。一箇所でもロックをミスしたのであれば、いずれかのバグがあります。 --- このようなバグは、以前のバグが修正されているようにデバッグするため、ますますまれにしか起こらず困難なケースで発生します ---

また、私たちは"CPythonとの違い"のもとでそれを適正に保存します。しかしながら、二つのスレッドが異なる順序で同じオブジェクトをロックしようとすると、デッドロックの危険性があります。実際には、予想に反して私が手書きするほど悪い状態ではありません。Jythonにおけるロックの数は適切であり、そして、期待どおりに動作するすべての"一般的なケース"が可能になります。（稀なケースは、以下を参照してください。）

性能面では、Java仮想マシン自体は、長期間にわたって猛烈な最適化されているロックが付
属しています。
しかしながらCでコーディングされたソリューションの場合は、手動でロックを最適化するために余分な作業が多く必要になります（多くのバグを含んでしまうだろう）。

CPYTHON: きめのあらいロック

CPython、C言語によるPythonの標準実装では異なる単純なアプローチを取った：それはシングルグローバルロックを持ち、グローバルインタプリタロック（GIL）と呼ばれる。
それは"きめのあらいロック"を使用しています: ロックは、全体の実行であっちこっちにある1つのバイトコードが取得されて、リリースされます（実際に100のような少ない数のバイトコード）。それらを呼び出す複数バイトコードはGILで自分自身をシリアライズされるので、この解決策は、2つの操作が互いに競合しないことを保証するのに十分です。それは、インタプリタ全体にわたって慎重なロックを獲得するコードを書くのを避ける --- Jythonとは異なった ---解決策です。また、より強い保証を提供しています：すべてのバイトコードは、アトミックに完全に実行されます。

今日において、GILのアプローチの引き戻しは、マルチコアマシン上では明白です：複数のスレッドを開始し、バイトコードの実行をシリアル化することによって、実際には複数のコアのインタプリタの使用を許可しません。

PyPy、PythonによるPythonの実装では、これまでと同じアプローチを採用しています。

現在の処理

これまで見てきたように、我々は次のような解決策：既存のPython言語、CPython実装は、マルチスレッドの使用状況についての非常に強い保証を提供しています。
それは、ほとんどの既存のマルチスレッドのPythonプログラムが実際にそのような強い保証に頼ることは重要であると強調する。
これは、人口のリストを受け取り、いくつかのスレッドで行う問題の例で見ることができます:

next_item = global_list.pop()

これは、暗黙的にpop()がリストからアトミックの除去を実行するという事実を当てにしています。
二つのスレッドが同時に同じリストからポップしようとすると、2つの操作は、ある順序または別で発生します。
しかし、それらは例えば、両方のスレッドへ同じオブジェクトを返すか、リストオブジェクトの内部状態までぶち壊します。

このような例を念頭に置いて、私たちはこれらのマルチコア問題を含む強力な保証を落とす解決策を望んでいないことは明らかです。
しかしながらJythonがそうするように障壁を下げるのは、間違いありません; しかし、いくつかのPython実装は、いくつかの保証を提供しなくてはいけません、または、マルチスレッド化を全く提供してはいけません。
これは、組み込み型のメソッドの多くがアトミックであるという事実が含まれています。

(それは、全てにおいてマルチスレッドを提供していないことも実際にはまた、（部分的な）問題の解決策であることに留意すべきです。
最近、いくつかの"ハック"は、多かれ少なかれ透過的なアクセスし複数の独立したプロセス (e.g. multiprocessing).をプログラマに与えることが明らかです。
これらはいくつかのコンテキストで適切な解決策を提供するわけだが、マルチスレッドのように広く適用されません。
典型的な例として、それらは、複数のコアが、全くシリアライズできない情報を処理する必要があるとき適用しません。
--- いくつかのプロセス間における、いかなるデータ交換の要件。)

ここに、Jythonの一貫性がCPythonのGILよりどう弱いかの例があります。
それを示しているのに一般的でない例を要しており、CPythonのようなプログラマがそれらを予想するどんな仕事もせず、一般的に、実装の詳細として考えられている。
考察:

Thread 1: set1.update(set2)
Thread 2: set2.update(set3)
Thread 3: set3.update(set1)

各操作はCPythonの場合にはアトミックです。
しかし、Jythonの場合は、次の2つの手順（各々は、アトミックとみなすことができる）に分けられる：引数から読み取り、そして、対象のsetを更新する。
最初にset1 = {1}, set2 = {2}, set3 = {3} を行うとします。CPythonにおいて、独立したスレッドの実行順序の結果、最も小さなset {1, 2, 3} になります。
Jythonにおいて、すべての3つのsetが2つだけの要素を含むだけで終わっている可能性があります。
例は、少しこじつけですが、CPythonとの一貫性はJythonのより厳密に強くなって表示されるべきです。

PYPY

PyPyはCPythonやJythonに非常に似たPythonインタプリタです。しかし、生成方法は独特です。
それはPythonのサブセットであるRPythonで書かれたインタプリタであり、自動的に"翻訳"と呼ばれる段階で完全な仮想マシン（Cのコードを生成）になって手に入ります。
このコンテキストでは、CPythonとJythonのコンテキストはは異なります: PyPyではまったくもって簡単に、"翻訳時"にインタプリタへ任意のプログラム全体の変換を適用することが可能です。

この点を考慮し、インタプリタによってRPythonで操作の全オブジェクトにロックを追加し、プログラム全体の変換を想像することは可能です。
これはJythonと同様な状況として終わるでしょう。
しかしながら、それは慎重な手動配置でのロックがJythonの場合は回避され、デッドロックの問題が自動的に解決するとはなりません。
（実際には、デッドロックフリーであることは自動的に確保、検証できないグローバルプログラムのプロパティです;
いくらかのJythonの変更は、理論的にはこのプロパティを破るため、巧妙なデッドロックを導入することができます。
同じことが、ノンアトミックに適用されます。）

実際には、もし、インタプリタがスレッド1のバイトコードでAとB、およびスレッド2のバイトコードでBとA(反対の順序)に（読み取りおよび書き込みの両方の）アクセスした場合、私たちは簡単にそれを確認することができ、
--- また、あなたが2番目のオブジェクトにアクセスする必要がある、と決める前に最初のオブジェクトにアクセスしている必要があります。 ---
その時、アトミック性の強い保証を維持しながらデッドロックを（GILから離れて）回避する方法はありません。
確かに、両方のスレッドがそのバイトコードの実行の途中に進行した場合は、既にスレッド1によって変更されており、同様にBは既にスレッド2によって変更されています。
その場合、うまくスレッドを実行し続けるのは、可能ではありません。

USING SOFTWARE TRANSACTIONAL MEMORY

ソフトウェアトランザクショナルメモリ(STM)は、明らかに上述の問題に解決策をもたらすアプローチです。
実行し続けるどこのスレッドが間違った状況で終わった場合、私たちは、中断しロールバックすることができます。
これは、データベースのトランザクションの概念と似ています。
上述の例において、一方または両方のスレッドは、トラブルや中断を実行しようとしていることがわかります。
これは、彼らはこれまでに中止または単にまだコミットされていないものすべての副作用において、バイトコードの先頭で実行を再開する方法を持っている必要があることをより、具体的に意味しています。

私たちは、中断してロールバックする能力はPythonのマルチスレッド実装に欠けているパズルのピースだと考えています。
実際に、上記の問題のプレゼンテーションによれば、それはCPythonの一貫性とアトミック性の同じレベルを提供したすべての解決策は、中断とロールバックの容量を伴うことは避けられないです。--- これは正確にそのSTMを避けることができないことを意味します。

OK、しかしなぜJythonのアプローチで落ち着いて、インタプリタを通して左右の慎重なロックをかけないのか？
（1）私たちは、すべての操作のアトミック性を考慮し、決定を確認する（またはJythonのを盗む）必要がありますし、それらをここに文書化します;
（2）それはまた、これらのロックを最適化するために、本当に多くの作業となります。e.g. JITのみならずJVMが行うことと同様に;
（3）それは直交すべき機能のどこにでも手動で微調整するコードを必要とし、それはPyPyの方法ではありません;
（3）はおそらくここで最も重要です：あなたはPyPyで実装する言語ごとに作業をやり直す必要があります。
私自身もまたポイント（4）を意味する：それは楽いことではない :-)

詳細であるが、次のようにプロセスは働くだろう。
（これは、1つの可能なモデルの概要を説明します; 異なったモデルがより良くなることは確実です。）すべてのスレッドで:

バイトコードの開始時に、私たちは"トランザクション"を起動します。これは、トランザクションで発生するログを記録するために、スレッドローカルなデータ構造を設定することを意味します。
私たちは、ログに読み込まれるすべてのオブジェクトを、行いたい変更と同様に記録します。
この時間の間に、私たちは"読み取り"の不整合を検出し、現在のトランザクションの開始時間より遅いオブジェクトの"最終修正"タイムスタンプによって証明し、また中断する。
これは、コードの残りの部分が矛盾した値とともに実行されるのを防ぐことができます。
私たちは"読み取り"矛盾なくバイトコードの最後に到達した場合は、私たちは、アトミックに"書き込み"の不整合を確認してください。
これらは、他のスレッド内のオブジェクトへの同時更新から生じる矛盾です。---「書き込み」という私たちのオブジェクトか「読み込み」という私たちのオブジェクトのどちらか
不一致がまったく見つからない場合、私たちは、トランザクションを遅延をコピーすることによって、メインメモリにログから書き込み、"コミット"します。

どれの取引が始まるか、終わりがまさにポイントであるか指す、どれですか?
トランザクションが開始または終了するポイントは正確なポイントで、CPythonでは、グローバルインタプリタロックは、それぞれ取得され、解放されます。

私たちであれば(純粋に性能のために)CPythonがGILを取得して、Nバイトコードごとにリリースするという事実を無視してください。その時これを意味しています。

私たちは、任意のバイトコードの前にGILを（トランザクションを開始する）を取得し、バイトコードの後に私たちは、それ（トランザクションを終了する）を放します; そして
CライブラリやOSへの外部呼び出しを行う前に、私たちは、GIL（トランザクションを終了する）を放し、その後のそれ（次のトランザクションを開始する）を再取得します

特にこのモデルは、システムコールと同様に、私たちは --- まさに --- システムコールのようにロールバックすることができないトランザクション以外に何もできず、STMの条件に適しています。
確かに、構造によって、CPythonではそれらはGILの解放で発生するため、これらのシステムコールはトランザクションの外で発生します。

PERFORMANCE

今のところ、多くの詳細な実装はまだ未解決です。
ユーザーの観点（i.e. Pythonを使用してプログラマ）から、最も関連しているものは総合的なパフォーマンスの影響です。
私たちは、これまで正確な数値を与えることはできず、また、初期性能がものすごく悪いと予想しています。（10倍遅いかもしれない）;
しかしながら、ロック機構、ロックを挿入するグルーバルプログラムの変換、ガーベージコレクション（GC）、ジャストインタイムコンパイラ（JIT）への連続な改善において、私たちはそれがほぼ妥当なパフォーマンス（たぶん、最大2倍遅い）を得ることが可能であると信じています。
例えば、GCは発生したスレッドから漏れることなくオブジェクト上のフラグを保持する。
私たちは、これらが多くの失われた性能を取り戻すことができる最適化の一種であると信じています。

THE STATE OF STM

トランザクショナルメモリは、Tom Knightにより1986年の論文で配信され、それ自体は比較的古い考え方です。
最初はハードウェアサポート、1995年に大衆化されたソフトウェアのみのトランザクショナルメモリ（STM）の考え方に基づいており、最近では集中的な研究の焦点となっています。

上記で説明したアプローチ --- 言語の実装の中核を形成するためにSTMを使用 --- は、私たちの知る限り、新しいです。
これまでのところ、ほとんどの実装ではライブラリの機能として、STMを提供しています。

それは明示的に使用する必要があります。多くの場合、オブジェクトは、STMによって保護されている必要があり、明示的に宣言の形態であってもよい（オブジェクトベースTSTMs）。
STMのネイティブサポートがClojure言語で特に現れ始めたのは最近のことです。

STMは、アプローチとして、Wikipediaに "大幅にマルチスレッドプログラムの概念的な理解を簡素化し、そのようなオブジェクトやモジュールなど既存の高レベルな抽象化と調和して働くことによって、プログラムのメンテナンス性の向上に役立ちます。" と記載されています。
私たちは実際に、これらの利点は、内部的に使用されているだけでなく、同様にPythonプログラマに公開されているほど重要であると考えています。

これは、Pythonプログラマは非常にシンプルなインターフェイスを与えるだろう:

with atomic:
<これらの操作はアトミックに実行されます>

（これは古い考え方です。私を含め2003人の人々はこれを面白いハックだと考えました。
いま私がブログ記事を書き、"それはハックではなかった、それは明確にハックされたロックを使用している。"と主張します。私は、composabilityのアイデアを買っています。）

実用的な観点から、私はロチェスター大学STM（RSTM）において、最近の研究の焦点となっているC++ライブラリ --- と結果のコレクション --- を真剣に探し始めた。
特に代表的な論文の一つが、Michael F. Spear、Luke Dalessandro、Virendra J. MaratheとMichael L. Scottによる
A Comprehensive Strategy for Contention Management in Software Transactional Memoryです。

CONCLUSION

これらのアイデアを取り、Pythonのような複雑な高水準言語の実装のコンテキストでこれらを適用すると、独自な難問が出てきます。
このコンテキストでは、PyPyを使用することは、実験プラットフォーム、また最近ではそのパフォーマンスのために注目されているプラットフォームにおいて道理にかなっています。
代替手段は興味ありません：例えばCPythonのでそれを行うと、グローバルインタプリタを書き換えることを意味します。
PyPyは代わりに、私たちは翻訳時に体系的に適用される変換としてそれを書きます。
また、PyPyは動的言語のために高速なインタプリタを生成するための一般的なプラットフォームです; PyPyにおいてSTMの実装だけではなく、同様にPython用だけではなく、他の言語の実装のために、Pythonの制約から抜け出して動作します。

Update:

これはほとんど私（Armin Rigo）が声を出して暴れる実験をしています; PyPyチーム全体が現在それに取り組むために、次の数年をフルタイムで費やすことを意味する記事と混同するべきではありません。
私が述べたようにそれは実際のPythonインタプリタに直交しており、それはいかなる場合でも、翻訳時にオンまたはオフにすることができる機能です;
私が知っている多くのまたはほとんどのユースケースでは、人々は2倍遅くしかしスケールするものより、むしろ速いPyPyに興味を持ち、手に入れたいと考えています。
私が言ったものはまったく本当に新しくありません。
証明のため、Riley and Zilles (2006)とTabba (2010) の両方は、私がここで説明したように、開始/終了のトランザクションにCPythonのかPyPyインタプリタのGILを回し、ハードウェアトランザクショナルメモリを試したので、参照して下さい。

（原文：Posted by Armin Rigo）
（翻訳：Tohru Ike）

PyPy 1.6 - kickass panda

2011-08-19T11:12:00.006+09:00

原文はこちら: PyPy 1.6 - kickass panda

私たちは、PyPy1.6のリリースを発表できることを嬉しく思います。このリリースでは、多くのバグ修正と1.5以上のパフォーマンスの向上をもたらし、Windows32とOS X 64bitのサポートの向上をします。このバージョンでは、Python2.7.1を完全に実装し、CPythonのC拡張読み込みをベータレベルサポートしています。ここからダウンロードできます。

http://pypy.org/download.html

PyPyとは？

PyPyは、非常に準拠しているPythonインタプリタであり、ほぼ、簡単にCPython2.7.1を代替できます。それはトレーシングJITコンパイラを統合しているため、高速です。（pypy1.6とCPython2.6.2のパフォーマンス比較）

このリリースでは、x86マシンで実行しているLinuxの64/32または、Mac OS Xがサポートされています。Windows 32はベータです（ほぼ動作しますが、多くの小さな問題はこれまで修正されていません）

このリリースの主なトピックは、スピードと安定性です: 私たちのベンチマークスイートの平均において、PyPy1.6は既に私たちのベンチマークではCPythonより高速なPyPy1.5より20%から30%速いです。

速度の改善はPyPyを構成する多くの層を最適化することで実現しました。
とりわけ、私たちはガーベージコレクタ、JITのウォームアップ時間、JITによって実行される最適化、生成されたマシンコードの品質とPythonインタプリタの実装を改善しました。

ハイライト

多数のパフォーマンス向上は、全体にかなりのスピードアップをもたらします:
- 非常に大きなオブジェクトや配列を扱う時のGCの振る舞い。
- fast ctypes:現在呼ばれるctypes関数はJITによって最適化され、PyPy1.5より60倍高速で、CPythonより10倍高速である。
- ジェネレータの改良(1): 単純なジェネレータは現在、ループ呼出しをインライン展開しており、PyPy1.5より3.5倍高速化し、パフォーマンスアップしました。
- ジェネレータの改良(2): 他の最適化のおかげで、ジェネレータはインライン化されてなくともPyPy1.5より10%から20%速いです。
- JITの高速なウォームアップ時間。
- single floatのJITサポート (e.g., for array('f'))。
- 最適化された辞書: 辞書の内部表現は、現在、動的に保存されているオブジェクトの種類に応じて適宜選択します。高速なコードと小さなメモリフットプリントの結果です。例えば、キーがすべて文字列、またはすべて整数である辞書。他の辞書でもバグ修正のため、より小さくなります。

これはあなたのPythonコードがJITによってコンパイルされアセンブリまで落とし込まれたものを確認するウェブベースツールであるJitViewerを含む最初の公式リリースです。
jitviewer 0.1は既にリリースされておりPyPy1.6でうまく動いています。

CPythonの拡張モジュールAPIが改善され、より多くの拡張機能をサポートしています。何がサポートされているかの情報については、私たちの互換性wikiを参照してください。

マルチバイトエンコーディングのサポート：これはCPythonが原因となって残っていた最後の領域でした。しかし、今私たちはそれを完全にサポートしています。

numpyのための準備的サポート：このリリースでは、PyPy JITと統合された非常に高速なnumpyのモジュールのプレビューが含まれています。残念ながら、これは、あなたが既存のnumpyのプログラムを作って、PyPyでそれの実行を期待できるということを意味するものではありません。なぜならば、モジュールはまだ未完成であり、numpyAPIのいくつかをサポートしているためです。しかしながら、いくつかの詳細を除いて、その仕組は非常に高速でなければなりません:-)

バグ修正: 1.5リリース以来、私たちはバグトラッカーにある53のバグを修正しました。私たちが発見し、バグトラッカー以外の経路を介して報告された多くののバグはカウントしていません。

喝采を贈る

Hakan Ardo, Carl Friedrich Bolz, Laura Creighton, Antonio Cuni, Maciej Fijalkowski, Amaury Forgeot d'Arc, Alex Gaynor, Armin Rigo とPyPyチームへ

（原文：Posted by Maciej Fijalkowski）

（翻訳：Tohru Ike）

JITされたコードの視覚化

2011-08-15T00:16:00.008+09:00

原文はこちら: Visualization of JITted code

こんにちわ。

私たちはjitviewerの最初の公式リリースを発表できることを誇りに思います。
現在のところ、jitviewerはPyPyのJITによってマシンコードにコンパイルされた
Pythonソースコードの理解を助けるちょっとした内部ツールです。

インストールするには、PyPyのごく最近のバージョン（8月9よりも新しい）、例えば、ナイトリービルドのいずれかが必要です:

pipとdistributeをインストールするまたは、PyPyで作られたvirtualenvか、次の述べるinstallation instructions

PyPyのソースコードチェックアウトし、PYTHONPATHに確実に入れてください。

pip install jitviewer。グローバルにインストールされたpipではなく、PyPyの管理下にあるpipを実行する必要があることに注意して下さい。

jitviewerをはじめるにはREADMEを見るまたは、それをただ実行したいならオンラインデモを試みてください。

jitviewerはflaskとjinja2で書かれたWebアプリケーションです。
ウェブ開発経験があって、PyPyを助けたいなら、私たちに遠慮無く連絡してください。PyPyを向上する多くのことがあります :-)

本当のところjitviewerは何をするのでしょうか？

ページの上部には、JITでコンパイルされたコードの一部分のリストが表示されます。
あなたは通常のループと"エントリブリッジ"の両方を確認することができます。ここでは、それらの違いについて議論する適当な場所ではありませんが、たぶんあなたは、通常はほとんどの時間が費やされている場所なので、ループをもっとも見たがっているでしょう。

各ループにおいて、ループの最初の命令を含んだ関数の名前が表示されることに注意してください。
しかしながら、JITによって行われるインライン化のおかげで、それに他の関数のコードが含まれます。

あなたがひとたびループを選択すると、jitviewerはJITがどのような階層的な方法でPythonソースコードをアセンブラにコンパイルしたのかを示します。それは4つのレベルで表示します:

Pythonソースコード: 空色で示された行だけが、この特定のループのためにコンパイルされており、灰色のものはそうではありません。

Pythonバイトコード, あなたが実行することによって得るもの:

def f(a, b):

   return a + b

import dis

dis.dis(f)

命令コード(opcodes)は、例えば LOAD\_FAST, LOAD\_GLOBAL などです。
太字になっていない命令コード(opcodes)は、完全にJITで常に最適化されています

JITコードの中間表現(IR)。これは操作（整数加算のような、構造体のフィールド読み出し）とガード（私達の仮定が実際に真であることを確認する）の組合せです。ガードは赤色です。それらの操作は"Cと同じレベルで": そう、例えば、+は、CPUのレジスタに格納された2つのボックス化が解除された整数を取ります。

アセンブラ: あなたは、右上メニューの"Show assembler"をクリックして、それを確認することができます。

時に、ガードが頻繁に失敗し、アセンブラの新しい部分が呼ばれてコンパイルされた事がわかるでしょう。
これはコードを通した迂回経路であり、そして、それはブリッジと呼ばれます。
ガードの横にリンクがある時には、jitviewerでブリッジを見ることができます。

詳しい情報の成果を得たいのであればjit documentationを探して下さい。

いまだに混沌としています

私が現状について説明すると、Jitviewerは完全ではありません。
あなたが、IRC上に現れたり、私たちのメーリングリストへメールを送ることは自由であり、また私たちはそれを説明し、解決策を改良するでしょう。
詳細については、お問い合わせのページを参照してください。

Cheers,
fijal & antocuni

（原文：Posted by Maciej Fijalkowski）

PyPyはCより速い。あらためて：stringフォーマッティング

2011-08-03T09:31:00.017+09:00

原文はこちら: PyPy is faster than C, again: string formatting

stringフォーマッティングは、おそらくPythonであなたが通常することであり、あえて考えたりはしないでしょう。
それはとても簡単で、まさに"%d %d" % (i, i)すれば完了です。
結果のバッファをどのように測るかは考えません。あなたの出力の最後に適したNULLバイトを持っているようと、または他の細かい事があろうと。Cに相当するのは次のようになります：

char x[44];
sprintf(x, "%d %d", i, i);

２行目のところで立ち止まり、数がどれくらい大きくなるかもしれないかを考慮して、サイズを過大評価しなければならなかったことに注意してください。
(44 = 64ビット上で最も大きい数の長さ(20) + 1 (符号のための) * 2 + 1 (空白のための) + 1 (NULバイト))
この投稿の著者、fijalとalexはこの３つの計算の試みを異議なしで実現しました :-)

この関数からxを返すことができない場合を除きすばらしいです。よりよい比較は次のようになります。

char *x = malloc(44 * sizeof(char));
sprintf(x, "%d %d", i, i);

xはいくらかの状況でわずかに過剰割り当てされますが、すばらしいです。

しかし、ただstringフォーマッティングの実現について議論するために、私たちはここいるわけではなく、速いPyPyを明確に新たなunroll-if-altブランチとともに示し、議論するためにここにいます。Pythonは次のコードをもたらします：

def main():
    for i in xrange(10000000):
        "%d %d" % (i, i)

main()

Cコード：

#include 
#include 


int main() {
    int i = 0;
    char x[44];
    for (i = 0; i < 10000000; i++) {
        sprintf(x, "%d %d", i, i);
    }
}

PyPyのunroll-if-alt branchブランチのheadで実行し、コンパイルはGCC4.5.2 -O4（他の最適化レベルをテストし、これが最高のパフォーマンスをもたらした）。PyPyで実行すると0.85秒、コンパイル済みのバイナリで実行すると1.63秒かかりました。
私たちはこれは動的コンパイルの信じられないほどの可能性を示すと考えおり、GCCはsprintfの呼び出しをインライン化またはアンロールすることができません。理由はlibcが内部に位置しているためです。

Cのベンチマークコード：


#include 
#include 


int main() {
    int i = 0;
    for (i = 0; i < 10000000; i++) {
        char *x = malloc(44 * sizeof(char));
        sprintf(x, "%d %d", i, i);
        free(x);
    }
}

前に議論されたとおり、これはPythonに匹敵し、1.96秒の結果が得られます。

パフォーマンスの結論：

Platform	GCC (stack)	GCC (malloc)	CPython	PyPy (unroll-if-alt)
Time	1.63s	1.96s	10.2s	0.85s
relative to C	1x	0.83x	0.16x	1.9x

全体的にPyPyは2倍速いです。これは明らかに、静的より動的コンパイラが優っています。 - sprintf関数はlibcにあり、不変な文字列に特化することができず、実行されるときはつねに、文字列を評価しなければなりません。
PyPyのケースでは、私たちは、剰余演算子の左側の文字列が不変であると検出すれば、アセンブラに特化することができます。

Cheers,
alex & fijal

（原文：Posted by Maciej Fijalkowski）

Pythonでのリアルタイム画像処理

2011-07-08T02:04:00.009+09:00

原文はこちら: Realtime image processing in Python

画像処理は、CPUを酷使する悪名高い仕事です。
ですので、リアルタイムで画像処理をするのにPythonで試みるのは馬鹿げており、高速な言語でアルゴリズムを実装する必要があります。
Pythonは明らかにこのタスクに十分な速度がありません。そうですよね？

実際には、画像処理において、PyPy JITコンパイラはリアルタイムのビデオ処理を行うために十分な速さのコードを生み出すことが判明しました。

sobel.pyは、画像、Sobel operatorのエッジを強める古典的な方法を実装しています。それは、グラデーションの大きさの近似値です。

処理時間は画像と3x3カーネルの間の2つの畳み込み処理に費やしています。
この処理は、入力画像を出力画像へピクセルを越えてコピーするシングルループで構成されています。

あなたは適切ななデモをダウンロードしてあなた自身で試すことができます。

pypy-image-demo.tar.bz2: このアーカイブはソースコードのみを含んでいます。これは既にインストールされているPyPyを必要とします。
pypy-image-demo-full.tar.bz2: このアーカイブは、Linux32bitと64bitのソースコードとビルド済みのPyPyバイナリの両方が含まれています

デモを実行するには、MPlayerがシステムにインストールされている必要があります。デモはLinux上でのみテストされて、それが他のシステムでも動作する（か動作しないかもしれません）可能性があります。


$ pypy pypy-image-demo/sobel.py


$ pypy pypy-image-demo/magnify.py

デフォルトでは、２つのデモはサンプルのAVIファイルを使用します。
より多くの楽しみを得るために、例に従いMPlayerに適切なパラメータを渡すことで、ウェブカメラを使用することができます。


$ pypy demo/sobel.py tv://

デフォルトではmagnify.pyは近傍法を使用します。
オプション-bを追加することにより、バイリニア補間が代わりに使用され、より滑らかな結果が与えられます。


$ pypy demo/magnify.py -b

magnify.pyのアルゴリズムの実装はただ一つしかありません。
二つの異なった挿入メソッドは実装されます。クラスのサブクラス化に
画像を表現し、補間を埋め込むピクセルアクセスメソッドの内側でよく使われます。

PyPyは画素アクセス法をインライン化し、アルゴリズムの実装を特化できるので、良好なパフォーマンスをこの抽象化で達成することができます。
C++では、画素アクセス法のようなものは仮想的になり、実行時のオーバーヘッドを招くことなく同じ効果を得るためにテンプレートを使用する必要があります。

上記のビデオは、PyPyとCPythonが並んでsobel.pyを実行しているところです。
（PyPyはウェブカメラから入力を受け、CPythonはテストファイルから入力を受けます）
また、PyPyがCPythonよりどのくらい高速であるか実感したいならば、後でデモを走らせて下さい。これらは、上記tarballリンクの標準のtest.avi ビデオとPyPyプレビルドバイナリを使用した際のマシン（(Ubuntu 64 bit, Intel i7 920, 4GB RAM)）での平均したfps(frames per second)です。
sobel.pyの場合:

PyPy: ~47.23 fps
CPython: ~0.08 fps

magnify.pyの場合:

PyPy: ~26.92 fps
CPython: ~1.78 fps

これはsobel.pyでは、PyPyが590倍速いことを意味しています。
magnify.pyでは、それほど違いは明白ではなく高速化は"たった"15倍です。

このことはPyPyができる極端な例であることに注意しなければいけません。
とりわけ、期待してはいけません（まだ :-)）

これがPyPyができることの極端な例であることに注意しなければなりません。特に、あなたは予想できません(まだ(^o^))。リアルタイムのときに任意のビデオ処理アルゴリズムを走らせるほど速いPyPy、デモだけがPyPyにはそこに到着する可能性があるとまだ立証しています。
PyPyに、リアルタイムで任意のビデオ処理アルゴリズムを実行するのに十分な速さを期待することはできません。しかしデモの結果は、PyPyが十分な速度を達成する可能性を秘めていることを証明しています。

（原文：Posted by Antonio Cuni）

グローバルインタプリタロックを無くす方法

2011-06-30T23:44:00.014+09:00

原文はこちら: Global Interpreter Lock, or how to kill it

EuroPythonで私（Armin Rigo）のライトニングトークを聴いた人は、突然知ったでしょう。我々はグローバルインタプリタロック---悪名高いGIL、複数のスレッドが実際にPythonコードへ干渉するのを防ぐCPythonのものです ---を取り除く計画を持っています。

それは画期的なものではありません。なぜならJythonは既にGILを取り除くことに対応しています。
Jythonは非常に慎重に全ての変更可能な組み込み型にロックを追加し、それらに対して、効率的になるよう基盤にあるJavaプラットフォームを頼っています。（結果は非常に慎重にCPythonで同様なロックを追加するより速いです）
"非常に慎重"は本当の本当に慎重を意味します。
例えば、'dict1.update(dict2)' はdict1とdict2の両方をロックする必要があります。しかし、あなたが安易にしてしまうなら、'dict2.update(dict1)'はデッドロックを生じる可能性があります。

PyPy、CPython、IronPythonとすべてはGILを持っています。
しかし、我々はPyPyに対して、Software Transactional Memory（ソフトウェアトランザクショナルメモリ）に基づく、Jythonとは大きく異なるアプローチを検討しています。
ソフトウェアトランザクションメモリはコンピュータサイエンスにおける近年の研究成果であり、ロックより良い解決策を提供します。
ここでソフトウェアトランザクションメモリについて、簡単に紹介します。

あなたが"list1"から項目をpopして"list2の'にpopしたものを追加したいとしましょう：


def f(list1, list2):
    x = list1.pop()
    list2.append(x)

これは、マルチスレッドとして安全な例ではありません（GILであるとしても）。
つまり、スレッド1でf(l1, l2)とスレッド2でf(l2, l1)を呼び出した場合です。

あなたが望む動作として、全く効果がないということです。(xは一方のリストからもう一方のリストまで動かされた後、元に戻ります)
しかし、それは、二つのリストのトップは入れ替わる代わりに、タイミングの問題によって起こることがあります。

これを治す一つの方法は、グローバルロックを使用することです:


def f(list1, list2):
    global_lock.acquire()
    x = list1.pop()
    list2.append(x)
    global_lock.release()

これを修正するより良い方法は、リストが備えているロックを使用することです:


def f(list1, list2):
    acquire_all_locks(list1.lock, list2.lock)
    x = list1.pop()
    list2.append(x)
    release_all_locks(list1.lock, list2.lock)

２番目の解決策はJythonのモデルです。そしてもう一方の１番目はCPythonのモデルです。CPythonインタプリタでGILを獲得し、一つのバイトコード（実際は100のような実数）にし、そしてGILを解放します。
そしてさらに、100の次の分岐を続けます。

ソフトウェアトランザクションは３番目の解決策をもたらします:


def f(list1, list2):
    while True:
        t = transaction()
        x = list1.pop(t)
        list2.append(t, x)
        if t.commit():
            break

この解決策では、トランザクションオブジェクトを作成し、すべてのリストへの読み書きで使用します。
それはは実際にいくつかの異なるモデルがありますが、そのうちの一つに注目してみましょう。
トランザクション中に、我々は実際にはまったくもってグローバルメモリを変更しません。その代わりに、スレッドローカルトランザクションオブジェクトを使用します
。

我々はそのオブジェクトに、どれから読むか、どのオブジェクトに書くか、何の値を書くか格納します。
それは、トランザクションに達した時、私たちはコミットの試みに達するのみです。
コミットは失敗するかもしれません。もし他のコミットがその間に発生した場合、矛盾が発生します。その場合、トランザクションは中止し、再度はじめから処理をやり直さなければなりません。

前の2つの解決策がCPythonとJythonのモデルであるのと同様に、STMの解決策は、PyPyの将来におけるモデルであるかのように見えます。
PyPyインタプリタは、トランザクションを開始、複数のバイトコードを実行、トランザクションを終了という処理をとてもよく繰り返します。
これはCPythonのGILが行っていることと大変似通っています。
特に、この処理はプログラマがGILの場合と同様に、同一の保証を与えられることを意味します。
唯一の違いは、コードがお互いを妨げない限り、マルチスレッドで並列に実行できるということです。
(とりわけ、あなたが既存のマルチスレッド化されたプログラムにおいて、GILだけではなく実際のロックも必要とするなら、これは不思議にもそれらの必要性を削除しません。
あなたがロックよりそれを好むなら、PythonプログラムにSTMを触れさせる特別な組み込みモジュールを取得する可能性がありますが、それは別の質問です）

なぜそのアイデアをCPythonに適用しないのでしょうか？
なぜならば、私たちはいたるところを変更する必要があるからでしょう。先程の例で説明すれば、
私はもう 'list1.pop()'と呼出しをしません。必ず呼出しは'list1.pop(t)'です。これはすべて実装を"トランザクション的な"動きを行うために、変える必要があると言うことです。

これは、代わりに実際にリストが格納されているグローバルメモリを変更することを意味します。つまり、代わりのトランザクションのオブジェクトの変更を記録しなければなりません。
私たちのインタプリタがCPythonのようにC言語で記述されている場合、我々は、明示的にいたるところでそれを書く必要があります。
それはより高いレベルの言語ではなく、書かれている場合など、変換ルールのセットとして、PyPyはそのまま、次に我々はこの動作を追加することができ、それが必要な場所であればどこでもそれらを自動的に適用されます。

それがPyPyのようなより高いレベルの言語で代わりに記述されているのであれば、
我々は変換規則のセットとして、この振舞いを加えることができますとともに、自動的にどこにでも、変換規則が必要であるところに振る舞いを適用します。
また、変換時のオプションを指定することができます。
あなたはGILがある現在の"pypy"、または、余分な出力処理のためより遅いでしょうがSTMがあるバージョンを得ることができます。
（どのくらい遅いかって？私はさっぱりわからないけど、荒っぽい推測として、２〜５倍程度遅いかもしれません。
十分なコアがある場合は、その限りスケールしすばらしいですよ。 :-）

最終的な注記：STMの研究は、ごく真新しく（2003年頃開始）、多くの亜種があり、どの場合にどれがより優れているかは、まだ明らかではありません。
私が判断できる限り、"A Comprehensive Strategy for Contention Management in Software Transactional Memory"（日本語注記：ソフトウェアの取引のメモリにおける主張管理のための包括的戦略）で説明されたアプローチは、1つが最先端であるということであるように思えます。それはまた、"すべてのケースに十分良い"ように思えます。

それで、いつグローバルインタプリタを取り除くことをするのでしょうか？私はまだ明言することができません。
それはまだアイデアの段階ですが、私はそれが実現できると思います。それを書くには私たちはどのくらいの時間を取るでしょうか？
再びさっぱりわかりません、しかし、我々は何日ではなく何ヶ月であると調べています。
これは私がユーロの資金が9月1日がなくなった後も、フルタイムで作業できるようにしたいと思ったりなど...。

現在、私たちは私が着手できるように金を工面するのにcrowdfundingを使用する方法を調べています。とってもすぐにブログ記事のポストを期待していてください。
しかし、これはcrowdfundingするうってつけの候補者に似ています。 --GILを無くすために10ユーロを支払うことをいとわない何千人ものあなた方が一応は存在します。今、私たちはこれを実現するだけです。

（原文：Posted by Armin Rigo）

調査の報告

2011-06-25T15:24:00.013+09:00

原文はこちら: Report back from our survey

やぁ、みんな。

私は調査の結果を報告します。
まず最初に、私たちは多くのユーザーがPyPyを快くプロダクトで使うというレポートにとっても喜んでいます。
回答者の多く（97%）はPyPyは速いという理由で使用しています。
しかし、26％（回答者は複数回答を選択できる）で、メモリ使用量が少ないという理由でPyPyを使用しています。
PyPy使用していないユーザーのうち、最も一般的な理由は、"その他"に続きC拡張でした。

みんなからのコメントを読んでから私たちが学んだことがいくつかあります：

Google docsはこのような物よりよいUIを必要としています。

とても多くの人々がNumPyとSciPyを望み、C拡張を望んでいます。（25%の回答者はなんとかNumPyを使いたいと言った。）
私たちは既にNumPyに関するプランを話題にした記事を書きました。

様々なOSのリポジトリにパッケージを持つことは、ユーザーの勉強と実行に大きな助けとなるでしょう。

すべての回答者の多大な貢献に感謝します！
最後に、もしあなたがPyPyをプロダクションで使っているのであれば、私たちはあなたに多いに感謝します。
そして、もし時間を割くことができるのであれば、メーリングリスト経由で連絡を下さい。

Thanks, Alex

(原文：Posted by Alex)