Shogo's Blog

たぶんプログラミングとかについて書いていくブログ

Re: GoとPythonとGrumpyの速度ベンチマーク

GoとPythonとGrumpyの速度ベンチマーク ~Googleのトランスパイラはどれくらい速い?~という記事を拝読したのですが、 もう一歩踏み込んで検証して欲しい・・・。

並列処理性能が優れているほか、PythonコードからGoのパッケージをPythonモジュールのように呼び出して利用することもできるという特徴がある。

Google、すごくスケールするPython実行環境をGoで開発から引用しているのに、 この件に全く触れていないんですよね。 Twitterに呟いたってどうせ誰もやってくれない気がするので、自分で試してみました。

環境

この記事を書いている2017年5月30日現在の最新バージョンで検証しました。

  • go version go1.8.3 darwin/amd64
  • CPython 2.7.13
  • Grumpy d8d01899f5

Grumpyのインストール方法はREADMEにある通り。

1
2
3
make
export GOPATH=$PWD/build
export PYTHONPATH=$PWD/build/lib/python2.7/site-packages

ただ個人的な環境問題としてPythonのバージョン管理に利用しているpyenvとの相性が悪いらしく、 pyenvが管理しているPythonへのパスを直接通す必要がありました。 (これがないとPythonスクリプトがなぜかbashに処理される。なんかこの問題最近Twitterで見たような・・・)

1
export PATH=$HOME/.pyenv/versions/2.7.13/bin:$PATH

モンテカルロ法を並列実行してみる

まず、並列処理性能について検証してみましょう。 モンテカルロ法の各試行は独立しているので、並列実行にするのは容易です。 Python2のthreadingモジュールを使って並列実行してみましょう。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#coding:utf-8
# モンテカルロ法 Pure Python 並列版
import threading
import random
import sys

class MyThread(threading.Thread):
    def __init__(self):
        super(MyThread, self).__init__()
        self.c = 0

    def run(self):
        r = random.Random()
        c = 0
        for _ in xrange(num):
            x = r.random()
            y = r.random()

            if x * x + y * y <= 1.0:
                c += 1
        self.c = c


if __name__ == "__main__":
    num = int(sys.argv[1])
    para = int(sys.argv[2])

    threads = []
    for i in xrange(para):
        t = MyThread()
        t.start()
        threads.append(t)

    c = 0
    for t in threads:
        t.join()
        c += t.c

    print 4.0*c/(num*para)

並列度に比例した計算負荷がかかるようになってます。 理想的な並列処理が行えていれば、並列度に関わらず同じ実時間で実行されるはずです。

CPythonでの結果

CPythonでtimeを使って雑に測定した結果です。 並列度を4倍にしたら実行時間も4倍になっています。 また、実時間と実行時間が大体おなじで、まったく並列実行できていません。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 並列度1で実行した場合(CPython)
$ time python con_monte.py 300000 1
3.14529333333
real    0m0.358s
user    0m0.279s
sys 0m0.032s

# 並列度4で実行した場合(CPython)
$ time python con_monte.py 300000 4
3.14382666667
real    0m1.261s
user    0m1.124s
sys 0m0.441s

CPythonを利用しているひとにはおなじみのグローバルインタプリタロック(GIL: Global Interpreter Lock)の影響ですね。 CPythonのスレッドはI/Oの並列化には向いていますが、計算の並列化には向いていません。

Grumpyでの結果

次にGrumpyで測定した結果です。 並列度を4倍にしたところ、実行時間は2倍程度になりました。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 並列度1で実行した場合(Grumpy)
$ time ./con_monte_darwin_amd64 300000 1
3.1441733333333333
real    0m16.129s
user    0m16.787s
sys 0m0.125s

# 並列度4で実行した場合(Grumpy)
$ time ./con_monte_darwin_amd64 300000 4
3.1401766666666666
real    0m33.935s
user    1m45.979s
sys 0m0.654s

実時間4倍までは行かなかったので、理想的な並列計算には及ばないものの、 CPythonよりは並列化の効果が出ていそうです。 実のところ、Goも計算の並列化よりI/Oの並列化・並行処理のほうが得意なんですよね(GILよりはまし)。

手元の4コアのMBAで試した結果なので、コア数が多いとまた結果が変わってくるかもしれません。

PythonからGoのライブラリを直接呼び出す

次にGoのパッケージを呼び出す機能を試してみます。 Pythonのrandomパッケージではなく、Goのmath/randパッケージを使ってモンテカルロ法を実行してみます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#coding:utf-8
# モンテカルロ法 Python+Go 並列版
import threading
import random
import sys
from __go__.time import Now
from __go__.math.rand import New, NewSource


class MyThread(threading.Thread):
    def __init__(self):
        super(MyThread, self).__init__()
        self.c = 0

    def run(self):
        r = New(NewSource(Now().UnixNano()))
        c = 0
        for _ in xrange(num):
            x = r.Float64()
            y = r.Float64()

            if x * x + y * y <= 1.0:
                c += 1
        self.c = c


if __name__ == "__main__":
    num = int(sys.argv[1])
    para = int(sys.argv[2])

    threads = []
    for i in xrange(para):
        t = MyThread()
        t.start()
        threads.append(t)

    c = 0
    for t in threads:
        t.join()
        c += t.c

    print 4.0*c/(num*para)

Grumpyでの結果

Grumpyでの実行結果です。 CPythonには遠く及ばないものの、もとのコードの8倍速くらいにはなりました。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 並列度1で実行した場合(Grumpy)
$ time ./con_monte_go_darwin_amd64 300000 1
3.1388133333333332
real    0m1.921s
user    0m2.006s
sys 0m0.029s

# 並列度4で実行した場合(Grumpy)
$ time ./con_monte_go_darwin_amd64 300000 4
3.143743333333333
real    0m4.115s
user    0m12.855s
sys 0m0.096s

竹内関数を並列実行してみる

竹内関数を並列実行した場合も試してみました。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#coding:utf-8
# 竹内関数 Pure Python 並列版
import sys
import threading

def tak(x, y, z):
    if x <= y:
        return y
    else:
        return tak(tak((x-1), y , z), tak((y-1), z , x), tak((z-1) , x, y))

class MyThread(threading.Thread):
    def __init__(self, a, b, c):
        super(MyThread, self).__init__()
        self.a = a
        self.b = b
        self.c = c
        self.result = 0

    def run(self):
        self.result = tak(self.a, self.b, self.c)

def main():
    a = int(sys.argv[1])
    b = int(sys.argv[2])
    c = int(sys.argv[3])
    para = int(sys.argv[4])

    threads = []
    for i in xrange(para):
        t = MyThread(a, b, c)
        t.start()
        threads.append(t)

    for t in threads:
        t.join()
        print t.result

if __name__=="__main__":
    main()

モンテカルロ法と同様に、理想的な並列処理が行えていれば、並列度に関わらず同じ実時間で実行されるはずです。

CPythonでの結果

CPythonでの結果です。 モンテカルロ法の場合と同様に、 並列度を4倍にしたら実行時間も4倍になっています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 並列度1で実行した場合(CPython)
$ time python con_take.py 11 10 0 1
11
real    0m1.529s
user    0m1.498s
sys 0m0.028s

# 並列度4で実行した場合(CPython)
$ time python con_take.py 11 10 0 4
11
11
11
11
real    0m7.333s
user    0m6.620s
sys 0m2.565s

Grumpyでの結果

Grumpyでの結果です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 並列度1で実行した場合(Grumpy)
$ time ./con_take_darwin_amd64 11 10 0 1
11
real    0m0.988s
user    0m0.988s
sys 0m0.018s

# 並列度4で実行した場合(Grumpy)
$ time ./con_take_darwin_amd64 11 10 0 4
11
11
11
11
real    0m2.031s
user    0m7.135s
sys 0m0.031s

(なんかCPythonより早くなったぞ????)

最初に紹介した記事でも、 モンテカルロ法のベンチマークではCPythonがGrumpyの数十倍の速度で圧倒的勝利でしたが、 竹内関数のベンチマークではその差は縮まっています。 この程度であれば並列度を上げて物理で殴れば容易にGrumpyが逆転するでしょう。

(この検証で並列度1のときもGrumpy勝ったの謎だけど・・・)

考察

モンテカルロ法はCPythonのほうが圧倒的に速かったのに、 竹内関数ではGrumpyのほうが速かった(あるいは差が縮まった)という結果から、 「GrumpyからGoの関数を呼び出すオーバーヘッドが大きい」のではと推測しています。 モンテカルロ法のPure Python版でも圧倒的差が付いたのは、 Grumpyのrandomパッケージの実装が内部でGoのmath/randを呼んでいるからです。

純粋なPure Pythonなコードであれば、Grumpyのシングルスレッド性能はCPythonより数倍遅い程度です。 最近のCPUコアたくさんなマシンであれば、GILのなくマルチスレッドを活かせるGrumpyが有利になると思います。 このことはグーグルのブログ記事「Grumpy: Go running Python!」でも触れられていますね。

まとめ

  • Grumpyが非常に遅いのではなく、「GrumpyからGoの関数を呼び出すオーバーヘッドが大きい」(推測)
  • Grumpyのシングルスレッド性能はCPythonより数倍遅い程度
  • 並列処理性能ではGrumpyが有利
  • そもそもGrumpyの目的は計算速度を上げることではないので、計算速度向上を求めている人は他の手法を模索しましょう

今回の検証に使用したソースコード、Grumpyによるトランスパイルの結果、各種プラットフォームのバイナリをGithubにあげておきました。

さらに検証を進めたい方は参考にどうぞ。

参考

Comments