Home > Archives > December 2009

December 2009

cachegrind... 遅い…

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

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

Go-lf!

ということで,せっかく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;y:="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を介さねばならないのでメンド臭い&長すぎる.

Go に手を出す(並列計算)

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

セミコロン少なめだし,カッコ少なめだし,型を書くのも少なめだし,タプルあるし,型システム単純だし,例外ないし,オーバーロードないし,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=17).C++ はg++4.5.0 (exeperimental) に -O3,Go は 6g/6l でコンパイル.OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定.speedup は C++ の1スレッドに対する速度比.

スレッド数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=17).C++ はg++4.3.2 に -O3,Go は 6g/6l でコンパイル.OMP_NUM_THREADS と GOMAXPROCS でスレッド数を指定.speedup は C++ の1スレッドに対する速度比.
スレッド数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もラウンドロビンとかにすれば改善するかも?


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

#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++の方が速い結果になったので問題なし.スケジューリングのオーバヘッドが無視出来る問題だから,スケジューリングの柔軟さがやっぱ効いてくるねと.

Home > Archives > December 2009

Search
Feeds

Page Top