マニュアル：JITからPyPyへのインタープリターの作成

この記事のすべてのソースコードと例は、こちらから入手できます 。

PyPyプロジェクトを初めて見たとき、それが何であるかを理解するのに時間がかかりました。 次の2つの要素で構成されます。

-プログラミング言語のインタープリターを作成するためのツールのセット。
-このツールキットを使用したPython実装。

ほとんどの人はおそらくPyPyは第2部に過ぎないと考えていますが、このガイドはPythonインタープリターに関するものではありません。 それはあなたの言語の通訳を書く方法についてです。

このガイドは、PyPyがどのように機能し、どのようなものであるかをよりよく理解するためのものです。 あなたはPyPyについてほとんど知らないと想定しているので、最初から始めます。

PyPyとは何ですか？

インタプリタを書きたいとします。 これには、ソースコードパーサー、バイトコード実行ループ、および標準ライブラリ内の多くのコードの記述が含まれます。

パーサーとコンパイラーの作成は、通常はまったく面白くないため、パーサーとコンパイラーを生成するツールがあります。

そして、それでもあなたはインタプリタのメモリ管理に注意を払わなければならず、任意の次元の整数、ハッシュテーブルなどのようなデータ型を実装しなければなりません。 これは、多くの人が独自のインタプリタの実装について考えを変えるのに十分です。

たとえば、Pythonのような高レベル言語で言語を実装できたら素晴らしいと思いませんか？ 自動メモリ管理や豊富なデータ型セットなど、高級言語のすべての利点を自由に活用できます。 しかし、ある言語を別のインタプリタ言語で解釈するのは非常に遅いはずですよね？

ご想像のとおり、PyPyはこの問題を解決します。 PyPyは、C（またはJVMまたはCLI）でインタープリターコードを分析および翻訳するための洗練されたツールキットです。 このプロセスは「翻訳」と呼ばれます。 彼は、Pythonの構文のすべてではなく、その大部分を翻訳する方法を知っています。 必要なことは、Python言語のサブセットであるRPythonでインタープリターを作成することだけです。その後、非常に効率的なインタープリターが得られます。

効果的な通訳を書くことは問題ではないからです。

言語

実装することを選択した言語は非常に単純です。 言語フレームは、ゼロに初期化された整数のテープと、このテープの現在のセルへの1つのポインターで構成されます。 言語には8つのコマンドしかありません。

< -ポインタを前のセルに移動します。

> -ポインタを次のセルに移動します。

+ -現在のセルで数値を1つ増やします。

--現在のセルで1つの数値だけ減少します。

[ -現在のセルの数が0の場合、対応する命令まですべての命令をスキップします]。

] -対応する命令[。に戻ります。

。 -現在のセルから1バイトを標準出力ストリームに出力します。

、 -標準入力ストリームから1バイトを読み取り、現在のセルに入れます。

認識されない文字は無視してください。

この言語を学べる人もいますが、これは頭脳です。

言語自体はすでにバイトコードであるため、ソースコードをバイトコードに個別に変換する必要はありません。 これは、インタープリターのメイン実行ループがソースコードで直接動作することを意味します。 これにより、実装が少し簡素化されます。

最初のステップ

通常のPythonでインタープリターを作成することから始めましょう。 メインの実行ループのスケッチを次に示します。

def mainloop(program): tape = Tape() pc = 0 while pc < len(program): code = program[pc] if code == ">": tape.advance() elif code == "<": tape.devance() elif code == "+": tape.inc() elif code == "-": tape.dec() elif code == ".": sys.stdout.write(chr(tape.get())) elif code == ",": tape.set(ord(sys.stdin.read(1))) elif code == "[" and value() == 0: # Skip forward to the matching ] elif code == "]" and value() != 0: # Skip back to the matching [ pc += 1 

ご覧のとおり、命令カウンター（pc）には現在の命令へのポインターが格納されています。 ループの最初の式が命令を取得し、その後、いくつかの条件ステートメントがその実行方法を決定します。

「[」および「]」演算子の実装は省略されており、命令カウンターを一致する括弧の位置に変更する必要があります。

そして今、整数のテープと現在の番号へのポインタを格納するTapeクラスの実装です。

 class Tape(object): def __init__(self): self.thetape = [0] self.position = 0 def get(self): return self.thetape[self.position] def set(self, val): self.thetape[self.position] = val def inc(self): self.thetape[self.position] += 1 def dec(self): self.thetape[self.position] -= 1 def advance(self): self.position += 1 if len(self.thetape) <= self.position: self.thetape.append(0) def devance(self): self.position -= 1 

ご覧のとおり、必要に応じてテープが増加します。 実際、ポインターが負になったときにエラーチェックを追加する価値があります。 しかし、これまでのところ問題ではありません。

プログラムに多くのコメントがある場合、それらは1バイトで読み取られるため、事前にソースコードを解析することをお勧めします。 同時に、括弧の辞書を作成して、ペア括弧を見つけることができます。

 def parse(program): parsed = [] bracket_map = {} leftstack = [] pc = 0 for char in program: if char in ('[', ']', '<', '>', '+', '-', ',', '.'): parsed.append(char) if char == '[': leftstack.append(pc) elif char == ']': left = leftstack.pop() right = pc bracket_map[left] = right bracket_map[right] = left pc += 1 return "".join(parsed), bracket_map 

この関数は、言語コマンドとペア括弧の辞書からのみ文字列を返します。

これを結合することは残っており、実用的なブレインファックインタープリターを取得します。

 def run(input): program, map = parse(input.read()) mainloop(program, map) if __name__ == "__main__": import sys run(open(sys.argv[1], 'r')) 

角括弧の実装を含むインタプリタの完全なコードは、最初の例で見ることができます。 example1.py

これで、インタプリタをPythonで実行して、動作することを確認できます。

$ python example1.py 99bottles.b

PyPyブロードキャスト

しかし、私たちの目標は、ブレーンファックインタープリターを書くことだけではありません。 PyPyがこのコードから超高速の実行可能ファイルを作成するには、何をする必要がありますか？

PyPyソースのpypy / translator / goalフォルダーには、便利な簡単な例があります。 始めるには、targetnopstandalone.pyをご覧ください-PyPyのシンプルなハローワールドです。

重要なことは、モジュールにエントリポイントを返すターゲット関数が含まれていることです。 この時点から放送が始まります。

 def run(fp): program_contents = "" while True: read = os.read(fp, 4096) if len(read) == 0: break program_contents += read os.close(fp) program, bm = parse(program_contents) mainloop(program, bm) def entry_point(argv): try: filename = argv[1] except IndexError: print "You must supply a filename" return 1 run(os.open(filename, os.O_RDONLY, 0777)) return 0 def target(*args): return entry_point, None if __name__ == "__main__": entry_point(sys.argv) 

entry_point関数は、結果の実行可能ファイルを実行するときにコマンドライン引数を受け入れます。

RPython

RPythonについて話しましょう。 Pythonは動的すぎるため、PyPyは通常のPythonコードを翻訳できません。 PyPyが変換できるように、標準ライブラリとPython構文に適用されるいくつかの制限があります。 それらをすべてリストするのではなく、ドキュメントで確認する方が良いでしょう。

上記の例では、いくつかのことを変更する必要がありました。 ここで、ファイルオブジェクトを使用する代わりに、os.openおよびos.read関数で低レベルの記述子を使用する必要があります。 「。」および「、」の実装もわずかに変更されています。 これらはすべて、PyPyがコードを消化するために必要な変更です。

それほど複雑ではなかったでしょう？ 辞書、拡張可能なリスト、さらにオブジェクトを含むクラスでさえ使用し続けます。 また、ファイル記述子が低すぎる場合は、rlib.streamioモジュールにいくつかの便利な抽象化があります。これは標準のRPythonライブラリに付属しています。

完全なコードは次のようになります： example2.py

放送

まだ行っていない場合は、bitbucket.orgのリポジトリから最新バージョンのPyPyをマージします。

$ hg clone bitbucket.org/pypy/pypy

実行するスクリプトはpypy / translator / goal / translate.pyです。 パラメータとして、翻訳が必要なモジュールが必要です。

$ python ./pypy/pypy/translator/goal/translate.py example2.py

翻訳を高速化するには、Pythonの代わりにPyPyを使用できます。

実行の結果は、実行可能ファイル-Brainfuckインタープリターになります。 リポジトリにはBrainfuckのフラクタルジェネレータが含まれており、私のマシンで完了するには約45秒かかります。 自分で試してみてください。

$ ./example2-c mandel.b

そして、Pythonで実行されている同じインタープリターが生成する速度と速度を比較します。

$ python example2.py mandel.b

そこで、RPythonでインタープリターを作成し、PyPyツールキットを使用して翻訳しました。

JITを追加

CでのRPythonの翻訳はクールですが、PyPyの主な機能の1つは、ランタイムコンパイラ（JIT）を生成する機能です。 インタープリターの動作に関するいくつかのヒントを使用して、PyPyは、解釈されたBrainfuckコードをマシンコードに変換するJITコンパイラーを生成します。

これが起こるためには、PyPyはプログラム実行サイクルがどこから始まるのかを知る必要があります。 これにより、brainfuckで実行された命令を追跡できます。

実行サイクルの機能も示す必要があります。 私たちの言語にはスタックがないので、プログラム変数とそのデータに関連する変数を示すだけです。 これは、それぞれ緑と赤の変数と呼ばれます。

2番目の例に戻ります。

メインの実行ループでは、pc、program、bracket_map、tapeの4つの変数が使用されます。 もちろん、pc、program、bracket_mapは緑の変数であり、解釈されたプログラムの実行を決定します。 可変テープは赤で、解釈されたプログラムが実行されると変化します。

PyPyにこのデータを伝えましょう。 JitDriverクラスをインポートしてインスタンス化することから始めましょう。

 from pypy.rlib.jit import JitDriver jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape']) 

そして、実行ループの最初に次の行を追加します。

 fjitdriver.jit_merge_point(pc=pc, tape=tape, program=program, bracket_map=bracket_map) 

また、JitPolicyを定義する必要があります。

 def jitpolicy(driver): from pypy.jit.codewriter.policy import JitPolicy return JitPolicy() 

完全なサンプルテキスト： example3.py

コードを再度変換しますが、フラグ--opt = jitを使用します。

$ python ./pypy/pypy/translator/goal/translate.py --opt = jit example3.py

ブロードキャストははるかに長く、私のマシンではほぼ8分で実行され、結果の実行可能ファイルははるかに大きくなります。 放送終了後、フラクタル生成プログラムを再び開始します。 違いは非常に大きく、前バージョンの45に対して約12秒です！

ご覧のとおり、JITコンパイラーは解釈する代わりにマシンコードを実際に使用しました。 画像の最初の数行は十分に速く表示され、その後プログラムは加速され、残りはさらに速く表示されます。

トレーサーJITコンパイラーについて少し

JITコンパイラのトレースが一般的にどのように機能するかについて話す価値はあります。 解釈コードは正常に実行されます。 JITがインタープリター言語で頻繁に実行されるループ（brainfuck）に遭遇すると、ループにトレースのフラグが立てられます。 次回同じサイクルに達すると、実行された各命令のロギングがオンになります。

結果のログはオプティマイザーに送信され、その結果はマシンコードに変換されます。 このコードは、ループの後続の実行に使用されます。

結果のマシンコードは、受信された特定の条件下でのみ正しいです。 したがって、使用する前に、これらの条件がチェックされます。 マシンコードの代わりにテストが失敗した場合、インタープリターが再び起動します。

詳細については、 Wikipediaを参照してください 。

デバッグおよびトレースログ

JITの機能を確認できますか？

デバッグ情報を出力するために使用されるget_printable_location関数を追加しましょう。

 def get_location(pc, program, bracket_map): return "%s_%s_%s" % ( program[:pc], program[pc], program[pc+1:] ) jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'], reds=['tape'], get_printable_location=get_location) 

この関数は緑の変数を取り、期日を返します。 現在の実行可能なステートメントがアンダースコアで囲まれているBrainfuckコードを出力します。

サンプルコードをexample4.pyに再配置します。

次に、トレースログの出力を使用してテストプログラムを実行します（test.bは文字「A」を約15回出力するだけです）。

$ PYPYLOG = jit-log-opt：logfile ./example4-c test.b

ログファイルには、生成されたすべてのトレースのログが含まれており、どの命令がマシンコードにコンパイルされたかを確認できます。 このファイルは、不要な指示や最適化の方法を確認できるという点で便利です。

各トレースは、次のような行で始まります。
[3c091099e7a4a7] {jit-log-opt-loop

そして次の行で終わります：
[3c091099eae17d jit-log-opt-loop}

トレースヘッダーの直後に、シリアル番号と操作の数を含むコメントがあります。 私の場合、最初のトレースは次のようになります。

  1: [3c167c92b9118f] {jit-log-opt-loop 2: # Loop 0 : loop with 26 ops 3: [p0, p1, i2, i3] 4: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0) 5: debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0) 6: i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>) 7: i6 = int_add(i4, 1) 8: setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>) 9: debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0) 10: debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0) 11: i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>) 12: i9 = int_sub(i7, 1) 13: setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>) 14: debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0) 15: i10 = int_is_true(i9) 16: guard_true(i10, descr=<Guard2>) [p0] 17: i14 = call(ConstClass(ll_dict_lookup__dicttablePtr_Signed_Signed), ConstPtr(ptr12), 90, 90, descr=<SignedCallDescr>) 18: guard_no_exception(, descr=<Guard3>) [i14, p0] 19: i16 = int_and(i14, -9223372036854775808) 20: i17 = int_is_true(i16) 21: guard_false(i17, descr=<Guard4>) [i14, p0] 22: i19 = call(ConstClass(ll_get_value__dicttablePtr_Signed), ConstPtr(ptr12), i14, descr=<SignedCallDescr>) 23: guard_no_exception(, descr=<Guard5>) [i19, p0] 24: i21 = int_add(i19, 1) 25: i23 = int_lt(i21, 114) 26: guard_true(i23, descr=<Guard6>) [i21, p0] 27: guard_value(i21, 86, descr=<Guard7>) [i21, p0] 28: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0) 29: jump(p0, p1, i2, i3, descr=<Loop0>) 30: [3c167c92bc6a15] jit-log-opt-loop} 

debug_merge_pointの行を少し長くしすぎました。

このコードセクションには4つのパラメーターがあります。オブジェクトへの2つのポインター（p0とp1）と2つの数値（i2とi3）です。

最初の演算子「>」は4行目から始まります。 指示なしで実行され、完全に最適化されています。 このサイクルは常にテープの一部で機能し、現在のセルへのポインターは一定のままです。

5番目から8番目の行-演算子「+」。 まず、インデックスi2の配列要素がポインターp1から抽出され（6行目）、ユニットが追加され、i6に格納されます（7行目）。 結果は配列に戻されます（8行目）。

9行目は「<」命令に対応していますが、操作も必要ありません。 どうやら-i2とi3は、事前に計算されたテープセルへの2つのポインタです。 また、p1がコマンドラインであることもわかります。 p0が何であるかは明確ではありません。

10行目から13行目は「-」演算子を実行します。つまり、配列の要素を抽出し、減算して元に戻します。

14行目では、演算子「]」に到達します。 行15および16は、i9が真（つまり、ゼロに等しくない）かどうかをチェックします。 i9は、1つ減らしてテープに入れた値です。 16行目-チェック。 条件が満たされない場合、<Guard2>という関数が実行され、1つのパラメーターp0が渡されます。

チェックに合格した場合、17行目から23行目は、bracket_map辞書から移動する命令のアドレスを取得します。 これらの行が正確に何をするのかはわかりませんが、2つの外部呼び出しと3つのチェックが含まれていることは明らかです。 Bracket_mapが変更されず、結果は移動先と同じアドレスになるため、これは無駄です。 しかし、PyPyはこれについては知りませんが、この場所を最適化できることはわかっています。

24行目は、bracket_mapから取得したポインターをインクリメントします。 25行目と26行目は、プログラムの長さを超えていないことを確認します。

さらに、行27は、ポインターが厳密に86に等しいことを確認する追加のチェックを実行します。これは、サイクルの開始時にジャンプを行う必要があることを確認するために必要です。

最後に、行28でサイクルが終了し、行29でパラメーターp0、p1、i2、i3でサイクルの先頭にジャンプします。

最適化

前述のように、ループの各反復で、辞書内で検索が実行され、ペアブラケットが検出されます。 これは非常に非効率的です。なぜなら、遷移の目標は異なる反復で変化しないからです。

辞書クエリが同じ辞書インデックスに対して常に同じ要素を返すと言うために、翻訳者にもう1つのヒントを与える必要があります。

これを行うために、ディクショナリが別の関数を呼び出し、pypy.rlib.jit.purefunctionでラップするようにします。

 @purefunction def get_matching_bracket(bracket_map, pc): return bracket_map[pc] 

このバージョンはexample5.pyにあります。

この例をブロードキャストします。 マンデルブロは12秒ではなく6秒で完了するようになりました！

新しいトレースログを見てみましょう。

  1: [3c29fad7b792b0] {jit-log-opt-loop 2: # Loop 0 : loop with 15 ops 3: [p0, p1, i2, i3] 4: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0) 5: debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0) 6: i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>) 7: i6 = int_add(i4, 1) 8: setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>) 9: debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0) 10: debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0) 11: i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>) 12: i9 = int_sub(i7, 1) 13: setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>) 14: debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0) 15: i10 = int_is_true(i9) 16: guard_true(i10, descr=<Guard2>) [p0] 17: debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0) 18: jump(p0, p1, i2, i3, descr=<Loop0>) 19: [3c29fad7ba32ec] jit-log-opt-loop} 

はるかに良い！ 現在、各サイクルは、加算、減算、配列からの2つのロード、配列内の2つの場所、および終了時のチェックのみです。 このコードでは、コマンドカウンターを変更する必要はありません。

この最適化は、pypy-devメーリングリストでArmin Rigoによって提案されました。 Karl Friedrichには、インタープリターの最適化に関するいくつかの記事があり、それらも有用であることが証明されています。

おわりに

この記事で、PyPyが高速なPythonインタープリターではないことを納得していただければ幸いです。

PyPy JITコンパイラについて詳しく知りたい方は、記事「メタレベルのトレース：PyPyのトレースJITコンパイラ」を読むことをお勧めします。