# pypy StatusBlog
### pypyができること
インタープリタ型の言語を書く時に、様々なソースコードパーサ、バイトコード(コードがバイト単位で構成)、多くのの標準ライブラリ（通例的に言語の各実装に備えられているもの）のコードを書く必要がある
私が初めてPyPyプロジェクトを知ったとき、それが何なのかを正確に理解するのに時間がかかりました。まだ知らない人のために説明すると、PyPyには2つの要素があります。
インタプリタ型言語のインタプリタを実装するためのツール群
このツールチェインを使ったPythonの実装
2番目の部分はおそらく多くの人がPyPyだと思っているものですが、このチュートリアルはPyPyのインタープリタについてではありません。このチュートリアルは、あなた自身の言語のために独自のインタープリタを書くためのものです。
## PYPYの機能
ここでは、PyPyができることについて簡単に説明します。例えば、インタプリタ型の言語を書きたいとします。そのためには、ある種のソースコードパーサー、バイトコード解釈ループ、そしてたくさんの標準ライブラリコードを書く必要があります。
お察しの通り、PyPyはこの問題を解決します。PyPyは、インタプリタコードを分析し、Cコード（またはJVMやCLI）に翻訳するための洗練されたツールチェーンです。このプロセスは「翻訳」と呼ばれ、Pythonの構文や標準ライブラリのかなり多くを翻訳する方法を知っていますが、すべてではありません。あなたがすべきことは、インタープリタをRPythonで書くことです。RPythonは、この種の分析と翻訳を可能にするために注意深く定義されたPython言語のサブセットで、PyPyはあなたのために非常に効率的なインタープリタを作成します。
## 言語(BF)
私が実装することにした言語は非常にシンプルです。言語のランタイムは、すべてゼロに初期化された整数のテープと、テープのセルの1つへの1つのポインタで構成されています。言語には8つのコマンドがあり、ここで説明します。
*>*
テープのポインタを右に1セル移動する
*<*
テープポインタを左に1セル移動させる
*+*
ポインターの下のセルの値を増加させる
*-*
ポインターの下のセルの値を減少させる
[
現在のポインタの下のセルが0の場合は、マッチングの後の命令にスキップする
]
マッチングにスキップして戻る [ (その条件を評価する)
.
ポインタの下のセルから 1 バイトを標準出力に出力します。
,
ポインタの下のセルに標準入力から1バイトを読み込んでください。
認識されないバイトは無視されます。
この言語に見覚えのある方もいらっしゃると思います。ここでは「BF」と呼ぶことにします。
ここで注目していただきたいのは、この言語はそれ自体がバイトコードであり、ソースコードからバイトコードへの変換はありません。つまり、この言語を直接解釈することができます。私たちのインタプリタのメインevalループは、ソースコード上で動作します。これにより，実装が非常に簡単になります．
最初のステップ
まず最初に，古いPythonでBFインタプリタを書いてみましょう．最初のステップは，evalループのスケッチです．
```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())) # stdoutは標準出力で1文字出力する
# chr()はASCIIcodeを文字に変換する。 0x41 なら A
elif code == ",":
tape.set(ord(sys.stdin.read(1)))
# ord()はchr()の反対で文字をASCIIcodeに変換する関数。
# stdin.read(1)は標準入力で1文字読み込む
elif code == "[" and value() == 0:
# マッチング ] までスキップ
elif code == "]" and value() != 0:
# マッチング [ に戻る
pc += 1 # プログラムカウンタに+1して返す
```
ご覧の通り、プログラムカウンタ（pc）は現在の命令のインデックスを保持している。ループの最初のステートメントは、実行する命令を取得し、複合ifステートメントは、その命令をどのように実行するかを決定する。
ここでは [ と ] の実装は省略しているが、これらの実装により、プログラムカウンタは一致するブラケットの値に変更されるはず。(その後、pcはインクリメントされるので、条件はループに入るときと、各反復の終わりに1回ずつ評価される。)
テープの値とテープポインタを保持するTapeクラスの実装は以下の通り。
```python=
class Tape(object): #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バイトずつ読み飛ばさなければない。そこで、それらを一度に解析してみる。
同時に、ブラケット間の辞書マッピングを構築して、マッチするブラケットを探すのに1回の辞書検索で済むようにする。方法は以下の通り
```python=
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
```
これは、無効な命令をすべて削除した文字列と、ブラケット・インデックスとそれにマッチするブラケット・インデックスをマッピングした辞書を返す。
あとはグルーコードを追加するだけで、動作するBFインタープリタが完成する。
```python=
def run(input):
program, map = parse(input.read())
mainloop(program, map)
if __name__ == "__main__":
import sys
run(open(sys.argv[1], 'r')) # 'r' は読み込む時にファイルが存在しないとエラーを返す
```
また、mainloop()のシグネチャを変更し、if文のブラケットブランチを実装する必要がある。
## PyPyの翻訳
しかし、これはBFインタプリタを書くためのものではなく、PyPyのためのもの。では、PyPyに超高速な実行ファイルに翻訳してもらうには何が必要なのか。
余談だが、PyPyソースツリーの pypy/translator/goal ディレクトリには、ここで役に立つ簡単な例がいくつかある。これを学ぶ出発点となったのは、PyPyのシンプルなhello worldである「targetnopstandalone.py」(リンクは無い) という例。
この例では、モジュールはエントリーポイントを返す "target "という名前を定義しなければならない。翻訳プロセスは、あなたのモジュールをインポートし、その名前を探し、それを呼び出し、返された関数オブジェクトが翻訳を開始する場所となる。
```python=
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について
PyPyは任意のPythonコードを翻訳することはできない。なぜならPythonはちょっとダイナミックすぎるため、標準ライブラリの関数や構文には制限がある。
上の例では、いくつかの点が変わっているのがわかる。ファイルオブジェクトの代わりに os.open と os.read で低レベルのファイル記述子を使用している。また、". “と”, "の実装も同様に変更されている（上には表示されてない）。このコードに変更を加えるのはそれだけで、あとはPyPyが消化できるほどシンプル。
それほど難しくなく、辞書や拡張可能なリスト、さらにはクラスやオブジェクトを使うことができる。もし、低レベルのファイル記述子が苦手なら、PyPyの "RPython標準ライブラリ "に含まれているrlib.streamioモジュールには、役に立つ抽象化機能がある。
## JITの追加
RPythonをC言語に変換することは素晴らしいことだが、PyPyの最も優れた機能の1つは、インタープリタ用のJITコンパイラを生成できる。
これを実現するために、PyPyに何を伝えればいいのか。まず、バイトコード評価ループの開始位置を知る必要がある。
また、特定の実行フレームを定義するものを知らせる必要がある。自分たちの言語にはスタックフレームがありませんので、特定の命令を実行するために何が一定で、何が一定でないかということになる。これらはそれぞれ「緑」と「赤」の変数と呼ばれている。
今回のメインループでは、pc、program、bracket_map、tapeの4つの変数が使われている。このうち、pc、program、bracket_mapはすべて緑色の変数。これらは、特定の命令の実行を定義する。JITルーチンは、以前と同じ緑色の変数の組み合わせを見た場合、スキップバックしてループを実行しているに違いないと判断した。変数 "tape "は赤の変数で、実行によって操作されている。
PyPyにこの情報を伝えるために、JitDriverクラスをインポートして、インスタンスを作る。
```python=
from pypy.rlib.jit import JitDriver
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'],
reds=['tape'])
```
そして、この行をmainloop関数のwhileループの一番上に追加する。
```python=
jitdriver.jit_merge_point(pc=pc, tape=tape, program=program,
bracket_map=bracket_map)
```
また、JitPolicy を定義する必要がある。派手なことはしないので、ファイルのどこかにこれだけあればいい。
```python=
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
```
JITを有効にすると翻訳にかなりの時間がかかり、マシンでは8分近くかかり、結果のバイナリも大きくなる。翻訳が終わったら、もう一度マンデルブロ・プログラムを実行させてみる。以前は45秒かかっていたのが、12秒に短縮された。
面白いことに、JIT コンパイラが解釈型から機械語型に切り替わるタイミングを mandelbrot の例で見ることができる。最初の数行はかなり速く出力されますが、その後、プログラムはスピードアップしてさらに速くなる。
### jitコンパイラーのトレースについて少し
この時点で、トレース用のJITコンパイラがどのように動作するかを読んでおく価値はある。インタープリタは通常、あなたが書いたインタープリタコードをそのまま実行している。ターゲット言語(BF)のコードのループが頻繁に実行されていることを検出すると、そのループは「hot」とみなされ、トレースの対象としてマークされる。次にそのループに入ると、インタープリタはトレースモードになり、実行されたすべての命令が記録される。
ループが終了すると、トレースは停止する。ループのトレースはオプティマイザに送られ、さらにアセンブラに送られてマシンコードが出力される。そのマシンコードは、その後のループの繰り返しに使用される。
このマシンコードは、多くの場合、最も一般的なケースに最適化されており、コードに関するいくつかの仮定に依存している。そのため、マシンコードにはガードが含まれており、それらの仮定を検証している。ガードチェックに失敗した場合、ランタイムは通常のインタプリタモードにフォールバックする。
より詳しい情報は http://en.wikipedia.org/wiki/Just-in-time_compilation を参照。
### デバッグとトレースログ
これ以上のことができるのか、JITが何をしているかをどうやって見ることができるのか、2つのことをやってみる。
まず、get_printable_location関数を追加する。これはデバッグのトレースログで使用される。
```python=
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)
```
この関数は、緑の変数で渡され、文字列を返す必要がある。ここでは、BFのコードをプリントアウトし、現在実行中の命令をアンダースコアで囲み、どこにあるかわかるようにしている。
これをexample4.pyとしてダウンロードし、example3.pyと同じように翻訳する。
そして、テストプログラム（test.b、ループの中で "A "の文字を15回ほど印刷するだけ）をトレースログ付きで実行してみる。
```
$ PYPYLOG=jit-log-opt:logfile ./example4-c test.b
```
"logfile "というファイルを見てみる。このファイルは非常に読みにくいので、ここで自分なりに説明すると、このファイルには、実行されたすべてのトレースのログが含まれており、基本的には、どのような命令をマシンコードにコンパイルしているかを垣間見ることができる。
各トレースは次のような行で始まる。
[3c091099e7a4a7] {jit-log-opt-loop
のような行で始まり、次のような行で終わる。
[3c091099eae17d jit-log-opt-loop}
次の行では、それがどのループ番号なのか、その中にいくつの OPS があるのかを示している。
```python=
[3c167c92b9118f] {jit-log-opt-loop
# Loop 0 : loop with 26 ops
[p0, p1, i2, i3]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
i14 = call(ConstClass(ll_dict_lookup__dicttablePtr_Signed_Signed), ConstPtr(ptr12), 90, 90, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard3>) [i14, p0]
i16 = int_and(i14, -9223372036854775808)
i17 = int_is_true(i16)
guard_false(i17, descr=<Guard4>) [i14, p0]
i19 = call(ConstClass(ll_get_value__dicttablePtr_Signed), ConstPtr(ptr12), i14, descr=<SignedCallDescr>)
guard_no_exception(, descr=<Guard5>) [i19, p0]
i21 = int_add(i19, 1)
i23 = int_lt(i21, 114)
guard_true(i23, descr=<Guard6>) [i21, p0]
guard_value(i21, 86, descr=<Guard7>) [i21, p0]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c167c92bc6a15] jit-log-opt-loop}
```
debug_merge_point の行がとても長かったので、少し切り詰めた。
このトレースは、2つのオブジェクトポインタ(p0とp1)と2つの整数(i2とi3)の4つのパラメータを受け取る。
4行目で最初の処理である">"を実行しているが、すぐに次の処理を実行している。この「>」には命令がなく、完全に最適化されているように見える。このループは常にテープの同じ部分に作用する必要があり、テープポインタはこのトレースでは一定で、示的な前進操作は不要。
5行目から8行目までが「+」演算の命令になっている。9行目では「<」命令を開始しているが、これもno-op(ノーオペレーション：何もしない命令)。
このルーチンに渡されたi2とi3は、このループで使われる2つのテープポインタがすでに計算されている。また、p1がテープ配列であることも推測される。p0が何であるかは明らかではない。
10行目から13行目では、配列の値を取得し（11行目）、減算し（12行目）、配列の値を設定する（13行目）という「-」の操作を行っている。
次に、14行目で「]」の演算を行う。15行目と16行目では、i9がtrue（0でない）かどうかを確認している。上を見ると、i9は先ほどデクリメントして格納した配列の値で、期待通りにループ条件としてチェックされている（「]」の定義を思い出してみる）。16行目はガードで、条件が満たされない場合、実行はどこか別の場所にジャンプする。ここでは<Guard2>というルーチンにジャンプし、1つのパラメータp0が渡される。
ガードを通過したと仮定すると、17行目から23行目は、プログラムカウンタがどこにジャンプすべきかを見つけるために、bracket_mapへの辞書検索を行っている。この命令が実際に何をしているのかあまり詳しくないが、2つの外部呼び出しと3つのガードがあるように見える。特に、bracket_mapが決して変更されないことがわかっているので、これはかなりコストがかかっているように思える（PyPyはそれを知りません）。これを最適化する方法は後述する。
24行目では、新しく取得した命令ポインタをインクリメントしている。25行目と26行目では、それがプログラムの長さよりも小さいことを確認している。
さらに27行目では、インクリメントされた命令ポインタであるi21がちょうど86になるようにガードしている。これは、先頭にジャンプしようとしている（29行目）ためで、命令ポインタが86であることは、このブロックの前提条件となっている。
最後に、ループは28行目で閉じているので、JITはループボディ<Loop0>にジャンプしてそのケースを処理することができ（29行目）、再びループの始まりとなる。パラメータ（p0、p1、i2、i3）を渡している。
## 最適化
前述したように、ループの繰り返しごとに、最後のジャンプに対応するマッチするブラケットを見つけるために、辞書を検索する。これは非常に非効率的で、ジャンプターゲットはループごとに変わることはない。この情報は不変であり、そのようにコンパイルされるべきである。
問題はルックアップが辞書から来ていて、PyPyがそれを不透明なものとして扱っていること。辞書が更新されていないことも、クエリごとに異なるものを返すこともわからない。
そこで、辞書の問い合わせは純粋な関数であり、出力は入力にのみ依存し、同じ入力からは常に同じ出力が返されることを示す別のヒントを翻訳に与える必要がある。
そのためには、提供されている関数デコレーターpypy.rlib.jit.purefunctionを使い、辞書呼び出しをデコレーションされた関数でラップする。
```python=
@purefunction
def get_matching_bracket(bracket_map, pc):
return bracket_map[pc]
```
このバージョンは example5.py にある。
JITオプションを使って翻訳し、スピードアップを確認してみる。Mandelbrotは6秒しかかからない。(最適化前は12秒だった)
同じ関数のトレースを見てみる。
```python=
[3c29fad7b792b0] {jit-log-opt-loop
# Loop 0 : loop with 15 ops
[p0, p1, i2, i3]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>_+_<-]>.[<+>-]<<-]++++++++++.', 0)
i4 = getarrayitem_gc(p1, i2, descr=<SignedArrayDescr>)
i6 = int_add(i4, 1)
setarrayitem_gc(p1, i2, i6, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+_<_-]>.[<+>-]<<-]++++++++++.', 0)
debug_merge_point('+<[>[>+<_-_]>.[<+>-]<<-]++++++++++.', 0)
i7 = getarrayitem_gc(p1, i3, descr=<SignedArrayDescr>)
i9 = int_sub(i7, 1)
setarrayitem_gc(p1, i3, i9, descr=<SignedArrayDescr>)
debug_merge_point('+<[>[>+<-_]_>.[<+>-]<<-]++++++++++.', 0)
i10 = int_is_true(i9)
guard_true(i10, descr=<Guard2>) [p0]
debug_merge_point('+<[>[_>_+<-]>.[<+>-]<<-]++++++++++.', 0)
jump(p0, p1, i2, i3, descr=<Loop0>)
[3c29fad7ba32ec] jit-log-opt-loop}
```
各ループの繰り返しは、加算、減算、2つの配列のロード、2つの配列のストア、そして終了条件のガードだ。このコードでは、プログラムカウンタの操作は一切必要ない。
このヒントはpypy-devのリストでArmin Rigo氏が提案してくれた。カール・フリードリッヒ氏のインタープリターの最適化に関する一連の投稿も非常に参考になっている。http://bit.ly/bundles/cfbolz/1
最後の言葉
以上、PyPyがPythonの高速な実装であること以外に何があるのかを紹介した。
このプロセスがどのように機能するかをもっと知りたい方には、このプロセスを詳細に説明した学術論文がいくつかあるので、そちらをお勧めする。特に、以下の通り。Tracing the Meta-Level: PyPy's Tracing JIT Compiler.
http://readthedocs.org/docs/pypy/en/latest/extradoc.html を参照。
{"metaMigratedAt":"2023-06-16T11:55:49.631Z","metaMigratedFrom":"Content","title":"pypy StatusBlog","breaks":true,"contributors":"[{\"id\":\"ff44b94e-8b6b-46e5-b4f3-6fac218b3a09\",\"add\":15059,\"del\":1723},{\"id\":\"3659621e-ccb8-4749-9f60-b5b38217fbc3\",\"add\":1,\"del\":324}]"}