2012/07/05
2012/07/08 LuaJIT を追加
2012/08/06 修正と「PyPy が CPython よりも遅くなるケース」を追加
Python のようなスクリプト言語を使っていると、実行時間が気になる。スクリプト言語が苦手な典型的な処理は、大きな文字列の先頭から1Byte づつ順に読み取り、何かを行うケースであろう。Python もそうであるが、そのような処理のために多数のモジュールを持っている。それらは C で書かれ、実行速度を稼ぐのである。しかし、それは決して褒められたものではない。シンプルさの代償として、ライブラリの山ができ、ライブラリの使い方を学ぶために多くの時間が取られる。そこで今回は、この問題にメスを入れてみる事にした。
目標とする処理の内容は、ファイルを読み取り(内容は何でもよい)、文字(内部コード)の出現頻度を調べる。ファイルとしては、適度に大きいものとして
-rw-r--r--@ 1 arisawa staff 18632739 3 24 13:47 python-2.7.2-macosx10.6.dmgを選んだ。また、言語としては、Python の他、Lua、C、Go を選び、処理速度を比較した。
Python に関しては、オーソドックスな CPython と、驚異的に速いらしい PyPy を選んだ。Python のプログラムに関しては、array と list を使った場合を比較した。
測定に使ったのは3年程前に買った旧い mac book (2009 early model) で、spec は
比較した処理系(CPython,PyPy,Lua,LuaJIT,C,Go)はいずれも x86_64 である。
以下にファイルを読み取り、文字の出現数を調べる Python のプログラムを2つ載せる。出現数をカウントするために、図1は array を使っているが、図2はlistを使っている。
array の方が速いに決まっていると予想していたのだが.... 結果は恐るべし!
import sys
import array
a=array.array("L",[0]*256)
f=open(sys.argv[1])
s=f.read()
f.close()
for c in s:
a[ord(c)] += 1
print " ",
for n in range(0,8):
print "%8x"%n,
for n in range(0,256):
if n%8 == 0:
print "\n%02x "%n,
print "%8d"%a[n],
import sys
a=[0]*256
f=open(sys.argv[1])
s=f.read()
f.close()
for c in s:
a[ord(c)] += 1
print " ",
for n in range(0,8):
print "%8x"%n,
for n in range(0,256):
if n%8 == 0:
print "\n%02x "%n,
print "%8d"%a[n],
注意: 図1も図2も、文字数の出現頻度を数えるだけであれば、他の書き方もあり、その方が実行速度が速いかも知れない。しかし、ここでの関心は、スクリプト言語が最も苦手とする問題に、特別のモジュールを使わないで、率直にプログラムを組んだ場合に、Python がどの程度の処理速度を発揮するか調べる事にあるのである。
今回は、Python2.7.2 のソースをコンパイルしたものを使った。2割程スピードがアップしている。
コンパイルの最適化レベルは O2 で、これは配布ソフトの最適化レベルのままである。
Python 2.7.2
bash$ time /usr/local/bin/python a.py python-2.7.2-macosx10.6.dmg
0 1 2 3 4 5 6 7
00 66653 67346 67418 69799 66925 69784 70146 71458
08 67407 80633 72830 71149 71158 71124 71770 73650
10 66896 68689 68613 69894 70747 70652 71337 73053
18 72673 70405 71814 72530 71852 72211 72980 75130
20 66909 67237 68821 69987 69734 70771 70362 72495
28 70568 71221 70360 73032 72100 71956 71607 93261
30 73544 72957 72055 72936 73819 71516 72788 75220
38 74684 74028 72622 72245 74430 72366 73684 77671
40 67219 82422 69885 72028 70245 73626 73936 73844
48 69711 72752 71678 73194 72066 72696 74030 75114
50 70049 72705 71155 72074 70736 72263 72141 73896
58 72266 73688 72978 72209 71162 71855 73690 76229
60 69691 74315 72482 73284 72292 73183 72350 75503
68 73348 72662 71966 73501 72672 72370 74052 77210
70 73396 73908 73195 73131 75258 72934 73743 76479
78 77106 74422 75019 73965 75831 73997 76505 80692
80 67532 70120 68656 72038 69480 71056 71957 73931
88 68889 70459 71781 73410 73068 72904 73201 74347
90 67323 70667 70957 72673 70270 70265 72032 73151
98 70207 70346 70605 72861 71676 72719 74180 75513
a0 68983 70840 71241 74152 69634 71798 70759 74098
a8 68817 70196 69716 72482 70861 71795 72118 75095
b0 69926 70872 71422 73813 71272 71633 71386 74337
b8 70618 71998 72295 73883 73767 74349 75533 79899
c0 70653 71409 72292 75925 69993 73313 73151 75471
c8 70567 72896 71202 73507 70963 72755 73476 76455
d0 72019 74187 70639 73995 69845 71387 71763 74109
d8 70748 73147 70816 73248 71868 74317 74463 79455
e0 72283 76130 72713 76637 72169 73049 72109 76233
e8 73874 73413 71118 74282 72129 73553 73409 78307
f0 76172 76874 73758 76142 74515 73917 73188 77325
f8 78997 75855 75017 76824 78946 78588 80770 86831
real 0m11.193s
user 0m11.053s
sys 0m0.068s
bash$
bash$ time /usr/local/bin/python a1.py python-2.7.2-macosx10.6.dmg [中略] real 0m7.395s user 0m7.316s sys 0m0.059s bash$
なんと、list を使った方が速い。list は array に比べて柔軟な構造で、いろいろな意味でデータへの間接参照が発生し、速度を落とすと考えられるのに、どうして???
次に、高速の誉れ高い PyPy である。
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:42:54)
[PyPy 1.9.0 with GCC 4.2.1] on darwin
bash$ time pypy a.py python-2.7.2-macosx10.6.dmg
0 1 2 3 4 5 6 7
00 66653 67346 67418 69799 66925 69784 70146 71458
08 67407 80633 72830 71149 71158 71124 71770 73650
10 66896 68689 68613 69894 70747 70652 71337 73053
18 72673 70405 71814 72530 71852 72211 72980 75130
20 66909 67237 68821 69987 69734 70771 70362 72495
28 70568 71221 70360 73032 72100 71956 71607 93261
30 73544 72957 72055 72936 73819 71516 72788 75220
38 74684 74028 72622 72245 74430 72366 73684 77671
40 67219 82422 69885 72028 70245 73626 73936 73844
48 69711 72752 71678 73194 72066 72696 74030 75114
50 70049 72705 71155 72074 70736 72263 72141 73896
58 72266 73688 72978 72209 71162 71855 73690 76229
60 69691 74315 72482 73284 72292 73183 72350 75503
68 73348 72662 71966 73501 72672 72370 74052 77210
70 73396 73908 73195 73131 75258 72934 73743 76479
78 77106 74422 75019 73965 75831 73997 76505 80692
80 67532 70120 68656 72038 69480 71056 71957 73931
88 68889 70459 71781 73410 73068 72904 73201 74347
90 67323 70667 70957 72673 70270 70265 72032 73151
98 70207 70346 70605 72861 71676 72719 74180 75513
a0 68983 70840 71241 74152 69634 71798 70759 74098
a8 68817 70196 69716 72482 70861 71795 72118 75095
b0 69926 70872 71422 73813 71272 71633 71386 74337
b8 70618 71998 72295 73883 73767 74349 75533 79899
c0 70653 71409 72292 75925 69993 73313 73151 75471
c8 70567 72896 71202 73507 70963 72755 73476 76455
d0 72019 74187 70639 73995 69845 71387 71763 74109
d8 70748 73147 70816 73248 71868 74317 74463 79455
e0 72283 76130 72713 76637 72169 73049 72109 76233
e8 73874 73413 71118 74282 72129 73553 73409 78307
f0 76172 76874 73758 76142 74515 73917 73188 77325
f8 78997 75855 75017 76824 78946 78588 80770 86831
real 0m5.033s
user 0m4.887s
sys 0m0.073s
bash$
array を使った場合には CPython よりも 3倍程度速い。ネットの記事では、もっともっと速い(C並み)との話もあるが、冗談でしょうね。
次は list を使った結果である。
bash$ time pypy a1.py python-2.7.2-macosx10.6.dmg [中略] real 0m0.767s user 0m0.700s sys 0m0.063s
しかし、array ではなく、list を使ったものは圧倒的に速い! どうして???
今回の結果を見ると PyPy でモジュールを呼び出した場合に、そのモジュールに対して PyPy による最適化が行われていないのではないかと疑われる。
後に、C の結果も示すが、PyPy であれば、C に比べて、4倍程度時間がかかるだけである。この程度を覚悟できれば、スクリプト言語にとって最も苦手な処理も、Python で書いても良いかも知れない。
PyPy が常に良い結果をもたらすかと言えば、そうでもないことが、次の結果から分かる。
このプログラムはフィボナッチ数列を 20000 項計算する。計算時間を食っているのは、大きな整数の和である。もちろん、この部分は C で直接書かれているはずで、PyPy によるスピードアップは期待できない。
x=1
y=1
for n in range(1,20000):
z=x+y
print n,x,y,z
x=y
y=z
実行結果は....
-bash$ time /usr/local/bin/python b.py>/dev/null real 0m16.949s user 0m16.794s sys 0m0.039s -bash$ time pypy b.py>/dev/null real 1m19.904s user 1m18.343s sys 0m0.217s
うーむ。この結果を見ると首を傾げたくなる。この PyPy は Python 2.7.2 とリンクしているのだが、x64 版とリンクしているのだろうか?
ちなみに、32bit 版の Python2.7.2 では
real 0m46.452s user 0m46.238s sys 0m0.071sである。
Lua はシンプルな言語であり、僕の好きな言語でもある。Python と違って、Lua は厳選されたメニューしか提供しない。そのことで、意外とプログラムしやすいのである。
ここでは、普通の Lua と、JIT を使った LuaJIT を試す。LuaJIT の開発バーションは、現在 2.0.0-beta であり、64bit 化されている。(stable 版の1.1.8 は64bitではない) 結果は、以下に見るように、Lua は list を使った CPython とほぼ互角である。LuaJIT-2.0.0-beta10 は PyPy と互角以上の速度が出ている。
-bash$ which lua
/usr/local/bin/lua
-bash$ file /usr/local/bin/lua
/usr/local/bin/lua: Mach-O 64-bit executable x86_64
Lua 5.2.0 Copyright (C) 1994-2011 Lua.org, PUC-Rio
function printf(fmt,...)
io.write(string.format(fmt,...))
end
a={}
for n=0, 255 do
a[n]=0
end
f=io.open(arg[1])
s=f:read("*a")
f:close()
for n=1,#s do
b=string.byte(s,n)
a[b] = a[b] + 1
end
printf(" ")
for n=0,7 do
printf("%8x",n)
end
for n=0,255 do
if n%8 == 0 then
printf("\n%02x ",n)
end
printf("%8d",a[n])
end
bash$ time lua a.lua python-2.7.2-macosx10.6.dmg
0 1 2 3 4 5 6 7
00 66653 67346 67418 69799 66925 69784 70146 71458
08 67407 80633 72830 71149 71158 71124 71770 73650
10 66896 68689 68613 69894 70747 70652 71337 73053
18 72673 70405 71814 72530 71852 72211 72980 75130
20 66909 67237 68821 69987 69734 70771 70362 72495
28 70568 71221 70360 73032 72100 71956 71607 93261
30 73544 72957 72055 72936 73819 71516 72788 75220
38 74684 74028 72622 72245 74430 72366 73684 77671
40 67219 82422 69885 72028 70245 73626 73936 73844
48 69711 72752 71678 73194 72066 72696 74030 75114
50 70049 72705 71155 72074 70736 72263 72141 73896
58 72266 73688 72978 72209 71162 71855 73690 76229
60 69691 74315 72482 73284 72292 73183 72350 75503
68 73348 72662 71966 73501 72672 72370 74052 77210
70 73396 73908 73195 73131 75258 72934 73743 76479
78 77106 74422 75019 73965 75831 73997 76505 80692
80 67532 70120 68656 72038 69480 71056 71957 73931
88 68889 70459 71781 73410 73068 72904 73201 74347
90 67323 70667 70957 72673 70270 70265 72032 73151
98 70207 70346 70605 72861 71676 72719 74180 75513
a0 68983 70840 71241 74152 69634 71798 70759 74098
a8 68817 70196 69716 72482 70861 71795 72118 75095
b0 69926 70872 71422 73813 71272 71633 71386 74337
b8 70618 71998 72295 73883 73767 74349 75533 79899
c0 70653 71409 72292 75925 69993 73313 73151 75471
c8 70567 72896 71202 73507 70963 72755 73476 76455
d0 72019 74187 70639 73995 69845 71387 71763 74109
d8 70748 73147 70816 73248 71868 74317 74463 79455
e0 72283 76130 72713 76637 72169 73049 72109 76233
e8 73874 73413 71118 74282 72129 73553 73409 78307
f0 76172 76874 73758 76142 74515 73917 73188 77325
f8 78997 75855 75017 76824 78946 78588 80770 86831
real 0m9.372s
user 0m9.266s
sys 0m0.092s
bash$
LuaJIT はどうやら 2.0.0 で x86_64 対応になったらしい。(安定版の 1.1.8 はまだx86_64 に対応していない)
-bash$ time luajit-2.0.0-beta10 a.lua python-2.7.2-macosx10.6.dmg [中略] real 0m0.505s user 0m0.312s sys 0m0.190s -bash$
なお LuaJIT 1.1.8 だと
-bash$ time luajit a.lua python-2.7.2-macosx10.6.dmg [中略} real 0m5.603s user 0m5.434s sys 0m0.157s -bash$で、10倍程の時間がかかっている。
なお、LuaJIT は PyPy に比べて非常に小さい。何と 1/100 しかない! ローディグタイムが気になる場合には、LuaJIT は圧倒的に有利である。
-bash$ ls -l /usr/local/bin/lua* -rwxr-xr-x 1 root wheel 218608 4 28 12:15 /usr/local/bin/lua -rwxr-xr-x 1 root wheel 147616 4 28 12:15 /usr/local/bin/luac -rwxr-xr-x 1 root wheel 217236 7 8 20:13 /usr/local/bin/luajit -rwxr-xr-x 1 root wheel 420608 7 8 21:01 /usr/local/bin/luajit-2.0.0-beta10 -bash$ ls -l /usr/local/bin/pypy lrwxr-xr-x 1 root wheel 28 6 20 21:06 /usr/local/bin/pypy -> /usr/local/pypy-1.9/bin/pypy -bash$ ls -l /usr/local/pypy-1.9/bin/pypy -rwx------@ 1 arisawa staff 41589912 6 8 06:44 /usr/local/pypy-1.9/bin/pypy
C はもちろん最速である。コンパイルは特に最適化していない。オプション無し。
i686-apple-darwin10-gcc-4.2.1
#include <stdio.h>
int a[256];
int main(int argc, char *argv[]){
FILE *fp;
int c,n;
fp = fopen(argv[1],"r");
while((c = fgetc(fp)) != EOF)
a[c] += 1;
printf(" ");
for(n=0; n < 8; n++)
printf("%8x",n);
for(n=0; n < 256; n++){
if(n%8 == 0)
printf("\n%02x ",n);
printf("%8d",a[n]);
}
}
bash$ time a.out python-2.7.2-macosx10.6.dmg
0 1 2 3 4 5 6 7
00 66653 67346 67418 69799 66925 69784 70146 71458
08 67407 80633 72830 71149 71158 71124 71770 73650
10 66896 68689 68613 69894 70747 70652 71337 73053
18 72673 70405 71814 72530 71852 72211 72980 75130
20 66909 67237 68821 69987 69734 70771 70362 72495
28 70568 71221 70360 73032 72100 71956 71607 93261
30 73544 72957 72055 72936 73819 71516 72788 75220
38 74684 74028 72622 72245 74430 72366 73684 77671
40 67219 82422 69885 72028 70245 73626 73936 73844
48 69711 72752 71678 73194 72066 72696 74030 75114
50 70049 72705 71155 72074 70736 72263 72141 73896
58 72266 73688 72978 72209 71162 71855 73690 76229
60 69691 74315 72482 73284 72292 73183 72350 75503
68 73348 72662 71966 73501 72672 72370 74052 77210
70 73396 73908 73195 73131 75258 72934 73743 76479
78 77106 74422 75019 73965 75831 73997 76505 80692
80 67532 70120 68656 72038 69480 71056 71957 73931
88 68889 70459 71781 73410 73068 72904 73201 74347
90 67323 70667 70957 72673 70270 70265 72032 73151
98 70207 70346 70605 72861 71676 72719 74180 75513
a0 68983 70840 71241 74152 69634 71798 70759 74098
a8 68817 70196 69716 72482 70861 71795 72118 75095
b0 69926 70872 71422 73813 71272 71633 71386 74337
b8 70618 71998 72295 73883 73767 74349 75533 79899
c0 70653 71409 72292 75925 69993 73313 73151 75471
c8 70567 72896 71202 73507 70963 72755 73476 76455
d0 72019 74187 70639 73995 69845 71387 71763 74109
d8 70748 73147 70816 73248 71868 74317 74463 79455
e0 72283 76130 72713 76637 72169 73049 72109 76233
e8 73874 73413 71118 74282 72129 73553 73409 78307
f0 76172 76874 73758 76142 74515 73917 73188 77325
f8 78997 75855 75017 76824 78946 78588 80770 86831
real 0m0.208s
user 0m0.187s
sys 0m0.019s
bash$
やはり、格が違うと言わなくてはならない。
Go lang は現在注目を浴びているプログラミング言語で、この3月に第1版がリリースされた。Go を試用してみると、C++ の役割は終わったと感じる。Go に賛同する多数のプログラマの協力で、現時点でも Go で書かれた多数のライブラリが揃っている。ライブラリは、まだまだ増えて行くだろう。
(Go は初心者には取っ付きにくいかもしれない。メニューがありすぎで.... 何を使ったら良いか... と悩むのではないか?)
go version go1.0.1
package main
import (
"os"
"bufio"
"fmt"
"io"
)
func main(){
a := [256] uint {}
file,_ := os.Open(os.Args[1])
rd := bufio.NewReader(file)
for b,err := rd.ReadByte(); err != io.EOF; {
a[b] += 1
b,err = rd.ReadByte()
}
fmt.Printf(" ")
for n:=0; n < 8; n++ {
fmt.Printf("%8x",n)
}
for n:=0; n < 256; n++{
if n%8 == 0 {
fmt.Printf("\n%02x ",n)
}
fmt.Printf("%8d",a[n])
}
}
bash$ time a python-2.7.2-macosx10.6.dmg
0 1 2 3 4 5 6 7
00 66653 67346 67418 69799 66925 69784 70146 71458
08 67407 80633 72830 71149 71158 71124 71770 73650
10 66896 68689 68613 69894 70747 70652 71337 73053
18 72673 70405 71814 72530 71852 72211 72980 75130
20 66909 67237 68821 69987 69734 70771 70362 72495
28 70568 71221 70360 73032 72100 71956 71607 93261
30 73544 72957 72055 72936 73819 71516 72788 75220
38 74684 74028 72622 72245 74430 72366 73684 77671
40 67219 82422 69885 72028 70245 73626 73936 73844
48 69711 72752 71678 73194 72066 72696 74030 75114
50 70049 72705 71155 72074 70736 72263 72141 73896
58 72266 73688 72978 72209 71162 71855 73690 76229
60 69691 74315 72482 73284 72292 73183 72350 75503
68 73348 72662 71966 73501 72672 72370 74052 77210
70 73396 73908 73195 73131 75258 72934 73743 76479
78 77106 74422 75019 73965 75831 73997 76505 80692
80 67532 70120 68656 72038 69480 71056 71957 73931
88 68889 70459 71781 73410 73068 72904 73201 74347
90 67323 70667 70957 72673 70270 70265 72032 73151
98 70207 70346 70605 72861 71676 72719 74180 75513
a0 68983 70840 71241 74152 69634 71798 70759 74098
a8 68817 70196 69716 72482 70861 71795 72118 75095
b0 69926 70872 71422 73813 71272 71633 71386 74337
b8 70618 71998 72295 73883 73767 74349 75533 79899
c0 70653 71409 72292 75925 69993 73313 73151 75471
c8 70567 72896 71202 73507 70963 72755 73476 76455
d0 72019 74187 70639 73995 69845 71387 71763 74109
d8 70748 73147 70816 73248 71868 74317 74463 79455
e0 72283 76130 72713 76637 72169 73049 72109 76233
e8 73874 73413 71118 74282 72129 73553 73409 78307
f0 76172 76874 73758 76142 74515 73917 73188 77325
f8 78997 75855 75017 76824 78946 78588 80770 86831
real 0m0.261s
user 0m0.237s
sys 0m0.021s
C より幾分遅いが、現在の Go は実行効率を上げるためにチューニングをする時期ではない。それでも、これだけの実行速度が得られれば、C から Go にスイッチしてもよいかも知れない。