TECH-MICCHON.jar

Scalaを中心に技術的な話題を書きます。

Tracing the Meta-levelとは?PyPyのJITコンパイラについて

本記事はFOLIO Advend Calendar 22日目のものです. 昨日は yoshiko_pg さんで「git grepでソースコード内検索のあれこれ」でした.

はじめに

みなさんは PyPy についてご存知ですか? PyPy とは非常に高速な Python 処理系で,通常の CPython に比べると約8倍の高速化を達成しています1.

何故早くなったのか,それは,Meta-Tracing JIT コンパイラを搭載した特殊な言語によって実装され,PyPy には JIT コンパイラが付属しているからなのです.

以降では JIT の話は省略しますが,一言でいうと「よく実行される部分を機械語コンパイルして実行する」というもので,プログラムの大幅な速度向上が期待できます.

今回は,その特殊な言語 RPython と Meta-Tracing JIT という技術について触れていこうと思います.

RPython について

RPython とは Python のサブセットです.元は PyPy を実装するために作られた言語でしたが,最近では独立して配布されるようになりました2. 処理系として面白いのは,keen さんのブログ3にもありましたが,Python コードをC言語Java バイトコードなどに変換するコンパイラでもあるのです.

さらに,この RPython は Meta-Tracing JIT コンパイラという技術によって任意の JIT コンパイラ付きの処理系を実装することが可能になりました.

Tracing JIT コンパイラ

Meta-Tracing JIT の説明する前に RPython の Tracing JIT について軽く触れておきます.

下のプログラムは,0から9999までの和を計算する単純な Python プログラムです. 左にあるのは meta-program-conter というもので,命令の並んでいる順番とだけ覚えておいてください.

0   sum = 0
1   i = 0
2   while i < 10000  # conter += 1 implicitly
3      sum += i
4      i += 1

この meta-pc が「再び同じ値になる」という状態に何度も繰り返しなったとします.そして,ある閾値を超えると RPython はその部分をループだとみなすのです.

具体例を出すと分かりやすいでしょう.まず,このプログラムを上から順番に実行するとして,meta-pc がどんな値になるか手で書き下してみると,

0, 1, 2, 3, 4, 2, 3, 4, 2, 3, 4 ...

となりますね.2, 3, 4 の塊が何度も現れているのが分かると思います.

2 のところに来たら counter が 1 だけ RPython のレベルでインクリメントされます.

そして,ある閾値を超えるとRPython はここをループだとみなし,その部分を「トレース」として JIT コンパイルします.

以上が Tracing JIT の大雑把な説明になります.

Meta-Tracing JIT コンパイラ

Meta-Tracing JIT コンパイラの話に移りましょう.ところで, Meta-Tracing JIT は PyPy の中ではどういった立ち位置にあるのでしょうか.

まず,以下の関係にあることを念頭に置きましょう.

実装する言語 実装される言語
RPython Python

RPython で Python を実装するということは,すなわち RPython 言語で Python インタプリタを実装するということです.

したがって, RPython JIT コンパイラは RPython で書いた Python インタプリタをトレースしなければなりません.

インタプリタをトレースする

インタプリタをトレースするというのは一体どういうことでしょうか.まず RPython の Meta-Tracing JIT の中核部分を見てみます. 下のコードは,とあるインタプリタの大枠だと思ってください.

def interp(regs): 
    pc = 0
    instr = bytecodes[pc] 
    while True: 
        jit_merge_point(pc=pc, ...) 
        if instr == ADD:
           ... 
        elif instr == IS_GT: 
           ... 
        elif instr == JUMP: 
           ... 
           can_enter_jit(pc=pc, ...)
          ...

しかし,このコードをただ Tracing JIT しただけでは,プログラムのループを正しく判定できません.何故なら「インタプリタのループとプログラムのループというものは同じループだけど意味が違う」からなのです.

インタプリタループとプログラムループ

インタプリタループとは,各オペコードに対して適切な処理へと ディスパッチし続けている while ループ のことを指します.

一方で,プログラムループとは, ユーザーが書いたプログラムにあるループ のことです.

Meta-tracing JIT が本当に JIT したいのは プログラムループ であることは間違いないでしょう.

この2つは意味は違うといっても「ループする」という性質は同じなので,そこを上手く区別してやらなければなりません.

RPython では

  • jit_merge_point
  • can_enter_jit

の2つの API が2つのループを区別する上で重要な役割を担います.

jit_merge_pointJIT コンパイラに現在の pc の状態を教えるためのメソッドです.ディスパッチループの先頭に置き,{meta-pc, pc}をセットで再び同じ状態になるかどうかを監視します.

can_enter_jitJUMP 命令などの pc が若い値になる命令を解釈する部分に置きます.それによって,JIT コンパイラに Tracing を開始させます.

以上のことをすると,Meta-Tracing JIT コンパイラは実行するプログラムのループを検知し,そこを Tracing JIT します.これが Meta-Tracing JIT の仕組みです.

PyPy の構造

Python VM は RPython によって実装され,その RPython には tracing-JIT コンパイラが付属しています.

ただ, PyPy を利用する側からは RPython という言語の存在は分かりません.

それはあたかも,RPython の JIT コンパイラPython VM のメタレベルを tracing-JIT したかのようです.これが Meta-Tracing JIT の真髄なのです.

image.png

余談

RPython で実装された処理系として, 有名なものだと

でしょうか.古い記事ですが http://rokujyouhitoma.hatenablog.com/entry/2015/06/12/115239 によくまとまっています.

Meta-Tracing JIT の話は Tracing the Meta-Level: PyPy’s Tracing JIT Compiler にあるので,興味のある方は一読してみるといいでしょう.

ちなみに,自分の卒業研究では OCamlMinCaml の Meta-Tracing JIT コンパイラを作っています.ココロが何度折れたか分からないほどしんどいですが,なんとか動くところまで実装して卒業したいです!