Contents
この文章は,PyPyのJust-In-Timeコンパイラの生産についての 技術的でない紹介と,その動機について説明するものです.
Pythonのような複雑な動的言語の為のインタプリタを 書くのは簡単な事ではありません. 特にパフォーマンスの事を考慮し,Just-in-Time(JIT)コンパイラ の導入までを考えば尚更です.
幸いな事は,それは我々がやった事ではないということです. 我々は確かに,Pythonのインタプリタを実装しましたが, (そのPython用の)JITコンパイラの為の実装はPyPyでは一切書いていません. その代わり,我々はそのPythonのインタプリタをRPythonで実装しています. これはとても素敵で,高水準な言語です – そしてこの言語で 記述されたPythonインタプリタは,PyPyが*自動的*に JITコンパイラを付与した形に変換してくれるのです.
当然ながら,この変換はユーザー(Pythonを書いているプログラマ)に透過的です. 我々のゴールは,*全ての*Pythonの特徴をサポートすることです – それは例えば, ランダムフレームアクセスやデバッガなどです.そしてこれらもまた,言語を実装する 為のソースコード(例えば,Pythonのインタプリタのソースコード) に対してもほぼ透過的 になるようにします.これには少しばかりのガイドが必要となるだけです:我々はそれ( 言語を実装する為のソースコード)に少しのヒントを加える必要があります.そのヒント を基に,その*JITコンパイラジェネレータ*はオリジナルのインタプリタと同様の言語セ マンティクスを持ったJITコンパイラをインタプリタの生産時に生成します.このJITコ ンパイラ自身はマシンコードをインタプリタの実行中に生産し,積極的な最適化をその ユーザーのプログラムに対して適応し,セマンティクスの変更なしに大きなパフォーマン スの向上へと導きます.もちろん,ここでの面白い事は,この我々のPythonインタプリ タ実装は,JITコンパイラ一緒に,時間とともに進化していく事です.
従来までの我々のJITコンパイラジェネレータは,”部分評価”手法をベースとしていまし た.これは有名かつ良く研究されている分野で,最も確実な手法だと考えられました. 本手法を用いて,インタプリタ言語からコンパイラ言語への自動変換が幾つか試みられ ましたが,それが実際に実行速度の向上に結びつく事はありませんでした.我々は,こ の試みが失敗した根本的な原因は,本手法をJITコンパイラの生産ではなく, 通常のコンパイラに適応したことだと考察しています.もしこの考察が正しければ,動 的言語の実際の実行スピードは大幅に向上できるはずです.
従来のJITコンパイラジェネレータの全ては,手書きのPsycoのようなコードを生産する ようなものばかりでした.しかし2009年から,我々のプロトタイプでは最早部分評価手 法は使っていません – 少なくとも,2009年現在は論文の査読に出す段階ではありませ ん.その代わりに,我々はJavaやJavaScriptで最近研究されている*Tracing JIT*手法を ベースにしています.しかしながら,今現在存在している全てのTracing JITコンパイラ と比較したときに,我々のJITジェネレータには,我々が以前JITジェネレータを部分評価 手法を用いて作成した時に得たテクニック(アロケーション命令の削減による構造最適化 など)を適応できることによるアドバンテージがあります.
我々の現在のJITに最も近い競合プロジェクトはTamarin’s TraceMonkeyです.このJITコ ンパイラは手動で書かれており(JITジェネレータなどを使うことなく),これを利用した 多くの試みがなされています.PyPyでは,我々はJITジェネレータをRPythonレベルで書 きます.これが意味することは,我々はPythonという言語を詳細に網羅したJITを書く必 要が無い（むしろ書けない）という ことです.これらの言語の詳細なところは,我々が 既に完全なPythonインタプリタを (RPythonで)書き終わっているという事実から,実質 ,自動的に与えられるものです.
我々の生産したJITコンパイラは,これまで広範な使用がされておらず、また、特別目新 しいとも言えないような手法をいくつか利用しています。我々がここで成し遂げたいの は、理論的な制約を押し込めて与えられた動的言語をいかに早くするかではありません。 我々の目的: 我々はそれを、全ての動的言語(例えばオープンソースの、産業や学術的 なサポートのない動的言語や内輪限定の言語なども含む)の為の、リーズナブルな Just-In-Timeコンパイラの**実際の例**であると位置づけています。我々は、この例は 次の条件を満たしているべきと考えます。
- 簡単 : (他のソリューションと比べて)一番少ない労力でインタプリタが書けること
- メンテナンス可能 : 我々のJITコンパイラはプロジェクトを分断しません(我々は
JITコンパイラの為にソースコードを分割したりはせず、ただ、VMの為のCソースコー ドを生産し、それをコンパイルするだけです). 言い換えれば、PyPyで生産された全て のJITコンパイラは、インタプリタが書き直される度にそれと同調する為に、いくら速 度の出ていたものであったとしても作り直されることになります。 * 十分早い: 当然JITコンパイラだけではありません。我々は、JITコンパイラの外で 適応する手法によってより良いパフォーマンスを引き出しています。
|
There are a large number of approaches to improving the execution speed of dynamic programming languages, most of which only produce small improvements and none offer the flexibility and customisability provided by our approach. Over the last 6 years of tweaking, the speed of CPython has only improved by a factor of 1.3 or 1.4 (depending on benchmarks). Many tweaks are applicable to PyPy as well. Indeed, some of the CPython tweaks originated as tweaks for PyPy.
IronPython initially achieved a speed of about 1.8 times that of CPython by leaving out some details of the language and by leveraging the large investment that Microsoft has put into making the .NET platform fast; the current, more complete implementation has roughly the same speed as CPython. In general, the existing approaches have reached the end of the road, speed-wise. Microsoft’s Dynamic Language Runtime (DLR), often cited in this context, is essentially only an API to make the techniques pioneered in IronPython official. At best, it will give another small improvement.
Another technique regularly mentioned is adding types to the language in order to speed it up: either explicit optional typing or soft typing (i.e., inferred “likely” types). For Python, all projects in this area have started with a simplified subset of the language; no project has scaled up to anything close to the complete language. This would be a major effort and be platform- and language-specific. Moreover maintenance would be a headache: we believe that many changes that are trivial to implement in CPython, are likely to invalidate previous carefully-tuned optimizations.
For major improvements in speed, JIT techniques are necessary. For Python, Psyco gives typical speedups of 2 to 4 times - up to 100 times in algorithmic examples. It has come to a dead end because of the difficulty and huge costs associated with developing and maintaining it. It has a relatively poor encoding of language semantics - knowledge about Python behavior needs to be encoded by hand and kept up-to-date. At least, Psyco works correctly even when encountering one of the numerous Python constructs it does not support, by falling back to CPython. The PyPy JIT started out as a metaprogrammatic, non-language-specific equivalent of Psyco.
A different kind of prior art are self-hosting JIT compilers such as Jikes. Jikes is a JIT compiler for Java written in Java. It has a poor encoding of language semantics; it would take an enormous amount of work to encode all the details of a Python-like language directly into a JIT compiler. It also has limited portability, which is an issue for Python; it is likely that large parts of the JIT compiler would need retargetting in order to run in a different environment than the intended low-level one.
Simply reusing an existing well-tuned JIT like that of the JVM does not really work, because of concept mismatches between the implementor’s language and the host VM language: the former needs to be compiled to the target environment in such a way that the JIT is able to speed it up significantly - an approach which essentially has failed in Python so far: even though CPython is a simple interpreter, its Java and .NET re-implementations are not significantly faster.
More recently, several larger projects have started in the JIT area. For instance, Sun Microsystems is investing in JRuby, which aims to use the Java Hotspot JIT to improve the performance of Ruby. However, this requires a lot of hand crafting and will only provide speedups for one language on one platform. Some issues are delicate, e.g., how to remove the overhead of constantly boxing and unboxing, typical in dynamic languages. An advantage compared to PyPy is that there are some hand optimizations that can be performed, that do not fit in the metaprogramming approach. But metaprogramming makes the PyPy JIT reusable for many different languages on many different execution platforms. It is also possible to combine the approaches - we can get substantial speedups using our JIT and then feed the result to Java’s Hotspot JIT for further improvement. One of us is even a member of the JSR 292 Expert Group to define additions to the JVM to better support dynamic languages, and is contributing insights from our JIT research, in ways that will also benefit PyPy.
Finally, tracing JITs are now emerging for dynamic languages like JavaScript with TraceMonkey. The code generated by PyPy is very similar (but not hand-written) to the concepts of tracing JITs.
The description of the current PyPy JIT generator is given in PyJitPl5 (draft).