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

原文はこちら

トレーシングと部分評価の比較 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 言語のための単純なトレーサ

原文はこちら

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

原文はこちら

私の博士論文の一部として、私は今 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

原文はこちら: 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 - スイートスポットの拡大

原文はこちら: 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）

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

原文はこちら: 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バイトコードごとにリリースするという事実を無視してください。その時これを意味しています。

1. 私たちは、任意のバイトコードの前にGILを（トランザクションを開始する）を取得し、バイトコードの後に私たちは、それ（トランザクションを終了する）を放します; そして
2. 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）