Contents
pypy-dev mailing list の助力によって Andrew Brown によって書かれました。
このチュートリアルのマスタコピーと追加のファイルはここにあります。 https://bitbucket.org/brownan/pypy-tutorial/
私が最初に PyPy プロジェクトについて知ったとき、それがなんであるか正確に理解するのに時間がかかりました。 それがなんであるかまだ知らない人のために説明すると、それは2つのことで:
ほとんどの人は2つ目のパートが PyPy であると思っていますが、このチュートリアルはその Python インタプリタについてのもの ではありません 。 あなた自身の言語のインタプリタを書くためのものです。
このプロジェクトは、私が PyPy がどのように働き、それがなんであるかをよりよく理解するための助けとするためのものです。
このチュートリアルは PyPy がどのように働き、そしてそれが何であるかについて少しばかり知っているという前提で書かれています。
ここは PyPy で何ができるかの簡単な概要を説明します。例えば、あなたがインタプリタ型言語を作りたいと思っているとします。 これにはソースコードパーサ、バイトコードインタプリタループそして標準ライブラリのコードを書くことが伴います。
これは適度に複雑な言語を実装するためにはかなりの作業で、さらに多くの低レベルな作業があります。 パーサとコンパイラのコードを書くことは通常あまり楽しくはありません。それがあなたのためのパーサとコンパイラを生成するツールが存在する理由です。
その場合でも、あなたはまだインタプリタのメモリ管理について心配する必要があります。 そしてあなたは任意精度の整数や素敵な一般的なハッシュテーブルなどの多くを再実装することになるでしょう。 その労力は彼らに言語のアイデアを実装することを先送りにさせるためには十分です。
もしもあなたが既存の高級言語に似た言語で、例えば Python であなたの言語を記述できたとすれば素敵だと思いませんか? あなたが自動メモリ管理やリッチなデータ型などの高級言語の全ての利点を利用したいと思うならば、それはたしかに理想的になるでしょう。 ああ、しかしインタプリタが他の言語を他の言語で解釈することで遅くなると思っていませんか? 実行のために二倍の解釈をしなければいけませんから。
あなたが予想しているとおり、 PyPy はこの問題を解決します。 PyPy はあなたのインタプリタのコードを C(もしくは JVM や CLI)に解析・変換するための洗練されたツールチェインです。 このプロセスは"変換"と呼ばれ、 Python の構文と多くの標準ライブラリの構文を変換する方法を知っていますが、全てではありません。 あなたがしなければならないことは、Python のサブセットである RPython で解析と変換ができるように慎重に定義し、インタプリタを書くことが全てです。そして、 PyPy はあなたのために非常に効率的なインタプリタを生成します。
なので、効率的なインタプリタを書くことは難しくありません。
私が実装することを選択した言語は死ぬほど簡単です。 言語のランタイムは、ゼロで初期化された整数値の書き込めるテープとテープのセルを指すポインタで構成されています。 言語は以下のような8つのコマンドを持ちます。
認識されないバイトば無視されます。
何人かはこの言語に見覚えがあるでしょう。私はこれを BF と呼ぶことにします。
ひとつ、言語は独自のバイトコードを持つことに気づくでしょう。そしてソースコードからバイトコードへの変換はありません。 これが意味することは、言語は直接解釈できるということです。インタプリタのメインの評価ループは、ソースコード上で動作します。 これはかなり実装を簡潔にしています。
昔ながらの Python で BF を書くことから始めてみましょう。 最初の一歩は評価ループの大枠を書くことです。
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)は現在の命令のインデックスを保持します。 ループの一文目は実行する命令を取得していて、その後の文が命令をどうやって実行するか決定できた場合、合成します。
[ および ] の実装はここでは置いておきます。しかし、それらはプログラムカウンタを対応する括弧の値に変更する必要があります。 (ループに入るときの条件が一度だけ評価されるように pc はインクリメントされ、そして各反復の終了時に一度行われます。)
ここで Tape クラスの実装です。 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
これは、すべての不正な命令を取り除いた文字列と、対応する括弧と括弧のインデックスをマッピングをするための辞書を返します。
必要なのはいくつかのグルーコードであり、動作する BF のインタプリタを持っています:
def run(input):
program, map = parse(input.read())
mainloop(program, map)
if __name__ == "__main__":
import sys
run(open(sys.argv[1], 'r'))
あなたが自宅で一緒にフォローしている場合、 mainloop 関数の識別子の変更と、括弧での if 文での分岐を実装する必要があります。
ここに完全な例があります: example1.py
ここでは Python インタプリタを実行することで動作することをあなたが見るために試すことができます。 しかし警告気をつけてください、それはもっと複雑な例では 非常に 遅くなります:
$ python example1.py 99bottles.b
私のリポジトリには mandel.b といくつかのサンプルプログラムがあります。
これは BF のインタプリタを書くことについてではなく、これは PyPy について書いている。 PyPy を超高速な実行ファイルに変換するためにはどうすればよいのでしょう?
サイドノートとして、PyPy ソースツリーの pypy/translator/goal ディレクトリに存在する有用ないくつかの簡単な例を示します。 学習のための例として、PyPy での単純な Hello, World の例である「targetnopstandalone.py」を出発点としました。
この例では、モジュールはエントリポイントを返す「target」と呼ばれるオブジェクトを定義する必要があります。 変換プロセスはこのモジュールをインポートし、「target」オブジェクトを探索し、呼び出し、そして返ってきた関数オブジェクトから変換を開始します。
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 は少々ダイナミックであるためです。 そこで、プログラムが使用できる標準ライブラリ関数と構文構造を制限しています。 私は全ての制限について把握しているわけではありません。詳しい情報は下記 URL を参照してください。 http://readthedocs.org/docs/pypy/en/latest/coding-guide.html#restricted-python
上記の例では、いくつかの変更が見て取れます。 ここでは os.open と os.read を用いて低レベルファイル記述子をファイルオブジェクトの代わりに使用しています。 (上記例では示されませんが)「.」と「,」の実装も同様に調整されています。
これらはそれほど難しくはありませんよね? 私は辞書も拡張可能なリストもさらにクラスとオブジェクトも利用できるのです! 低レベルファイル記述子あなたにとってが低すぎる場合は、 PyPy の「RPython 標準ライブラリ」にある rlib.streamio モジュールに便利な抽象構造が存在します。
ここまでの例は example2.py にあります。
あなたがまだ最新版の PyPy を bitbucket.org のリポジトリからチェックアウトしていないならば:
$ hg clone https://bitbucket.org/pypy/pypy
(私の例を実行するために最新版でのバグフィックスが必要です)
スクリプトの実行には 「pypy/translator/goal/translate.py」を使用します。 このスクリプトにサンプルモジュールを引数として渡して実行してください。
$ python ./pypy/pypy/translator/goal/translate.py example2.py
(必須ではありませんが、 PyPy の Python インタプリタを使用することで高速化できます)
PyPy の実行にはしばし時間がかかり、実行中は素敵な見た目のフラクタルをコンソールに描きます。 私のマシンではおおよそ 20 秒程度掛かっています。
この結果は BF プログラムの実行可能なバイナリのインタプリタです。 私のリポジトリにはいくつかのサンプル BF プログラムが含まれています。 そこに含まれるマンデルブロフラクタル生成器は、私の計算機で実行すると大体 45 秒ほどかかります。 試してみてください。
$ ./example2-c mandel.b
Python 上で動く未変換のインタプリタと比較してみます:
$ python example2.py mandel.b
永遠に実行していませんか?
これでおわかりでしょう。 RPython でインタプリタを書き、 PyPy ツールチェインで変換することに成功したのです。
RPython から C に変換することはとてもクールです。しかし、 PyPy の最高の機能のひとつは、 あなたのインタプリタのために Just-in-time コンパイラを生成 できることです。 そうです、あなたのインタプリタがどのように構成されているのか、といういくつかのヒントのみで PyPy はラインタイムにインタプリタの対象の BF 言語からマシン語に変換する JIT コンパイラを生成し、含めることが可能なのです!
では、これを実現するために PyPy にヒントを与えるためには何をする必要があるのでしょう? まず、あなたのバイトコード評価ループがどこから開始するのかを知る必要があります。 これにより対象となる言語(BF)で実行される命令を追跡できます。
何が特定の実行フレームを定義しているかを知らせることも必要です。 実際にはスタックフレームを持っていない私たちの言語から、結局のところどの定数が実行する特定の命令で、どれがそうではないのかをです。
以下の文章のために example2.py に戻って参照してください。
メインループでは 4 個の変数が使われています: pc, program, bracket_map, tape. これらのうち、 pc, program, bracket_map は全てグリーン変数です。 それらは特定の命令を 定義 しています。 JIT のルーチンが以前と同じグリーン変数の組み合わせを発見すると、手前に戻ってループを実行する必要があると知っています。 「tape」変数はレッド変数で、実行によって内容が変更されます。
さあ、 PyPy にこの情報を伝えてみましょう。 JitDriver クラスをインポートしてインスタンスを作ることから開始します:
from pypy.rlib.jit import JitDriver
jitdriver = JitDriver(greens=['pc', 'program', 'bracket_map'],
reds=['tape'])
そしてこの行 mainloop 関数のを while ループの一番上に追加します:
jitdriver.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
JIT を有効にすると変換に大幅に長くかかるでしょう。私のマシンでは大体 8 分かかります。 そして出来上がるバイナリファイルはとても大きくなります。 それが終わったらマンデルブロプログラムを再度実行してみてください。 以前の 45 秒と 12 秒とを比べると違う世界です!
興味深いことに、マンデルブロの例で JIT コンパイラがインタプリタからマシンコードに切り替えるところを見られるのです。 最初の数行はかなりはやく出力され、その後のプログラムは速度が加速され、より速くなります。
JIT コンパイラの動きをトレースする方法を今の時点で読むことに価値があります。 ここで簡単な説明をします: 通常インタプリタはあなたが書いたインタプリタのコードを実行しています。 対象言語(BF)のループを検出したとき、多くの場合は実行され、ループが「ホット」だと考えられるとトレースするようにマークされます。 次回ループに入ると、インタプリタはトレースモードに移行し、全ての実行された命令は記録されます。
ループが終了したときにトレースは停止します。ループをトレースした結果はオプティマイザに送られ、出力するマシンコードになります。 マシンコードは後続のループのイテレーションに使用されます。
マシンコードは多く場合、最も一般的なケースで最適化され、コードはいくつかの仮定に紐付けられます。 したがって、マシンコードにはそれらの仮定を検証するためのガードが含まれます。 ガードのチェックに失敗した場合、ランタイムは通常のインタプリタモードにフォールバックします。
詳細を参照するのに以下の場所から開始するとよいでしょう http://en.wikipedia.org/wiki/Just-in-time_compilation
より良くすることはできますか? どうすれば 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)
この関数はグリーン変数を受け取り、文字列を返します。 ここでは、 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}
次の行はループ番号がどれであるかを示し、オペレーションがいくつその中にあるかを表示しています。 このケースでは、最初のトレースはこのようになっています:
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 と表示されている行を少し取り除きました。
では、これが何をしているかを見てみましょう。 このトレースは四つのパラメータを受け取ります: 二つのオブジェクトのポインタ (p0 と p1) と二つの整数 (i2 と i3) です。 デバッグ行を見ると、これはこのループのとある反復をトレースしているようです: "[>+<-]"
四行目の最初のオペレーション ">" の実行を開始していますが、直後に次のオペレーションを実行開始しています。 ">" は何も実行せず、完全に最適化されているように見えます。 このループは常にテープの同じ部分に作用する必要があり、テープポインタはこのトレースでは変化しません。 明示的な事前の操作は不要です。
五行目から八行目は "+" オペレーションの命令です。 まず、ポインタ p1 にある配列の i2 番目の要素を取得します。 その値に 1 を加算して i6 にストアし (七行目)、それを配列に戻します(八行目)。
九行目は "<" 命令を開始しますが、これもなにもしません。 このルーチンに渡された i2 と i3 は、事前に計算されたこのループで使われる二つのテープポインタであるようです。 おそらく p1 はテープの配列でしょう。 p0 が何であるかははっきりしていません。
10行目から13行目は "-" オペレーションの実行です: 配列の値を取得(11行目), 減算(12行目)そして配列への値の設定です(13行目)。
次の14行目では、 "]" オペレーションに到達します。 15行目と16行目では i9 が true (非ゼロ) かどうかをチェックしています。 上の行を見てみると、i9 はデクリメントしてストアされた配列の値で、期待通りループの継続条件としてチェックされています ("]" の定義を思い出してください)。
ガードをパスしたと仮定すると、17行目から23行目は bracket_map の辞書検索を行い、プログラムカウンタのジャンプ先を探しています。 私はどの命令が実際に実行されるかを読み解くのにあまり慣れていませんが、二つの外部呼び出しと3つのガードがあるように見えます。 これらは特に、bracket_map が変更されないと分かっている場合はとても重い処理に見えます (PyPy はそれを知りません)。 これを最適化する方法を以下に示します。
24行目は次に獲得する命令のポインタをインクリメントしています。 25行目と26行目はプログラムの長さよりも短いかどうかを確認しています。
さらに 27行目は命令ポインタをインクリメントした値である i21 が実際に 86 であるかのガードを実行しています。 これは、最初にジャンプする(29行目)ための前提条件が、命令ポインタの値が 86 であることである為です。
最後に、ループが閉じる 28行目で再度ループを開始するようなケースを処理するために JIT はループ本体 <Loop0> にジャンプできます(29行目)。
述べたように、ループの反復ごとに最後のジャンプで対応する括弧を見つけるために辞書検索を行っています。 ジャンプのターゲットは次のひとつのループの中で変更されることはないため、これはとても非効率的です。 情報は定数であり、そのようにコンパイルする必要があります。
問題となっているのは辞書からのルックアップで、 PyPy はそれそのままを扱っています。 辞書が変更されないことかクエリごとに別の値を返さないことを知らないためです。
私たちがしなければならないのは、変換のために辞書へのクエリが純粋関数であるということを、別のヒントとして提供することです。 それは、出力が入力の値に のみ 依存し、同じ入力からは同じ出力が得られるということです。
pypy.rlib.jit.purefunction で提供されているデコレータ関数を使用し、辞書呼び出しの関数をラップしてください:
@purefunction
def get_matching_bracket(bracket_map, pc):
return bracket_map[pc]
このバージョンは example5.py です。
JIT オプションとともに再度変換し、高速化されていることを確認してください。 マンデルブロの実行は今では 6秒しかかかりません! (最適化前は 12 秒でした)
さあ、同じ関数のトレースを見てみましょう:
[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}
とても良いです! ループの反復ごとに減算、二つの配列の読み込み、二つの配列のストア、そして終了条件のガードが追加されています。 これです! このコードは どんな プログラムカウンタの操作も必要ありません。
私は最適化のエキスパートではありません。このヒントは pypy-dev mailing list で Armin Rigo に提案されたものです。 Carl Friedrich はあなたのインタプリタを最適化する際に役立つ一連の記事を書いています: 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