Tutorial: Writing an Interpreter with PyPy

This is a copy of a source code of a guest blog post by Andrew Brown, which was originally posted to the pypy-dev mailing list. The original source code of this tutorial was hosted on Bitbucket, but it is no longer available in 2024. This version has been reproduced to serve as educational material for lab interns at the PRG-lab of Institute of Science Tokyo (from September 2024, formerly Tokyo Institute of Technology).

本リポジトリはpypy-devメーリングリストに投稿されたAndrew Brownによるゲストブログ記事のサンプルコードのクローンです。 本リポジトリは東京科学大学プログラミング研究室の4日間のインターンコース教材として作成されました。

Schedule

• Day 1: Tutorial: Writing an Interpreter with PyPy, Part 1を読む
• Day 2: Tutorial Part 2: Adding a JITを読む
• Day 3, Day 4: BFインタプリタのJITコンパイラを最適化する or PyPyの論文を読む

Requirements

• Python 2
• RPython

Installation

rpython(の配置されているpypy)を本リポジトリのサブモジュールとして導入します。

git clone --recursive [email protected]:prg-titech/pypy-tutorial-jp.git

旧情報との差分

pypy 及び rpython の差分管理方法の変更

Part 1 - Translating 内の hg clone https://bitbucket.org/pypy/pypy は古い情報です。 rpython は 2024年10月時点で GiHub で管理されている pypy リポジトリ内の pypy/rpython/bin/rpython に配置されています。

rpythonを手動で導入する場合は、当該箇所を以下に読み換えてください。ただし、上記の導入方法(Installation)を取った場合は既に pypy が既にローカルに配置済みのため、不要です。

git clone https://github.com/pypy/pypy

rpython で BF インタプリタを変換

Part 1最終節およびPart 2の rpython translatorの実行は、スクリプトの配置先の変更に伴い、/pypy/pypy/translator/goal/translate.py を ./pypy/rpython/bin/rpython に読み替えてください。(your interpreter).pyを変換するには以下を実行してください。--opt=jit オプションをつけると、変換先のインタプリタ (your interpreter)-c にJITコンパイラが生成され、実行中に使用されます。

python ./pypy/rpython/bin/rpython (--opt=jit)* (your interpreter).py

他注意点

• （注）"Download and Install" からダウンロードできるprebuildバイナリにはrpythonは含まれていないことに注意してください。
• （注）RPythonは Python 2 で書かれていることに注意してください。
  • Python 3で実行すると構文解析エラーが出力されます。
  • pyenvを使うと両バージョンを容易に切り替えられます。

  pyenv local x.y.z

トレースを見る方法

JITコンパイラがどんなコードを出しているかを調べる方法です。以下のコマンドを実行するとAが100個出るはずです。

PYPYLOG=jit-log-opt:logfile ./example5-c test100.b

logfileにコンパイルされたトレースが記録されています。この場合は、内側の2つのループに対応するものが Loop1, Loop2 として記録されているはずです(どっちがどっちかは場合によります)。その命令を見て、無駄な命令がないかを考えます。 命令を見ても何をやっているかを想像するのは難しいのですが、

• int_add とか int_sub とかは明らかだろうと思います。
• setarrayitem_gc, getarrayitem_gc とかは配列の読み書き
• setfield_gc, getfield_gc はオブジェクトのフィールドの読み書き (フィールド名が引数に出現しているはず) です。

インタプリタの中で green とした pc, program, bracket_map に関する命令がもし残っていたら、質のよくないコードが出ている可能性があります。

最適化のヒント

最適化のポイント

• Tapeオブジェクトへのアクセスに伴うread/write回数を減らしたい
• 静的に計算できるものは静的に計算してしまいたい

ループオーバーヘッドの除去

• オーバーヘッドの予測：ループがあると、pcの指す値が0になるまで、何度もguard（readとcompareとassertion）が発生して遅い
• 最適化のアイディア：1ループでpcが移動しない幾つかのループに関しては、対応する命令で拡張したBF拡張言語を設計し、インタプリタ内で拡張命令の効率的な処理を実装することでループを除去可能

頻出パターン：set 0

ループの解釈：今のpcの位置の値を0にし、pcの位置はそのまま

[-]

頻出パターン：add n (Run-length encoding)

ループの解釈：今のpcの位置の値を3つ右のポインタの値に加算し(元の位置はset 0)、元のpcの位置に戻る

[->>>+<<<<]

[>>>+<<<-]

ループの解釈：今のpcの位置の値を2つ左のポインタの値に加算し(元の位置はset 0)、元のpcの位置に戻る

[-<<+>>]

[<<+>>-]

頻出パターン：add nパターンの一般化 (Run-length encoding)

ループの解釈：今のpcの位置の値を1つ右,2つ右,3つ右のポインタの値にそれぞれ加算し(元の位置はset 0)、元のpcの位置に戻る

[->+>+>+<<<]

[>+>+>+<<<-]

ループ開始位置におけるテープ位置の事前計算

要追記, 未検証

結果・評価

• Part 1を最後まで完了すると、以下のような出力を得ます:

./example2-c mandel.b

• PyPyツールチェーンで変換されたインタプリタの速度を比較するには evaluate.py を実行します。 evaluate.py の内部では、 example2-c, example3-c, example4-c, example5-cのそれぞれを5回ずつ実行した実行時間を記録し、平均値と分散を元に結果のグラフを出力しています。

python3 -m venv evalenv
source evalenv/bin/activate
python3 -m pip install numpy matplotlib
python3 evaluate.py
deactivate

実行例：