ゴール¶

このプロジェクトではPythonを速くしたいと思っている。また、大きくて安定しているアプリケーションをこのプロジェクト”Unladen Swallow”に切り替えて使用してもらえるようにするのもゴールの一つである。

1. CPythonと比べて、最低でも5倍早いバージョンのPythonを作成する
2. Pythonアプリケーションの動作は安定していなければならない
3. CPythonアプリケーションと、ソースレベルの互換性を維持する
4. CPythonの拡張モジュールと、ソースレベルの互換性を維持する
5. Pythonの実装をずっと維持し続けたくはないため、Pythonとフォークするのではなく、ブランチとして活動する

概要¶

パフォーマンスと互換性という、二つのゴールを同時に達成するために、我々はスクラッチから作るのではなく、CPythonを改修していくという方法を取ることを決めた。具体的には、CPython 2.6.1に対して作業を始めることにした。Python 2.6が、2.4/2.5(ほとんどのアプリケーションが使用している)と、3.x(最終的に到達する未来)の、間のちょうどいい位置にあるからである。CPythonのリリースコードから開始したおかげで、我々は組み込みの関数やオブジェクト、標準ライブラリモジュールなどの重要な部品を再実装しなくて済んでいる。また、頻繁に用いられているCPythonのC言語による拡張のAPIもそのまま使用することができるのである。2.XのCPythonからスタートしているため、既存のアプリケーションからは簡単に移行することができる。もし、3.Xから始めていたら、大きなアプリケーションのメンテナンスをしている人たちにアプリケーションの移植からお願いする必要があり、私達が対象としているユーザにうまくスタートしてもらうのを難しいと思っていただろう。

多くの時間をPythonコードの実行速度の方にフォーカスして行う仕事がメインとなる。Pythonのランタイムライブラリに使用する時間は少なくなるだろう。我々が長期間かけて提案したいのは、LLVM上に構築された、Python用のJIT機能付きのカスタムの仮想マシンを補完することである。それ以外のPythonランタイムに関してはほとんどCPythonのままになる予定である。我々が今までに行ってきた調査によると、Pythonのアプリケーションはメインのevalループの中で多くの時間を消費しているということが分かっている。特に、opコードのディスパッチといった、VMの構成部品に比較的小さい変更を加えるだけで、Pythonアプリケーションのパフォーマンスには著しい効果がある。我々は、LLVMのJITエンジンを通じて、Pythonをマシンコードにコンパイルすと、極めて大きなパフォーマンスの向上が得られると信じている。

いくつか明確になっているメリット:

• JITを使用することで、Pythonをスタックベースマシンから、レジスタマシンにすることができる。こうすることで、過去にいくつかの似たような言語がパフォーマンスの向上を示している(Ierusalimschy et al, 2005; Shi et al, 2005)。
• 例え他に効果がなかったとしても、命令コードのフェッチとディスパッチが除去できるというだけで、十分にメリットは十分にある。http://bugs.python.org/issue4753 で行われている議論を見ると、CPythonの命令コードのディスパッチの変更がいかに難しい問題であるかが分かるだろう。
• 現在のCPythonのVMの命令コードのフェッチ/ディスパッチのオーバーヘッドはあまりに大きいために、追加の最適化が行えない状況になっている。例えば、SELF-93(Ho”lzle, Chambers and Ungar, 1992)の型のフィードバックと、動的な再コンパイルをしようとしても、ポリモーフィズムの使えるインラインキャッシュを実装するのが容認できないほど遅いと感じている。
• LLVMを使用しているため、さまざまなプラットフォームに対して簡単に使用できるコードジェネレータが利用できる。LLVMのコードジェネレータはC/C++を中間形式にコンパイルすることもできるが、それと同じコードをPythonから出力しようとしている。これにより、インラインでC/C++と連携したり、現在のPython/C言語間の障壁を越えたコード分析が行える。

マシンコードを生成するインフラを、Pythonをコンパイルする機能に加えると、現在のバイトコード表現で行えることよりももっと多くの効果的な実装が行えるようになる。例えば以下のようなコードがあったとすると：

for i in range(3):
  foo(i)

現在は以下のように変換される

$x = range(3)
while True:
  try:
    $y = $x.next()
  except StopIteration:
    break
  i = $y
  foo(i)

もしrange()というのが組み込み関数のrange()のことであるというのを知ることができれば、我々は以下のように変換することもできるだろう。

for (i = 0; i < 3; i++)
  foo(i)

C言語では、数値計算のためのアンボックス型を使用することもできる。また、以下のようにループを展開することもできるだろう。

foo(0)
foo(1)
foo(2)

我々は、Unladen Swallowの内部構造を、マルチコアが使用できることになることを想定した構造にしようと考えている。サーバにおいては、コア数は増える一方であり、より多くのタスクを並列でこなすために、性能を引き出せるようにしたいと考えている。例えば、他のコアで仕事をしつつ、より時間がかかるが性能の良い最適化を平行して行う並列コードオプティマイザを入れたいと考えている。また、並列ガーベジコレクションも導入して、負荷のかかっていない、あまっているコアを利用できるようにしたいと考えている。今日では、ほとんどのサーバの製品は、4個から32個のコアを載せて出荷されているので、私達はこの方向性での最適化が有利であると考えている。しかし、高度に並列化されたアプリケーションの需要については敏感に察知していかねば、と考えている。盲目的にコアを消費すればいいとは考えていない。

なお、我々が取り組もうとしている領域の多くの部分では、他の動的言語の実装がいくつも計画されていたり、開発されていたりする。例えば、MacRuby, JRuby, , Parrotや、他のPython実装である、Jython, PyPy, IronPythonなどである。我々はデバッグ情報に関するアイディアや、正規表現のパフォーマンスに関するアイディア、動的言語で一般的に使用されているパフォーマンスのためのアイディアというのを知るために、これらの他の実装を参考にさせてもらっている。これらは、すでに先人により踏み固められてきた部分であるため、一から車輪の再発明をすることは、できれば避けたいと考えている。

マイルストーン¶

Unladen Swallowは三ヶ月ごとにリリースを行う。また、それとは別に必要に応じてその間にバグフィックスのためのリリースを行う。

詳細の計画¶

すぐにできる改良を行って、何人かの人に我々のPythonが適用できると確信してもらったら、LLVMへの切り替え作業に入る予定である。おそらく、最初はブランチを切って作業を開始するだろう。これによって数多くの作業が行えるようになる。

1. (完了)llvmmoduleと、llvmfunctionの２つの型をPythonに追加する。これはLLVMのモジュールと関数型へのインタフェースである。llvmmoduleに対しては、ビットコードファイルの読み方と、それを整形して文字列化する機能を実装する。ビットコードファイルの読み込みは次のステップの開発には必要ではないが、テストを楽にすることができる。llvm-pyはこのようにラップされた型をいくつか持つが、コアインタプリタ内でPythonによって定義された型を使用するのはとても難しい。そのため、自分たちでこれらを書き直そうと考えている。llvm-py内に実装されるものは完全なラッパーとはならないが、デバッグが便利になると考えている。
2. (完了)LLVM IR(中間コード)で定義されたPython関数を実行する方法を追加する。これらの関数のコンパイルと実行にはLLVM JITを使用する予定である。この作業自体は迅速に進んだが、開発の間中面倒をみる必要があると思われる問題がいくつか残っている。
3. (作業中) CPythonのバイトコードに加えて、llvmmoduleやllvmfunction型としてLLVM IRを生成するコンパイラを組み込む。この作業は少しずつ進行させていくが、その間中、Pythonインタプリタとしても動作可能なまま作業を行っていく。作業の進捗は、Python/ll_compile.h内の未実装(UNIMPLEMENTED)の命令コードで見ることができる。命令コードごとにLLVM IRのほぼ手作業で変換するという作業を行っている。作業のほとんどは、関数を分解して、これらを呼ぶという方法でできる。しかし、いくつかのPythonの構造はそう簡単には実装できない。

• クロージャー: クロージャーというのは、宣言された環境をパラメータとして設定された関数である。
• 例外のハンドリング – c版のevalの例外ハンドリング機構を変換する作業は順調とは言い難い状況である。CPythonは、ジャンプ先のバイトコードのインデックスを保存する。LLVMは命令のアドレスを保存することはできないため、例外ハンドラとして使用される基本ブロックと、適切なブロックにジャンプするswitch文を生成するようにしている。
• 関数呼び出し規則 – すべての引数を含むPyFrameObjectを渡している。生成コストは我々が期待しているものよりも高価である。PyFrameObjectはスタックのように動作し、関数から戻る時にローカル変数を戻すのに使用されるが、LLVMが最適化するのを妨げてしまうのである。
• ジェネレータ: 我々は、例外ハンドラで行ったのと同じように、yieldステートメントの数を数える予定である。そして、関数の中に、switch文を作成し、一度抜けたyield文から復帰できるポイントをブロックとして表現することを考えている。yieldの呼び出しの前後では、すべてのレジスタとローカル変数を保存する必要がある。幸いなことに、現在のCPythonのバイトコードからの変換作業の中では、スタックとローカル変数はすべて、return時にFrameObjectに保存するようにしているため、yieldからの復帰を実現するのも簡単にできる見込みである。しかし、フレーム内にローカル変数を保存するのをやめてしまうと、これを実現するのが難しくなってしまう。本来ならば、疑似レジスタの保存・復帰機能があればよかったが、残念ながら、現在のLLVMにはそのような機能は実装されていない。

4. おそらく、LLVM中間コードジェネレータと、CPythonコンパイラを切り離す。すべての関数に対して中間コードを生成するのは、メモリと時間の観点で見ると、かなりコストがかかる。すべてのJITコンパイラ内蔵のシステムがやっているように、使用頻度の高い関数に関してのみコンパイラすることで、よりパフォーマンスが向上するだろう。この処理を入れる前に、両方の選択肢の測定をする必要はあるだろう。
5. .pycを永続化するにあたって、一番簡単に行うにはどのようにするかを理解する。今考えているのは、PythonモジュールをLLVMモジュールとしてバイトコードにして実行できる形式でディスクに保存することである。将来的(step11)には情報がぎっしり詰まったプロファイリングのデータと、最適化前のコードも追加したいと考えている。
6. Pythonに対して、高速JITと低速JITを、ある関数はどちらを適用するか、というのをどのように決定するか、というのを教える(JIT::createにfast==Trueを渡す)。nlewycky氏は「コード生成は高速モードにおいては、おおまかに3倍は高速(計測時はリリースモードではなく、デバッグモード)」と話をしている。このタスクの中では、ただしいバランスを見つけるためには、非常に細かい調整が必要になりそうである。この時点で、我々の最初のリリースよりも早くなることが期待される。

7. 追加の最適化の追加の開始 Talin氏は、Pythonの関数呼び出しが間接的であるため、事前定義の最適化に関する技術を前もって適用するのは困難であると指摘している。そのため、直接呼出しができるように、型推論に取り組みたいと考えている。

8番目以降の項目は、2009の第二四半期の終わりに向けて、平行で作業を行っていく。

• Step4の成果と関連する項目。よりよいプロファイルやコンパイル結果が得られるように、CPythonバイトコードからのLLVM中間コード生成をやり直すか、あるいはAST情報を使用してLLVM中間コードへのコンパイルを直接行いたい。
• どのようにして特定の型に対して、特別バージョンの関数を定義すればいいかを考える。これができれば、インライン化されて高速になる。Psycoのアルゴリズムを盗むことができるため、同じぐらい簡単にできるはずである。
  1. インタプリタに対して、どの特別版を使用すればいいのかをユーザがアノテーションを使って指定できるようにする
  2. メソッド呼び出しとをプロファイルし、一般的な引数の型を推測する
• 9bと10は与えられた関数を実現するためには、複数のバージョンのコードを取得し、既存の呼び出し元に対してさかのぼってパッチを与える必要がある。我々は複数バージョンのGCが必要になるだろう。興味深くなるはずである。
• 生成されて、最適化された中間コードを、.pycファイルの代わりにディスクに保存する。このとき、同時に収集済みのプロファイルデータも保存する。２回目以降の実行時には、前回の実行時に既に行われた最適化のメリットを享受することができるようになる。LLVMが約束している「一生涯にわたるプログラム分析と変換のためのコンパイルフレームワーク」という標語にも合っている。

テストと測定¶

リスク¶

Pythonのメインのソースコードに対して結果をフィードバックすることがおそらくできない:

Pythonのコア開発コミュニティのメンバーの中には、我々が行った変更が大きすぎるということで反対する人がいる。しかし、これは正しいことである。このような状況において、変更に反対することは健全なことである。我々のパッチを公に検査を行うことは、かなりの労力をさいたとしても、CPythonのメンテナンスに長期にわたる影響を与えてしまうからである。もちろん、Pythonはオープンソースであるので、変更をチェックしようと言う人が現れるのは大歓迎である。我々は、自分達の提案は正当なものであると認めてもらうことは可能であると信じている。Guidoや他のコミュニティメンバーと緊密に協調し続けているが、我々の変更は、受け入れてもらうチャンスがある内容に限定したいと考えている。しかし、いくつかのパッチはリジェクトされる可能性もまだある。そうなると、我々はデファクトのPython実装とは別のPython実装をサポートし続けるか、あるいは妥協して、期待ほど速くない実装で我慢するかしなければならない。人生と言うのはそういうものである。

LLVMにまつわる多くの未知のもの:

拡張モジュールの影響は？マルチスレッドアプリケーションにおけるJITの動作は？Pythonの起動時間に与える影響は？

Windowsサポート:

現在のCPythonのWindowsサポートはすばらしいので、メインのコードに我々のパッチをマージする際にもこれは維持する必要があると考えている。Unladen SwallowのエンジニアはWindowsの経験が浅いか、ない人が多く、Windowsマシンもないが、我々の進捗を多少遅らせても大丈夫なレベル、もしくはいくつかのパフォーマンス改善コードを無効にしたとしても、windowsのサポートは維持していこうと考えている。コミュニティの貢献により、これらのことが行うことができている。

特殊なプラットフォーム:

CPythonは現在、巨大な鉄の塊のサーバマシンから、Nokiaのケータイ電話まで、幅広いハードウェア、ソフトウェアのプラットフォームで実行できる。このプロジェクトでは、移植性と柔軟性をできる限り維持したいと考えている。LLVM(や、手書きのJITコンパイラ)を使用することでメモリ使用量と、Pythonのバイナリファイルのサイズが大きくなることはわかっている。そのため、程度によっては、以前サポートされていたプラットフォーム上でもUnladen Swallowが実行できなくなってしまう可能性もある。このリスクを軽減するために、Unladen SwallowではLLVM統合を完全に無効にして、以前のevalループを強制的にしようさせる、./configureのフラグを導入しようと考えている。

コミュニケーション¶

Unladen Swallowに関するすべてのコミュニケーションは、Unladen Swallowのメーリングリスト上で行われるべきである。このメーリングリストでは、設計に関する議論が行われ、ビルド結果、パフォーマンスの数値、コードレビューの結果が定期的に報告され、その他のオープンソースプロジェクトに関するすべての詳細な話も行われる。もしこのページ(Unladen Swallowのwiki)にコメントを付けたとしても、見落とすことがあるかもしれないため、申し訳ないが、メーリングリストの方にメールを出してもらいたい。