GoとPythonとGrumpyの速度ベンチマーク ～Googleのトランスパイラはどれくらい速い？～

#概要
- GrumpyというPythonからGoへのトランスパイラを使ってみた
- GoとPythonとGrumpyでベンチマークを取ってみた
- 処理速度は Go >> Python >> Grumpyで非常にGrumpyが遅かった

#Grumpyとは
*Googleは1月4日(米国時間)、「Google Open Source Blog: Grumpy: Go running Python!」において、Goで開発されたPython実行環境「Grumpy」を発表した。GrumpyはGoで実装されたPython実行環境。Pythonのコードを一旦Goのコードに変換することで動作するコンパイラ方式を採用。並列処理性能が優れているほか、PythonコードからGoのパッケージをPythonモジュールのように呼び出して利用することもできるという特徴がある。*

引用：[Google、すごくスケールするPython実行環境をGoで開発](http://news.mynavi.jp/news/2017/01/06/110/)

いわゆるトランスパイラと呼ばれるもので，PythonのコードがGoのコードへ変換される．という非常に変わったものです．他のJavascriptなどでは，AltJSと呼ばれるような言語(TypeScriptやCoffeeScript)とかがありますが，元となる言語がPythonで，変換先がGoというのはなかなか珍しいものです．しかも，普通のスクリプト言語のPythonがネイティブなバイナリになる．というのもなかなか面白いところがあります．

#実験の目的

**PythonがGrumpyによってネイティブのバイナリになったら爆速になるんじゃない？**

ということが一番気になったところです．先述した記事にもありますが，「GrumpyはCPythonより速い」といった前評判がありました．私自身Goでコード書くのはあまり慣れていないですが，Go自身には結構興味があります．特にGoでコンパイルされたバイナリ1つで動いてしまうため，ポータビリティ性に優れ，デプロイも非常に簡単だな．と思います．WebアプリをPythonで書けて，CPythonより速くて，Goのように1バイナリで動く世界になる．とPythonスキーの自分では文句の付けどころがない．と思って，速度のベンチを取ってみることにしました．


#環境
go version go1.6.2 linux/amd64
Python 2.7.12
grumpy 66c4b9413391faed2bf8bea92245b9349a4d15d1


Grumpyのインストールに関しては[Grumpy(Go running Python)を試してみた。](http://qiita.com/kmry2045/items/998250b3d430d82594c2)を参考



#モンテカルロ法による円周率の求解によるベンチマーク
##実験方法
プログラミングの教本でもよくある円周率のモンテカルロ法による計算をベンチにしました．
よい解説があったので引用で貼っておきます．
試行回数により，処理時間がどのように変化するかを観察します．

![image.png](https://qiita-image-store.s3.amazonaws.com/0/139643/c1cb55fc-9161-ca8d-e4fb-8fbc9dbb1da4.png)

引用：[モンテカルロ法と円周率の近似計算](http://mathtrain.jp/montecarlo)


##Pythonでの実装

```python:mote_py.py
#coding:utf-8
import random

if __name__=="__main__":
    num = int(raw_input())
    c = 0

    for i in xrange(num):
        x = random.random()
        y = random.random()

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

    print 4.0*c/num
```

##Goでの実装

```go:monte.go
package main

import (
	"fmt"
	"math/rand"
)

func main() {
	var num int
	fmt.Scan(&num)

	c := 0

	for i := 0; i < num; i++ {
		x := rand.Float64()
		y := rand.Float64()

		if x*x+y*y <= 1.0 {
			c++
		}
	}

	var p float64
	p = 4.0 * float64(c) / float64(num)

	fmt.Printf("%f\n", p)
}
```


##Grumpyでの実装

Grumpyの出力に関しては省略．300行程度のコードが出力されたため，省略．

```shell-session
$ ./grumpy/build/bin/grumpc mote_py.py > mote_py.py.go
$ go build mote_py.py.go
```


##結果
![image.png](https://qiita-image-store.s3.amazonaws.com/0/139643/85d6e5fc-9158-b263-e536-1bc1d3e4fbef.png)

|  試行回数  | Python[sec] | Grumpy[sec] |    Go[sec]  |
|------:|------:|-------:|-------:|
| 50000 | 0.070 |  2.180 |  0.000 |
|100000 | 0.130 |  6.550 |  0.020 |
|150000 | 0.170 |  8.520 |  0.030 |
|200000 | 0.210 | 10.750 |  0.030 |
|250000 | 0.240 | 14.340 |  0.020 |
|300000 | 0.370 | 26.140 |  0.050 |

**Go > Python >> Grumpy**

##考察

　一言で言うと意外だった．モンテカルロ計算は非常に負荷が高いため，スクリプト言語でやるものではない．そのため，GoとPythonであれば，圧倒的にGoのほうが速いだろう．という予測はあった．その中で，**Grumpyのコード生成が賢ければ，Goの速度に肉薄するだろう**という若干の期待があったため，非常に残念である．
　そのうえで，不可解な点もあり，それはGrumpyの処理時間が指数関数的に遅くなっている気がする．という点だ．このプログラムのコードを読むと分かるようにO(n)の計算量だ．しかし，Grumpyの処理時間を見てみると250,000を境に急激に処理時間がかかっている．そのため，何かしらインタプリタ側の処理に難があり，このように不可解な挙動をしているように思われる．


#竹内関数によるベンチマーク
##竹内関数とは

*竹内関数（たけうちかんすう）は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。*

![image.png](https://qiita-image-store.s3.amazonaws.com/0/139643/70d75c0e-7980-cb22-09f8-e67c0b0517f7.png)

参考：[竹内関数](https://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0)


##実験方法
Tarai(n,n-1,0)という形で竹内関数を呼び出し，nの大きさと処理時間にどのような変化があるのかを観察する．


##Pythonでの実装

```py:tarai_py.py
#coding:utf-8
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))

if __name__=="__main__":
    a,b,c = map(int,raw_input().split())
    print tak(a,b,c)
```

##Goでの実装

```go:tarai_go.go
package main

import (
	"fmt"
)

func tak(x int, y int, z int) int {
	if x <= y {
		return y
	} else {
		return tak(tak((x-1), y, z), tak((y-1), z, x), tak((z-1), x, y))
	}
}

func main() {
	var a int
	var b int
	var c int

	fmt.Scan(&a, &b, &c)
	fmt.Printf("%d\n", tak(a, b, c))
}
```

##Grumpyでの実装

```shell-session
$ ./grumpy/build/bin/grumpc tarai_py.py > tarai_py.go
$ go build tarai_py.go
```

Grumpyのコードは省略．


##結果
![image.png](https://qiita-image-store.s3.amazonaws.com/0/139643/a16d0766-bc2e-59fa-034a-e16aea8c8285.png)

| n  |  Python[sec] |  Grumpy[sec] |  Go[sec]   |
|:--:|--------:|--------:|------:|
| 10 |   0.220 |   0.380 | 0.000 |
| 11 |   0.960 |   2.230 | 0.030 |
| 12 |   6.960 |  14.580 | 0.150 |
| 13 |  42.500 | 106.380 | 0.970 |
| 14 | 290.060 | 688.670 | 6.190 |

**Go >> Python >> Grumpy**


##考察

　残念．という気持ちだった．これも前述した通り，GrumpyでPythonからGoに変換され，ビルドする際に推論が十二分に効くのではないか？と考えていた．そして，このような関数言語的なコードや，関数の呼び出しが非常にかかるコードは，ネイティブが有利だと思っていた．しかし，結果はGrumpyの大惨敗であった．


#感想

　自分自身の今までのプログラミングの中で，「Pythonで作る」「実行時間が足りない」「じゃあboost::pythonでネイティブ拡張書くか」みたいなことはありました．そのため，C++を使わねばならないことが割とありました．それがGrumpyでネイティブ拡張を書かなくてすら良い！であれば，使うのはやぶさかではないなぁ．と思っていました．しかし，この結果を見ると，もう少し使うのは待ったほうが良いのかなぁ．と思います．
　もしGrumpyでWebアプリを書いたとしても，今対応しているのはPython2.7系のみです．そのため，「今から新造するWebアプリに対して，2系はちょっと・・・」となると思います．私自身は2系のほうが長いので，そっちのほうがいいのですが，やっぱり3系に対応していただいたほうが，いろいろと幸せな未来になる気がします．
　こう見ると純粋なGrumpyの性能試験というと,Grumpyは歩が悪い気がします．どちらかというとGoの資産をPythonでBindできるトランスパイラの認識のほうが正しいと思います．
　また，世の中AltGo(Grumpyのようなスクリプト言語をGo言語に書き換える処理系)というものは作られるのでしょうか？やはりスクリプト言語の記述性は捨てきれないと感じていて，そのAltGo言語としてPythonは思想が合わない気がします．やはり，Googleの公式ブログでも「youtube.comにあるPython2.7資産のため」と書かれているので，そういうことも考えるとPython3対応って望み薄いのかもなぁ．と思った次第でした．