Go to Qiita Advent Calendar 2024 Top
LoginSignup
14
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

PythonAdvent Calendar 2014

Day 8
@nothingcosmos(佑樹 坂頂)

Pyston 0.3に関して

Last updated at Posted at 2014-12-07

はじめに

こんばんは、はじめまして。
( ﾟ∀ﾟ)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を見ながらいろいろと調べてみました。

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:src/runtime/ics.cpp
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:src/codegen/irgen.cpp
  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:test/basic_test.c
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ではどういう部分が遅いのか調べてみました。

  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の今後に期待です。

14
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?