2009年12月

valgrind --tool=cachegrind でキャシュミスを調べようと思ってプログラムを走らせたのだが…　計算が終了する気配が無い．データサイズ小さくすりゃ速くなるだろうけど，そしたらデータがキャッシュ乗り切ってしまうので本末転倒．

まあ，キャッシュ効きまくり状態でも50秒かかるのだからシミュレーションでキャッシュの計測とかしてたらなかなか終わらんか．うーん，この実験を繰り返すのは苦痛だなぁ．

ということで，せっかくGoを勉強したのでゴルフ場で（頭と指の）運動をしてみた．

大人気なく問題を解きまくってGoで解いた人ランキング一位になった．

以下，ショートコーディングのための技術．

• Raw String Literal を使うべし． 特に，改行にエスケープがいらないため，

  s:="hoge\nhuga"

  が

  s:=`hoge
  huga`

  でいいので1Bの短縮．他にもバイナリデータを文字列として埋め込んでしまうという…

• 外部パッケージをローカルの名前空間に展開すべし．
  インポート時の束縛名にドットを使うと，他パッケージの関数などをローカルの名前空間に展開出来る．なので，

  import"fmt"func m(){fmt.Print(“c")}

  が

  import."fmt"func m(){Print(“c")}

  に短縮できる．複数のパッケージをローカルに展開できるが，同一名があると衝突するので，解決に短い名前を付ける必要がある．ついでにインポートのファイル名の後には空白がいらないという…

• 関数変数を使うべし．
  関数も変数に入れられる．なので，

  x:=Sprintf("%c",c);y:=Sprintf("%c",d);

  が

  f=Sprintf;x:=f("%c",c);y:=f("%c",d);

  に短縮できる．でもprintlnとかの特別な関数は束縛出来ないという…

• 依存の無い（初期値）代入はまとめるべし．
  変数への値代入は，型に関係なくカンマでつないで一気に書ける．なので，

  x:=1;ｙ:="str";z:=2

  が

  x,y,z:=1,"str",2

  に短縮できる．でも，複数の値を返す式が右辺にあると怒られるという…　（複数値のコンテキストのネストが出来ないらしい） ついでに，複数値の代入文は右辺が全て評価されてから左辺へと代入されるので，

  t:=x;x=y;y=t

  変数のスワップなどは複数値の代入を使って

  x,y=y,x

  のように短く書ける．

• Sliceは上手に作るべし．
  Sliceの生成にはmakeを使う方法とcomposite literalを使う方法がある．なので，小さなsliceをつくるなら

  b:=make([]byte,1)

  でなく

  b:=[]byte{1}

  にする．また，大きなsliceも

  b:=make([]byte,10000)

  でなく

  b:=make([]byte,1e4)

  にする．

そして微妙な謎は，手元のコンパイラではプログラムの最後に改行が必須だったりブロックの閉じカッコの直後に文を書くにはセミコロンが間に必須だったりするのだけど…　ゴルフ場だと必要ないらしい．ちょっと手元でプログラム書くときに気を使う．

それにしても全体的に短く出来ない言語だなぁという感想．入出力が一苦労だったりするし．もう少し入力を簡単に取れると良いのだけど…　現状では必ず[]byteを介さねばならないのでメンド臭い＆長すぎる．

並列に動くっぽいけど本当にそうなのか気になったので，色々書けるようにと勉強してみた．

セミコロン少なめだし，カッコ少なめだし，型を書くのも少なめだし，タプルあるし，型システム単純だし，例外ないし，オーバーロードないし，generics 入ってないし，GCだし，メソッド定義にはレシーバ書くし，継承ないし，interface とかメソッドさえ揃っていれば継承したことになるし，embedded types とか楽すぎだし，宣言したのに使ってない変数があるとコンパイルしてくれないし，スコープ上書きしたときに何も言ってくれないし，速度も十分速いし．スクリプト言語の気分で速いプログラムが書けるような気がする．一方で，generic types がないので高レベルな汎用ルーチンが書きづらい．

で，そんなことはさておきとりあえずベンチマークということで，n-queen問題のプログラムを書いてみた：

package main
import ("fmt"; "flag")
 
func nqueen(n, i, u, l, r int) int {
  if i==n { return 1 } 
  nl := (l << 1) | 1;
  nr := ((r|(1<<uint(n))) >> 1);
  ni := i + 1;
  p := u & nl & nr;
  c := 0;
  for p!=0 {
    lb := (-p) & p;
    p ^= lb;
    c += nqueen(n, ni, u ^ lb, nl ^ lb, nr ^ lb)
  }
  return c
}
 
type State struct { n, i, u, l, r int }
func nqueenRes(ch chan int, n, i, u, l, r int) { 
  ch <- nqueen(n, i, u, l, r)
 }
 
func gentasks(cs *[] chan int, lim, n, i, u, l, r int) {
  if i==lim {
    lx := len(*cs);
    *cs = (*cs)[0:lx+1];
    (*cs)[lx] = make (chan int);
    go nqueenRes((*cs)[lx], n, i, u, l, r);    
    return;
  }
  nl := (l << 1) | 1;
  nr := ((r|(1<<uint(n))) >> 1);
  ni := i + 1;
  p := u & nl & nr;
  for p!=0 {
    lb := (-p) & p;
    p ^= lb;
    gentasks(cs, lim, n, ni, u ^ lb, nl ^ lb, nr ^ lb)
  }
}
 
func nqueensGo(n int) int {
  b := (1<<uint(n)) - 1;
  cs := make( [] chan int, 0, n * n * n);
  gentasks(&cs, 3, n, 0, b, b, b);
 
  sum := 0;
  for _, c := range cs { sum += <- c }
 
  return sum;
}
 
var n = flag.Int("n", 16, "n")
 
func main() {
  flag.Parse();
  fmt.Println(nqueensGo(*n));
}

ついでに比較対象のC++プログラム（OpenMP使用）：

#include<iostream>
#include<vector>
#include<omp.h>
#include<stdlib.h>
 
using namespace std;
 
int nqueen(int n, int i, int u, int l, int r) 
{
  if(i==n) return 1; 
  const int nl = (l << 1) | 1;
  const int nr = ((r|(1<<n)) >> 1);
  const int ni = i + 1;
  int p = u & nl & nr;
  int c = 0;
  while(p!=0) {
    const int lb = (-p)&p;
    p ^= lb;
    c += nqueen(n, ni, u ^ lb, nl ^ lb, nr ^ lb);
  }
  return c;
}
struct state {
  int n, i, u, l, r;
  state(int n, int i, int u, int l, int r) : n(n), i(i), u(u), l(l), r(r) {}
};
int nqueen_res(const state &st) { return nqueen(st.n, st.i, st.u, st.l, st.r); }
 
void gentasks(vector<state> &xs, int lim, int n, int i, int u, int l, int r) 
{
  if(i==lim) {
    xs.push_back(state(n, i, u, l, r));
    return;
  }
  const int nl = (l << 1) | 1;
  const int nr = ((r|(1<<n)) >> 1);
  const int ni = i + 1;
  int p = u & nl & nr;
  int c = 0;
  while(p!=0) {
    const int lb = (-p)&p;
    p ^= lb;
    gentasks(xs, lim, n, ni, u ^ lb, nl ^ lb, nr ^ lb);
  }
}
 
int nqueensOMP(int n)
{
  int b = (1<<n) - 1;
  vector<state> xs;
  gentasks(xs, 3, n, 0, b, b, b);
 
  int nx = xs.size();
  int sum = 0;
#pragma omp parallel for reduction(+:sum)
  for(int i = 0; i < nx; i++) {
    sum = sum + nqueen_res(xs[i]);
  }
  return sum;
 
}
 
int main(int argc, char *argv[])
{
  int n = argc > 1 ? atoi(argv[1]) : 16;
  int c = nqueensOMP(n);
  std::cout << n << " " << c << std::endl;
  return 0;
}

---

とりあえず実験結果．OpenMPのスケジューリングを変更して性能を改善したものの結果は下のほう．

8コアのマシン(Xeon E5430 @ 2.66GHz x2)での実験結果（n=1７）．C++ はg++4.5.0 (exeperimental) に -O3，Go は 6g/6l でコンパイル．OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定．speedup は C++ の１スレッドに対する速度比．

スレッド数	C++ [秒]	C++ [speedup]	Go [秒]	Go [speedup]
1	105.594	1.00000	140.792	0.75
2	52.717	2.00304	70.811	1.49121
3	40.357	2.61650	47.447	2.22551
4	29.754	3.54890	35.652	2.9618
5	24.524	4.30574	28.414	3.71627
6	20.513	5.14766	23.712	4.45319
7	17.643	5.98504	20.349	5.18915
8	15.398	6.85764	17.929	5.88956

どうやらC++の1.3倍程度の遅さらしい．問題が問題だけに台数効果はほぼリニアに出ている（スレッド数増やした時のC++の伸び具合が今ひとつだが…　スケジューリング変えるべきか？）．Goは性能的に何の問題もなく優秀だねぇ．まあ，この手の極単純なループの並列化に関してはOpenMPの方が楽ではあるけれど．

ついでに，24コア(Xeon X7460 @ 2.66GHz x4)のマシンでの実験結果（n=1７）．C++ はg++4.3.2 に -O3，Go は 6g/6l でコンパイル．OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定．speedup は C++ の１スレッドに対する速度比．

スレッド数	C++ [秒]	C++ [speedup]	Go [秒]	Go [speedup]
1	123.353	1.00000	144.181	0.85554
2	61.897	1.99288	71.764	1.71887
3	47.255	2.61037	47.722	2.58482
4	35.073	3.51704	35.823	3.4434
5	28.474	4.33213	28.741	4.29188
6	23.761	5.19141	23.846	5.1729
7	20.539	6.00579	20.491	6.01986
8	18.019	6.84572	17.954	6.8705
9	16.112	7.65597	15.965	7.72646
10	14.372	8.58287	14.394	8.56975
11	13.065	9.44148	13.109	9.40979
12	12.051	10.2359	12.007	10.2734
13	11.322	10.8950	11.091	11.1219
14	10.270	12.0110	10.299	11.9772
15	9.579	12.8774	9.619	12.8239
16	9.055	13.6226	9.014	13.6846
17	8.440	14.6153	8.500	14.5121
18	8.081	15.2646	8.014	15.3922
19	7.652	16.1204	7.611	16.2072
20	7.333	16.8216	7.225	17.0731
21	7.025	17.5591	6.904	17.8669
22	6.646	18.5605	6.587	18.7267
23	6.419	19.2169	6.296	19.5923
24	6.359	19.3982	6.274	19.661

スレッド数増やしたときにGoの方が速くなっているのはスケジューリングがうまいからだろうなぁ．OpenMPもラウンドロビンとかにすれば改善するかも？

---

ということで，サイズ１でラウンドロビンするように

#pragma omp parallel for reduction(+:sum) schedule(dynamic)

に変えてC++の実験を取り直した．

8コアマシンで．

スレッド数	C++ [秒]	C++ [speedup]	Go [秒]	Go [speedup]
1	106.079	1.00000	140.792	0.75344
2	53.386	1.98702	70.811	1.49806
3	35.603	2.97950	47.447	2.23574
4	26.741	3.96690	35.652	2.97540
5	21.373	4.96322	28.414	3.73334
6	17.901	5.92587	23.712	4.47364
7	15.329	6.92015	20.349	5.21298
8	13.513	7.85014	17.929	5.91662

24コアマシンで．

スレッド数	C++ [秒]	C++ [speedup]	Go [秒]	Go [speedup]
1	123.471	1.00000	144.181	0.85636
2	62.137	1.98708	71.764	1.72051
3	41.452	2.97865	47.722	2.58730
4	31.043	3.97742	35.823	3.44670
5	24.837	4.97125	28.741	4.29599
6	20.711	5.96161	23.846	5.17785
7	17.849	6.91753	20.491	6.02562
8	15.546	7.94230	17.954	6.87707
9	13.785	8.95691	15.965	7.73386
10	12.434	9.93011	14.394	8.57795
11	11.309	10.9179	13.109	9.41880
12	10.360	11.9181	12.007	10.2833
13	9.562	12.9127	11.091	11.1325
14	8.882	13.9013	10.299	11.9886
15	8.302	14.8724	9.619	12.8362
16	7.772	15.8866	9.014	13.6977
17	7.317	16.8745	8.500	14.5260
18	6.914	17.8581	8.014	15.4069
19	6.552	18.8448	7.611	16.2227
20	6.227	19.8283	7.225	17.0894
21	5.923	20.8460	6.904	17.8840
22	5.663	21.8031	6.587	18.7446
23	5.431	22.7345	6.296	19.6110
24	5.474	22.5559	6.274	19.6798

うん，常にC++の方が速い結果になったので問題なし．スケジューリングのオーバヘッドが無視出来る問題だから，スケジューリングの柔軟さがやっぱ効いてくるねと．