Pyston 0.3に関して

# はじめに
こんばんは、はじめまして。
( ﾟ∀ﾟ)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の開発に取り組んでいるようです。

* python0.2のrelease note
http://blog.pyston.org/2014/09/11/9/

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

pystonのリポジトリの中には代表的なベンチマークが含まれており、
build済みであれば、make run_TESTNAMEでベンチマークを走らせることができました。

```lang: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
```

```lang: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: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ではどういう部分が遅いのか調べてみました。

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