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でPythonとC/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コマンドでは測定不能でしたが、これに迫る速さ?
if文と動的配列
次はif文を使用して10000000までの奇数を動的に配列に入れるという処理をしてみます。
C++は慣れていないですが、vectorを使って実装してみました。Pythonはlist.appendを使用します。
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がサポートされているようです。vector
配列に対する計算
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
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++でゴリゴリ書くべき)
*オマケ
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と同様にPythonをC++に変換するものらしいけどまだ実験段階?
Speeding up Python (NumPy, Cython, and Weave)
Python < NumPy < Weave < Cython
WeaveというのはSciPyのモジュールでPythonのコードにインラインでCのコードを書けるものらしい.
結論
今回の結果と自分のスキル,可読性を考えると
Python << NumPy < Cython < Cython+NumPy
*例外として互換性を完全に捨てる形でほぼCのCython
という感じだろうか.
NumPyとCythonを勉強していくうちに順位が変わる可能性は大いにありそうです
追記(2013/9/16):
かなり今更ですが、Cython公式のチュートリアルに沿って、NumPy+Cythonの組み合わせをさらに高速化する記事を書いていました。NumPyとCythonを組み合わせると爆速!
その記事の最後に触れていますが、Cythonのコンパイルオプションを変更すると、デフォルトの設定よりもさらに高速化させることができます。
残念ながらまだ和訳はされていないようですが、興味がある方は本家ドキュメントのこちらをどうぞ
http://wiki.cython.org/enhancements/compilerdirectives