Python
jit
pyston
PythonDay 8

Pyston 0.3に関して

More than 3 years have passed since last update.


はじめに

こんばんは、はじめまして。

( ゚∀゚)o彡° pyston! pyston!!


Pyston概要

PystonはDropboxで開発している、Python2.7互換の処理系です。LLVMを利用したJITコンパイルによりpythonの高速化が期待されており、ライバルはpypyです。

今はx86_64しかサポートしていないようで、試すならubuntu14推奨です。

ビルド方法はこちらが詳しいです。

http://qiita.com/Masahito/items/edd028ebc17c9e6b22b0

2014/09にPystonはv0.2をリリースし、v0.3の開発に取り組んでいるようです。

0.3では、実際のベンチマークを対象に性能向上中です。

pystonのリポジトリの中には代表的なベンチマークが含まれており、

build済みであれば、make run_TESTNAMEでベンチマークを走らせることができました。


minibenchmarks

allgroup.py  fannkuch.py      go.py      interp2.py  nbody_med.py  raytrace.py

chaos.py fannkuch_med.py interp.py nbody.py nq.py spectral_norm.py


microbenchmarks

attribute_lookup.py  fib2.py            listcomp_bench.py  repatching.py          vecf_add.py

attrs.py function_calls.py nested.py simple_sum.py vecf_dot.py
closures.py gcj_2014_2_b.py polymorphism.py sort.py
empty_loop.py gcj_2014_3_b.py prime_summing.cpp thread_contention.py
fib.py iteration.py prime_summing.py thread_uncontended.py
fib.pyc lcg.py pydigits.py unwinding.py


Pystonの見どころ

JITコンパイラの特徴を、PystonのREADMEを見ながらいろいろと調べてみました。

https://github.com/dropbox/pyston

Pystonの見どころは、LLVMを利用したJITコンパイルだと思います。

LLVMをJITコンパイラとして利用したもので、もっとも有名なもとは、JavaScriptCoreのFTL JITだと思います。

こちらのFTL JITの説明が参考になります。

http://blog.llvm.org/2014/07/ftl-webkits-llvm-based-jit.html

JSCは4階層のJITコンパイルを行います。


  1. low-level interpreter (LLInt)

  2. baseline JIT

  3. DFG JIT

  4. FTL JIT (LLVMを使用するのはこれだけ)

Pystonでも4階層のJITコンパイルを行います。

JSCのJSBytecodeに対応して、Pyston 0.3からはPypaのParserおよびASTを利用するようです。


  1. LLVM-IR interpreter (EffortLevel::INTERPRETED)

  2. Baseline LLVM compilation (EffortLevel::MINIMAL)

  3. Improved LLVM compilation (EffortLevel::MODERATE)

  4. Full LLVM optimization + compilation (EffortLevel::MAXIMAL)

LLVMによるJITコンパイルは、2-3-4階層目で行っており、

2階層目では、LLVMによる最適化を行わず、実行時のTypeを収集するコードを埋め込みます。

4階層目では、実行時に収集したTypeを元にTypeSpeculationを行い、LLVMで最適化を行い、

高速なコードを生成します。

4階層目の対象は、10,000回以上実行されるループ、もしくは10,000回以上呼び出される関数です。

将来的には、3階層目は削除。1階層目のLLVM-IR interpreterは、独自実装に置き換えたいようです。

patchpointはLLVMのintrinsicsを利用しているようですが、

stackmapsは、独自実装なのかな?


Inlining

JITコンパイル時に、pythonのメソッドは適時inliningされるようです。

また、runtimeで頻繁に必要になる基本的な操作(boxing/unboxing)やコレクション(list/dict/tuple/xrange)は、

Pystonのコンパイル時にbitcodeを生成しておき、JITコンパイル時にbitcodeレベルでinliningを行うようです。

この辺が少し特徴的で、InlinerはLLVMのものを改造しつつ、Pyston独自のPassを作成したようです。

詳細はcodegen/opt/inlinerと、runtime/inline(これがbitcode生成するコレクション)


inline cache

RuntimeIC(void*addr, int num_slots, int slot_size)

で辞書を管理。辞書本体はICInfo

呼び出しは、RuntimeICを継承したクラスからの、call()

call自体はtemplateになってた。


lang

template <class... Args> uint64_t call_int(Args... args) {

return reinterpret_cast<uint64_t (*)(Args...)>(this->addr)(args...);
}

template <class... Args> bool call_bool(Args... args) {
return reinterpret_cast<bool (*)(Args...)>(this->addr)(args...);
}

template <class... Args> void* call_ptr(Args... args) {
return reinterpret_cast<void* (*)(Args...)>(this->addr)(args...);
}

template <class... Args> double call_double(Args... args) {
return reinterpret_cast<double (*)(Args...)>(this->addr)(args...);
}


詳しくは以下を参照

src/runtime/ics

src/asm_writing/icinfo


hidden class

V8のhidden class相当なのだろうか。

なぜかConservativeGCObjectを継承しているし、メソッドもGC向けのが多い。

なぞだ

Pythonの場合、attributeの違いを吸収するためにhidden class必要なのか?

Pythonの仕様よくわからない、attributeの違いが問題になるのか?

詳しくは以下を参照

src/runtime/objmodel


Type feedback

2-3階層のJITコンパイル時に、実行時の型情報を収集するコードを埋め込みます。

基本的には、実行時にBoxedClassのclsフィールドを取り出し、

recorderに記録させるasmを2-3階層目のJITコンパイル時にemitします。

JITコンパイル時に記録数が100以上になったものを、型の予測結果として採用するようです。

型の予測結果をCompileTypeとし、JITコンパイル時にdynamic typeからCompileTypeに特殊化します。

その際に、BoxedClassから、積極的にCompileTypeへのUnbox化を試行するようです。

speculationは、src/analysis/type_analysis

recorderはsrc/codegen/type_recording

runtimeでのrecord処理はsrc/runtime/objmodel


Object representation

Pystonで扱うInstanceはすべてboxedな状態のようです。

そのため、先頭にclsフィールドが埋まっていて、例としてBoxeIntはint64_tのvalueが格納されます。

BoxedClassの一覧は、たぶんこんな感じです。


lang

BoxedClass* object_cls, *type_cls, *bool_cls, *int_cls, *long_cls, *float_cls, *str_cls, *function_

*none_cls, *instancemethod_cls, *list_cls, *slice_cls, *module_cls, *dict_cls, *tuple_cls, *file_cls,
*member_cls, *method_cls, *closure_cls, *generator_cls, *complex_cls, *basestring_cls, *unicode_cls, *
*staticmethod_cls, *classmethod_cls;

各種コレクション(listやdict)やargsに格納できるのは、boxedなオブジェクトだけのようですが、

そこから実際の値を取り出す処理は、可能な限り特殊化するようです。

そのため、type feedbackの結果を元に、収集された関数のargsの型から実行時の型を推論し、

可能な限りboxedなオブジェクトを排除し、適時unboxed化を挿入するようです。

type speculationは、src/analysis, Box系は、src/runtime/classobjとその派生クラスを参照


Optimize

LLVMの最適化により、高速なコードを生成するようです。


lang

  doCompile()

CompiledFunction()
if (ENABLE_SPECULATION && effort >= EffortLevel::MODERATE)
doTypeAnalysis()
BasicBlockTypePropagator::propagate()
optimizeIR() /* LLVM PassManagerによりLLVMの最適化をセットする */
makeFPInliner() /* pyston独自のMyInliningPass */

EscapeAnalysis() /* pyston独自実装のEscapeAnalysis */
createPystonAAPass() /* Escape解析の結果を参照してAAの結果を更新する */

createMallocsNonNullPass() /* (malloced != NULL) を除去するっぽい */

createConstClassesPass()
createDeadAllocsPass() /* escapeしないallocを除去 */


主制御は、src/codegen/irgen.cpp

Speculation系はanalysis

独自開発のLLVM最適化パスは、codegen/optを参照

EscapeAnalysisは、alloc->stack確保に置き換えるのかと思いきや、

LLVMのModRef解析にたいして、NoEscapeな参照をNoModRefとしてフィードバックするだけのようでした。

LLVMのScalarReplAggregatesは、NoModRefを参照して、Allocaへ置換してくれるんだっけ?

DeadAllocsPassでは、AAの結果を参照してload/storeの参照を解析し、不要なLoadを除去する。 */

その後LLVMのdceでalloca相当の命令が根こそぎ除去されるのかもしれない。

http://blog.pyston.org/2014/11/06/frame-introspection-in-pyston/

blogでは、stackにlocal variablesを割り当てているようです。


C API native extension

v0.2から、C_APIの拡張をサポートしたようです。

サンプルコードとして、test/test_extensionにありました。

src/capiを参照


lang

static PyObject *

test_load(PyObject *self, PyObject *args)
{
if (!PyArg_ParseTuple(args, ""))
return NULL;

assert(stored);
Py_INCREF(stored);
return stored;
}

static PyMethodDef TestMethods[] = {
{"store", test_store, METH_VARARGS, "Store."},
{"load", test_load, METH_VARARGS, "Load."},
{NULL, NULL, 0, NULL} /* Sentinel */
};

PyMODINIT_FUNC
initbasic_test(void)
{
PyObject *m;

m = Py_InitModule("basic_test", TestMethods);
if (m == NULL)
return;
}



python処理系の最適化ポイント

こちらのIBM製PythonJITコンパイラに資料が詳しいので、参考にして

pythonではどういう部分が遅いのか調べてみました。

http://www.cl.cam.ac.uk/research/srg/netos/vee_2012/slides/vee18-ishizaki-presentation.pdf


  1. look up hash when access field /* icsで参照? field参照の高速化は不明*/

  2. check instance of a class /* 基本的なクラスはすべてboxed */

  3. search dictionary when call hasattr /* attrはよくわからん */

  4. exception check without splitting BBs /* pythonの例外って何か規約あるのか */

  5. specialize runtime type information /* type feedback and type speculation */

  6. speculatively builtin-functions /* bitcode inlining */

  7. reference counting without branch /* ??? */

  8. map to stack-allocated variables /* escape analysis and deadalloc */


まとめ

進捗だめだったので、ただのメモ書きになってしまいました。

他とPython処理系や、Pystonが参考にしているであろうJavaScriptのJIT処理系(V8やFTL JITなど)と比較してどんな感じなのか、雰囲気が伝われば幸いです。

PystonはPyPyやCpythonを比較対象とつつ、pypyのベンチマークを取り込んだりする予定のようです。

現状のPystonと比較すると、PyPy速すぎ、仕組みが根本的に異なります。

Pystonの今後に期待です。