Kesinの知見置き場

知見を共有していきたいじゃないですか

Pythonを高速化するCythonを使ってみた

突然ですが私はPythonが好きです。でもPythonは遅いです。
何が遅いかというと、致命的なことに四則演算が遅いです。でも他の動的型付け言語でスクリプト言語と呼ばれるPerl, Ruby, Javascript も C, Javaのようなコンパイルを行う静的型付け言語に比べれば圧倒的に遅いです(近年ではJavascriptのように著しく進歩した言語もあるので必ずしもそうだとは言えませんが)。
スクリプト言語が遅い原因の一つは、変数の型が指定されていないので型のチェックを毎回行う必要があるからです。この特性があるおかげ自動的に型を変換してオーバーフローを防いでくれるというメリットもあるのですが、どうしても静的型付け言語よりは速度を出すことができません。
ならPythonのコードに型指定を加えてコンパイルしちゃえばいいじゃん!というのがCythonです。正確にはPythonライクな文法で書いたコードをC/C++に変換してコンパイルします。噂では単純な計算だとPythonのコードを実行するより100倍以上も高速化することもあるらしい(!)ということで試してみました。


Cythonの基本的な使用方法は公式のドキュメントをご覧下さい
http://docs.cython.org/
日本語版
http://docscythonja.zouri.jp/


注意:以下のベンチマークMacOS 10.7.3 MacBook Core2 Duo 2.26GHzでPythonC/C++コンパイラはMac標準のPython2.7.1, llvm-gccを使用しています。
C/C++はtimeコマンド、Python/Cythonはipythonのtimeitを利用して実行時間を測定しています。
なお、以下の記録はあくまで私の環境、私の実装での記録なので比較の結果は正しいというものではないです。記事の下の方に他の方のベンチマークへのリンクを載せましたのでそちらもご覧下さい。

単純な加算

まずは単純な加算を比較してみましょう。1~100000000までの数を足しあわせます。

C
$ gcc -O2 simple_add.c
$ time ./a.out

real     0m0.004s
user     0m0.001s
sys     0m0.003s
Python
In [1]: import test_py
In [2]: timeit -n1 test_py.simple_add(100000000)
1 loops, best of 3: 8.39 s per loop

Python遅っ!Cは多分速すぎてちゃんと測定できてないです。
ではCythonを使ってみましょう。pyximportを使用するとCythonがimport時にコンパイルしてくれます。まずはPythonのコードを何も変更しないでただコンパイルしてみましょう.

Python/pyximport+.py
In [1]: import pyximport; pyximport.install(pyimport = True)
In [2]: import test_py
In [3]: timeit -n1 test_py.simple_add(100000000)
1 loops, best of 3: 4.27 s per loop

おお!何もしないで2倍近く速くなりました!これだけでも十分ありがたい結果です。
次はコードに何も手を付けずに拡張子をCythonの.pyxに変更してみます

Cython/pyximport+.pyx
In [1]: import pyximport; pyximport.install()
In [2]: import test_cy
In [3]: timeit -n1 test_cy.simple_add(100000000)
1 loops, best of 3: 4.36 s per loop

前の結果とほとんど変わらないですね。誤差の範囲でしょう。
さていよいよ本番です。pyxで型の指定を行います。cdefで型を指定することでCの変数を使うので速くなるそうです。

Cython/cdef
In [1]: import pyximport; pyximport.install()
In [2]: import test_cy
In [3]: timeit -n1 test_cy.simple_addc(100000000)
1 loops, best of 3: 1.19 us per loop

・・・( ゚д゚)
Pythonと次元が違う、というか時間のオーダーが全然違います。Cの時間がtimeコマンドでは測定不能でしたが、これに迫る速さ?

結果:
time(s) Pythonとの相対効率(倍)
C 測定不能 測定不能
Python 8.39 1.0
Python/pyximport+.py 4.27 1.96
Cython/pyximport+.pyx 4.36 1.92
Cython/cdef 0.00000119 7050420

if文と動的配列

次はif文を使用して10000000までの奇数を動的に配列に入れるという処理をしてみます。
C++は慣れていないですが、vectorを使って実装してみました。Pythonはlist.appendを使用します。

C++/vector
$ g++ -O2 odd.cpp
$ time ./a.out

real     0m0.195s
user     0m0.083s
sys     0m0.106s
Python/list
In [1]: import test_py
In [2]: timeit -n1 test_py.odd(10000000)
1 loops, best of 3: 2.24 s per loop

list.appendとかありえん!Python使いだったらリスト内包表記だろ常考!という声が聞こえてきますのでリスト内包表記でも試してみます。

Python/list内包表記
In [1]: import test_py
In [2]: timeit -n1 test_py.odd_listcomp(10000000)
1 loops, best of 3: 1.64 s per loop

なるほど、内包表記にするとたしかに速くなります。しかし、さすがにC++と比べると全然といったところ。
Cythonでは問題なくリスト内表記が使用できるので、Pythonのコードに型指定だけ加えてコンパイルします。ここからはsetup.pyを用意してコンパイルを行います。

Cython/cdef+list内包表記
In [1]: import test_cy
In [2]: timeit -n1 test_cy.odd_listcomp(10000000)
1 loops, best of 3: 288 ms per loop

C++に届きませんが、元のPythonよりかなり高速になりました。Cythonでもリスト内包表記が使えるのはありがたいです。
次はCythonでC++vectorを呼び出してみます.実はCythonではC++の標準ライブラリが簡単に使えるようになっていて、deque, list, map, pair, queue, set, stack, vectorがサポートされているようです。vectorvector[int]というように少し文法が異なりますが、PythonC++を書いている感じになってきました。

Cython/vector
In [1]: import test_cy
In [2]: timeit -n1 test_cy.odd_vec(10000000)
1 loops, best of 3: 97.4 ms per loop

ええー!?C++より速い・・・。C++はプログラム全体の実行時間をtimeコマンドで計測してるのに対して、Cythonはipythonでimportしてから関数だけを呼び出すので有利な条件にはなっていますが、ここまで迫るとは正直予想していませんでした(^_^;)

結果:
time(s) Pythonとの相対効率(倍)
C++/vector 0.195 11.5
Python/list.append 2.24 1.0
Python/list内包表記 1.64 1.37
Cython/cdef+list内包表記 0.288 7.78
Cython/vector 0.0974 23.0

配列に対する計算

3つ目は、NumPyとも比較してみます。1~10000000までの数を格納した配列全てでlogを取ってから、逐次読み取ってsumを計算します。NumPy以外はlogとsumの計算を一度にやってしまってもいいのですが、NumPyに有利なようにlogとsumの行程を分けてあります。また、念のため計算結果を表示します。
まずはC++Pythonから。

C/vector+math.log
$ g++ -O2 logsum.cpp
$ time ./a.out
1.51181e+08

real     0m0.742s
user     0m0.515s
sys     0m0.197s
Python/math.log
In [1]: import test_py
In [2]: li = [i for i in xrange(1, 10000000)]
In [3]: timeit -n1 test_py.logsum(li)
151180949.369
151180949.369
151180949.369
1 loops, best of 3: 3.48 s per loop

次はCythonでC++と同じようにvectorを使用します。また、Pythonのmathを使用しないでCのmath.hを使用する方が速いそうなのでそちらを利用します。

Cython/vector+cdef math.log
In [1]: import test_cy
In [2]: li = [i for i in xrange(1, 10000000)]
In [3]: timeit -n1 test_cy.logsum(li)
151180949.369
151180949.369
151180949.369
1 loops, best of 3: 850 ms per loop

いい感じですね。C++に近い速度が出てます!
次はPythonで行列計算が得意なNumPyを使用してみます。

Python/Numpy
In [1]: import test_py
In [2]: li = [i for i in xrange(1, 10000000)]
In [3]: timeit -n1 test_py.logsum_numpy(li)
151180949.369
151180949.369
151180949.369
1 loops, best of 3: 2.09 s per loop

うーん・・・単純にPythonで書くよりは高速ですが、Cython/vectorの結果を見てしまうと(^_^;)
NumPyはSIMD命令に対応しているらしいのでもっと速いと思っていたのにかなりガッカリです。
NumPyは慣れてしまえば行列に対する計算を分かりやすくコンパクトに書けるのですが、本気で速度を気にするならCythonでゴリゴリ書くべきなんでしょうかね・・・(本当はC++でゴリゴリ書くべき)

結果:
time(s) Pythonとの相対効率(倍)
C++/vector+math.log 0.742 4.69
Python/math.log 3.48 1.0
Cython/vector+cdef math.log 0.850 4.09
Python/NumPy 2.09 1.67

*オマケ

CythonはNumPyにもサポートしているそうなのでどれだけ高速化するのか試してみます。
10000*10000の行列に0から順に入れて、全て+1した後に行ごとのsumで割って、行列全ての合計を求める。行ごとのsumで割ると行の合計は1.0になるはずなので、sum=1*1000になるはずです。

Python/Numpy
In [1]: import test_py
In [2]: timeit -n1 test_py.dim2sum_numpy(1000)
1000.0
1000.0
1000.0
1 loops, best of 3: 869 ms per loop
Cython/Numpy+cdef int
In [1]: import test_cy
In [2]: timeit -n1 test_cy.dim2sum_numpy(1000)
1000.0
1000.0
1000.0
1 loops, best of 3: 621 ms per loop

CythonはPython/NumPyのコードのループに使用する変数をint型に指定しただけです。劇的なスピードアップはありませんが、ほぼコードの改変無しにしては十分でしょう。
次はcimportでNumPyを使用します。こうするとNumPyの配列に高速にアクセスできるらしい。

Cython/cimport Numpy+cdef int
In [1]: import test_cy
In [2]: timeit -n1 test_cy.dim2sum_pynumpy(1000)
1000.0
1000.0
1000.0
1 loops, best of 3: 630 ms per loop

あれ、変わらない?cimportで効果があるのは引数にNumPyの配列を受け取るときだけなのだろうか?
うーん、勉強不足ですいません(^_^;)

結果:
time(s) Pythonとの相対効率(倍)
Python/NumPy 0.869 1.0
Cython/NumPy+cdef int 0.621 1.4
Cython/cimport NumPy+cdef int 0.630 1.38


追記(3/10):
@lucidfrontier45さんに時間が変わらないのはnumpy.ndarrayをcdefしていないからだと教えて頂きました。
さらに、そもそもndarrayの配列の参照はfoo[i][j]よりもfoo[i,j]の方が速いことが分かったので、この2点を修正してやりなおしました。

結果(修正版):
time(s) Pythonとの相対効率(倍)
Python/NumPy 0.350 1.0
Cython/NumPy+cdef int 0.222 1.58
Cython/cimport NumPy+cdef int 0.0431 8.12

Cythonを使わなくても2次元のndarrayの参照の方法を変えただけで速くなりました!これは今後も気を付けなければ・・・。
Cythonの方はndarrayをcdefしてやるとかなり速くなることが確認できました。今回のコードだとndarray.sum()を使用している部分が多いですが、配列の逐次参照部分が多ければもっと差がつくのではないかと思います。
アップしてあるコードも修正しました

他の方のベンチマーク

High Performance Python tutorial v0.2 (from EuroPython 2011) 上の方のpdf
Pythonを高速化する様々な手法のベンチマークが載っている.
Python2.7 < PyPy1.5 < Cython < Cython+numpy < ShedSkin
の順番に高速だったらしい.ShedSkinはCythonと同様にPythonC++に変換するものらしいけどまだ実験段階?


Speeding up Python (NumPy, Cython, and Weave)
Python < NumPy < Weave < Cython
WeaveというのはSciPyのモジュールでPythonのコードにインラインでCのコードを書けるものらしい.

結論

今回の結果と自分のスキル,可読性を考えると
Python << NumPy < Cython < Cython+NumPy
例外として互換性を完全に捨てる形でほぼCのCython
という感じだろうか.
NumPyとCythonを勉強していくうちに順位が変わる可能性は大いにありそうです


今回使用したソースコードgithubにアップしました

追記(2013/9/16):
かなり今更ですが、Cython公式のチュートリアルに沿って、NumPy+Cythonの組み合わせをさらに高速化する記事を書いていました。NumPyとCythonを組み合わせると爆速!
その記事の最後に触れていますが、Cythonのコンパイルオプションを変更すると、デフォルトの設定よりもさらに高速化させることができます。
残念ながらまだ和訳はされていないようですが、興味がある方は本家ドキュメントのこちらをどうぞ
http://wiki.cython.org/enhancements/compilerdirectives