HOME Sather を試そう 書き込む

1. Sather vs C++: 実行速度の比較

1. Sather は本当に C++ より速いのか？

Wikipedia をみると "Sather で書かれたプログラムはしばしば C++ で書かれたものよりも早く実行される" と書いてありました。本当か？と思って簡単なプログラムを書いて試してみることにしました。 Sather と C++ の特徴が出て、かつ、 単純で処理時間が長いプログラムということで素数の数を数え上げる簡単なプログラムを書いて試してみました。 見つかった素数はリストに保持していきます。

2. C++ で書くと

まず、C++ で書くと [code 1] のようになります。vector<int> を使って見つかった素数をリストに加えていきます。 それほど C++ の特徴を生かした例ではないのですが、vector クラスを使ったということで良しとしましょう。 
01:     // g++ -O2 nprime.cpp -o nprime_cpp
02:     #include <iostream>
03:     #include <vector>        // 指摘により list &rarr vector に書き換える
04:     
05:     #define W 500
06:     
07:     using namespace std;
08:     
09:     
10:     inline bool primep(vector<int>& plist, int i){             // 指摘により参照渡しにする
11:       for( vector<int>::iterator iter = plist.begin();iter != plist.end(); iter++){
12:         int j = *iter;
13:         if(j*j>i) return true;
14:         if(i%j==0) return false;
15:       }
16:     }
17:     
18:     void nprime(int m){
19:       vector<int> plist;
20:       plist.push_back(2);
21:       plist.push_back(3);
22:       for(int j =5, r=3; j <= m; j+=2, r++){
23:         if(primep(plist, j)) plist.push_back(j);
24:         if(r==W){
25:           cout << j << " " << plist.size() << "\n";
26:           r = 0;
27:         }
28:       }
29:     }
30:     
31:     int main(int ac, char** av){
32:       if(ac ==2){
33:         int m = atoi(av[1]);
34:         if(m > 10000){
35:           cout << "#Limit, N of primes\n0 0\n";
36:           nprime(m);
37:           return 0;
38:         }else{
39:           cerr << "limit should be > 10000\n";
40:         }
41:       }else{
42:         cerr << "Usage: nprime_cpp N\n";
43:       }
44:     }

簡単な説明

  1. inline bool primep(vector<int>& plist, int i):
    i が素数なら真を返します。高速化のため inline 宣言しています。 i が plist にある今まで見つかった素数で割り切れるか調べています。
  2. void nprime(int m):
    素数が見つかるとそれを plist に加えていきます。また、 0 から m までの素数の数を 1000 ごとに標準出力に吐き出します。
  3. int main(int ac, char** av):
    引数をチェックして、問題が無ければ nprime を呼び出します。
このプログラムは 0 から N (av[1]) までの素数の数を 1000 ごとに標準出力に出力します。 コンパイルして 10000000 までの素数の数を求めてみました。 
$ g++ -O2 nprime.cpp -o nprime_cpp

$ time ./nprime_cpp 10000000 > nprime_cpp.dat

real    0m8.365s
user    0m8.245s
sys     0m0.004s
8.365 秒で終わりました。やはり早いです。

3. Sather で書くと

次に、同じプログラムを Sather で書いてみました [code 2]。 繰り返しのやり方が特徴的でイテレーターを使っています。elt! や step! などのイテレータを使うと while! を使ったときより処理時間が短くなるようです。 
01:     -- primitive couting prime numbers program
02:     -- sacomp -O_fast nprime.sa -o nprime_sa
03:     
04:     class MAIN is
05:        attr plist :LIST{INT}; 
06:        const w:INT := 500;
07:     
08:        private primep(i:INT):BOOL is
09:           j:INT;
10:           
11:           loop 
12:     	 j :=self.plist.elt!;
13:     	 if j * j > i then
14:     	    return true;
15:     	 end;
16:     	 if i % j = 0 then
17:     	    return false;
18:     	 end;
19:           end;
20:        end;
21:     
22:     
23:        nprime(maxi:INT) is
24:           j,r:INT;
25:           self.plist := #(|2,3|);
26:           r := 3;
27:           loop
28:     	 j := 5.step!((maxi-3)/2, 2);
29:     	 if self.primep(j) then
30:     	    self.plist.append(j);
31:     	 end;
32:     	 if r = w then
33:     	    #OUT + j + " " + self.plist.size + "\n";
34:     	    r := 0;
35:     	 end;
36:     	 r := r+1;
37:           end;
38:        end;
39:        
40:        main(av:ARRAY{STR}) is
41:           if av.size = 2 then
42:     	 m:INT := av[1].cursor.get_int;
43:     	 if m <= 10000 then
44:     	    #ERR + "limit should be > 10000\n";
45:     	 else
46:     	    #OUT +"# limit, N of primes\n0 0\n";
47:     	    nprime(m);
48:     	 end;
49:           else
50:     	 #ERR + "Usage: nprime N\n"
51:           end;
52:        end;
53:     end;
やっていることは C++ で書いたものと同じです。C++ のと Sather のを比べてみてください。 
$sacomp -O_fast nprime.sa -o nprime_sa
$time nprime_sa 10000000 > nrpime_sa.dat

real    0m14.262s
user    0m11.617s
sys     0m0.016s
14.262 秒かかりました。このような単純なプログラムではやはり C++ より少し遅いようです。 しかしもちろん Python や Scheme よりは圧倒的に早いので Sather は 簡単に高速なプログラムが書ける 魅力的な言語だといえます。 そして、もし速度をもっと向上させたければ C や Fortran とのインターフェースを利用することができます。


図 1. 素数の数

素数の密度は数が大きくなっていくと徐々に減少していくことがわかります。

4. Sather を使ってみよう！

紫藤はこの結果をみて Sather を勉強しようと思いました。高速なプログラムをきわめて簡単に書くことができます。 ちゃんと書かれた C++ の方が早かったのですが、C++ はちょっとしたミスでものすごく遅いプログラムになってしまいます。 実行速度が気にならないプログラムであれば Python や Scheme で書くのが簡単ですが、実行速度が問題になる プログラムを書くときはこれからは Sather を使おうと思います。 このプログラムの可読性は Sather, C++, C ともそんなに変わりませんが、大きなプログラムになると 圧倒的に Sather の方が読みやすくなります。

なぜ Sather が普及しないのか不思議です。

HOME Sather を試そう 書き込む