編集可能

PyPyの論文つぶやき

動的言語、JITの研究している知人がPyPyの論文読みながらつぶやいてたので、まとめとく。
15
Ryotaro Ikeda @chlere

らぼでPyPyの新しい論文読んでる

2011-08-15 11:23:22
Ryotaro Ikeda @chlere

今回はlanguage-specificな特徴量をいかにしてMeta-Tracingで扱うかについて述べられています (via : http://t.co/miqpeba ) #pypy

2011-08-15 11:26:20
Ryotaro Ikeda @chlere

Pythonで簡単にVMを作りたい!->RPythonで作れるPyPyというFWを作りました!->JITは言語の実装に寄らないようにRPythonそのものを対象にしちゃうよ!->あれ、データモデルの部分にもJITが入り込むからすげー早くなっちゃった (いまここ) #pypy

2011-08-15 15:59:05
Ryotaro Ikeda @chlere

Meta-TracingがTypical-Tracingを凌駕する日は来るのだろうか?Trace monkeyと張って勝てれば確実に凌駕したと言えそうだが。 #pypy

2011-08-15 16:01:02
Ryotaro Ikeda @chlere

論文をみる限りだと、Meta-Tracingは"Typicalでは難しいから実装を保留してしまっている部分"にも入り込める事をアドバンテージとして謳っているが、仮にTypicalで全て実装した場合とタイマン張ったらどうなるんだろう。ほぼ互角ならMetaの時代だな #pypy

2011-08-15 16:05:49
Ryotaro Ikeda @chlere

そう考えると、日本では(?)PyPyはもっぱら高速化ソリューションとして見なされがちだが、本来はTracing-JITとGCを実装した本格的なVMを「手軽に作る」為のものなんだよなー。Meta-Tracingが出てきちゃったからごっちゃになってる。 #pypy

2011-08-15 16:09:37
Ryotaro Ikeda @chlere

filter/map/reduceはそもそもRPython上で定義されていないことが分かった。だから、PyPy上で呼ぶと(多分C callなので)遅いんじゃないかなぁ。 #pypy

2011-08-18 16:16:06
Ryotaro Ikeda @chlere

"PyPyは元々処理系作成用のフレームワークなのにそういう使い方をする為のチュートリアルがねーぞー"とか思ってたら、普通にあった。3ヶ月前とか最近すぎる。 http://j.mp/ojv1lb

2011-08-18 16:19:00
Ryotaro Ikeda @chlere

そもそもMeta-Tracingの"Meta"とは何か。ここではつまるところ「本来であれば複数の対象があればその都度同じ仕事を各対象に対して行わなければならないが、それを1つの仕事に集約できる」というC++のテンプレート「メタ」と同様の意味を持っている。 #pypy

2011-08-18 17:06:37
Ryotaro Ikeda @chlere

PyPyではRPythonで処理系(インタプリタ)を書いてもらい、そのRPythonに対してJITを適応することで、本来であればインタプリタごとに書かなければ実装できない”JITコンパイラの実装”という仕事をメタ化している。 #pypy

2011-08-18 17:08:38
Ryotaro Ikeda @chlere

けれど結局、メタ化したせいで実装するインタプリタ言語依存の特徴を利用できないという欠点があるように思われるが、実は、メタ化によって本来JITを組む際に難しくてトレースから除外されるようなデータ操作もトレースできるようになってしまうという驚くべきアドバンテージが生まれた。#pypy

2011-08-18 17:11:45
Ryotaro Ikeda @chlere

JITのトレースはRPythonレベルで行われるので、JITコンパイルによりそれがマシンコードになる直前までに行われる最適化処理も、やはりRPythonレベルで行われたトレースを基にして行われる。 #pypy

2011-08-18 17:21:00
Ryotaro Ikeda @chlere

RPython上でトレースする(メタトレーシング)する仕組みだから、RPythonで実装さえすればどんなインタプリタ言語であれGC, JITコンパイラが自動装備されたきちっとした処理系が手軽に作れる #pypy

2011-08-18 17:23:35
Ryotaro Ikeda @chlere

多くの場合、JITコンパイラは頻繁に実行される部分(ループなど)を見つけてそこをコンパイルする。ユーザープログラムのループを処理している時には処理系のプログラム自体も似たような経路のメインループを何度も処理しているハズなので、RPythonレベルでこれを行える。 #pypy

2011-08-19 14:18:14
Ryotaro Ikeda @chlere

あるユーザープログラムのトレースの閉路を考える時、その閉路を実行する為のRPythonの命令列はそのユーザープログラムのトレースと意味が等価な「変形」とみなすことができる #pypy

2011-08-19 14:22:50
Ryotaro Ikeda @chlere

PyPyでの最適化は、RPythonのトレースが終わった後、バックエンドにそれらが送られる前に(RPythonのままの形式で)行われる。 #pypy

2011-08-19 14:32:29
Ryotaro Ikeda @chlere

トレースはリニアな形式であるため、主にここでの最適化はトレースの簡略化に重点が置かれる。すなわち、定数値置き換え、共通式除去、冗長メモリ割り当ての除去などを適応する。 #pypy

2011-08-19 14:34:21
Ryotaro Ikeda @chlere

結局の所、「RPythonで書けば速くなる」も「RPythonから別言語へのSource-to-Sourceコンパイラ」も事実上は正しい認識なんだよな #pypy

2011-08-22 10:02:08
Ryotaro Ikeda @chlere

PyPyでは、RPythonで実装したインタプリタ内から2種類の「ヒント」を貰う事で、定数値置き換えの最適化を行う。それが適切に作用する事がPyPyにおけるクリティカルな速度向上の要となる。何故なら、この定数置き換えがさまざまな最適化を行う事を可能にするからだ #pypy

2011-08-22 14:28:44
Ryotaro Ikeda @chlere

インタプリタ実行とJITによって生産されたネイティブコード実行を切り替える為の条件分岐である「Guard」は、型推論と定数置き換えに使える。例えばあるトレースのGuardが「x==1」であれば、そのGuard以降のxはint型の1に置き換えることが可能となる。 #pypy

2011-08-22 15:02:49
Ryotaro Ikeda @chlere

このGuardを用いた型推論/定数置き換えの方法を「プロモーション」と云う。 やべぇちょっとかっけぇ #pypy

2011-08-22 15:03:25
Ryotaro Ikeda @chlere

この「プロモーション」を効率的に行うために、RPython上で「promote」という組み込み関数を用いてPyPyに対してヒントを提供することができる。例えば、ループ毎に殆ど値の変わらない変数xに対して、promote(x)などとしてヒントの記述を行う。 #pypy

2011-08-22 15:11:43
Ryotaro Ikeda @chlere

このpromote()はインタプリタ上では何の動作もしないダミー関数のようにふるまう。だけど、実際にJITコンパイラによってTraceが行われる時にプロモーションの対象となる。(このプロモーションは、どうやらPyPy側では自動では行われないようだ) #pypy

2011-08-22 15:15:24
Ryotaro Ikeda @chlere

promote()は不適切な部分に挿入してもエラーにはならない。トレースの分岐が増えて、結局は実行しているうちにその部分もコンパイルされて実行されるようになる。しかし、それはマシンコードの無駄な増加を意味するので好ましくはない(遅くなる) #pypy

2011-08-22 16:24:53
残りを読む(114)