はじめに
Pythonのループが遅いという話があり、単純なループでざっくりベンチマークをしてみた。
環境
| 言語 | バージョン | 最適化オプション |
|---|---|---|
| Linux | 4.16.5-1-ARCH | - |
| CPU | Intel(R) Core(TM) i5-3570K CPU @ 3.40GHz | OC 4.2Ghz |
| Python | 3.6.5 | - |
| Ruby | 2.5.1p57 | - |
| gcc | 7.3.1 | -O0/-O2 |
| Go | go1.10.1 | - |
| Haskell(ghc) | 8.2.2 | -O2 |
総和ループでのベンチマーク
Python
a = 0
i = 0
while (i <= 100000000):
a = a + i
i = i + 1
print(a)
Ruby
a = 0
i = 0
while i <= 100000000 do
a = a + i
i = i + 1
end
print(a, "\n")
C
main () {
unsigned long a = 0;
unsigned long i = 0;
while (i <= 100000000) {
a = a + i;
i = i + 1;
}
printf("%ld\n", a);
}
Go
package main
import "fmt"
func main() {
a := 0
i := 0
for i <= 100000000 {
a = a + i
i = i + 1
}
fmt.Printf("%d\n", a)
}
Haskell(再帰)
loop :: Int -> Int
loop 0 = 0
loop n = n + loop (n-1)
main = do
let a = loop 100000000
print (a)
Haskell(foldl)
import Data.List
main = do
let a = foldl' (+) 0 [0..100000000]
print (a)
実行結果
| 言語 | 秒 |
|---|---|
| Python | 13.930 |
| Ruby | 2.004 |
| C(-O2) | 0.002 |
| C(-O0) | 0.196 |
| Go | 0.048 |
| Haskell(再帰) | 2.095 |
| Haskell(foldl) | 2.809 |
所感
- やはり、Pythonのループは遅かった。
- Rubyがかなり頑張っている。
- Haskell
の末尾再帰はRubyよりも遅いのか…。残念 orz
C++(clang++-6.0.0 -O2)では
になってた。
gccでも同様。
もはやループでも何でもない。
https://godbolt.org/g/rfzyW4
ということはC言語でもそうだろう。
https://wandbox.org/permlink/RYsU7PY6xYszGs0g
やはりな。
圧倒的なわけだ。
Haskell詳しくないけど末尾再帰になってない事だけは一目で分かる…
(参考)pythonistaがpythonっぽく書くと６倍速くらいにはなるよ！
Haskell のコードは末尾再帰になっていないように見えます。というか Haskell は
sumという総和を計算する関数が最初からあるのでそれを使うのが楽な方法だと思います。自分で書くのであればfold系の関数を使うか、累積変数を使って手で再帰を書くのがよさそうです。以下はそれぞれの方法でベンチマークを取ったものです。(gauge というベンチマークライブラリを使っています)。
sumなどの方が速いのが分かると思います。benchmarked sum/original time 236.9 ms (232.9 ms .. 242.9 ms) 0.999 R² (0.999 R² .. 1.000 R²) mean 243.2 ms (238.7 ms .. 252.1 ms) std dev 10.34 ms (4.500 ms .. 14.87 ms) benchmarked sum/sum time 2.854 ms (2.819 ms .. 2.894 ms) 0.998 R² (0.997 R² .. 0.999 R²) mean 2.888 ms (2.869 ms .. 2.920 ms) std dev 79.51 μs (57.09 μs .. 120.1 μs) variance introduced by outliers: 11% (moderately inflated) benchmarked sum/fold time 2.823 ms (2.793 ms .. 2.845 ms) 0.999 R² (0.998 R² .. 1.000 R²) mean 2.858 ms (2.840 ms .. 2.889 ms) std dev 81.81 μs (53.53 μs .. 124.3 μs) variance introduced by outliers: 11% (moderately inflated) benchmarked sum/original' time 5.697 ms (5.599 ms .. 5.813 ms) 0.996 R² (0.993 R² .. 0.999 R²) mean 5.848 ms (5.792 ms .. 5.935 ms) std dev 221.4 μs (155.0 μs .. 321.9 μs) variance introduced by outliers: 17% (moderately inflated)(追記: 結論は変わりませんがもう少しフェアな比較になるように修正)
(再追記: 結論は変わりませんがリストリテラルが間違っていたのを修正)
Haskell ですが，手元の環境だともとのままのコードでも Python の400倍（Python で変数を関数内に入れると150倍）， Ruby の 50 倍程度の速度が出ています．最適化オプションを渡すのをお忘れでないでしょうか (このコメントについては手元で大きなミスをしていたので完全に撤回します．申し訳ありませんでした．（GHCのバージョンが云々一瞬書いていましたがそれも間違い，大きくは関係ないです）ghc -O2 a.hs)．しれっと更新されてるけど C が -O0 でコンパイルされてて悲しくなる…。
-O2 の最適化で定数に展開されてしまうのは、それこそが gcc や clang の能力なのであって結果が間違ってる訳では全くないのです。
要するに、こんな単純なベンチマークでインタプリタとコンパイラを比較する事自体がナンセンスだったという事でしょう。
みなさま、コメントありがとうございます。
@_EnumHack
そこまで最適化されるとは考慮不足でした。-O0の測定を追加しました。
@chuntaro
末尾再帰は、ご指摘の通りなので訂正しました。
また、コンパイラ系と単純比較するのが間違っているのはご指摘の通りではありますが、「Pythonの単純ループが遅い」が主眼だったので、Cも載せるとしたら、敢えて-O0でまともにループさせる方が適切と考えました。とは言え、-O2もないとCが遅いと誤解を生むので併記にします。
@syocy
そもそもHaskellを載せるべきかもありますが、単なる興味で載せました。同様のコード(ループの比較を主眼とする)なら、確かに、foldlの方が適切と思いました。追加しました。が、自分の環境だと何故か余計に遅くなりました…。
ループの速度を測るのがテーマだと思いますが，部分和が途中で231 を超えるので，ここから先が多倍長になるようなシステムでは多倍長整数の加算の性能が大きく効いてきます。
つまり，ループを測定しているのか多倍長整数演算を測定しているのか分からなくなってくる可能性があるように思います。
余談ですが，Ruby 2.6.0-preview1 ではもう少し（数%か 1 割程度）速いようです。