CSA例会資料 2006/09/09 電通大 山下 宏 YSSの高速化について 昨年はあまり効果がある改良はできなかったので、昔から やってきた小さな高速化の寄せ集めを紹介します。 高速化の基本としては、 「やっぱり実際に計ってみないと分からない」 というのがあります。 明らかに速そうなコードでも計ってみるとCPUの特徴などで遅くなったります。 （ループ展開など） 1. ハッシュのクリア HASH *pt = hash_table; // ループの中ではグローバルポインタは使わない。 int size = Hash_Table_Size; for (i=0; i 512MB -> 256MB) これの3回目でfree(),malloc()で落ちる。謎。 reallocでも4回目に落ちる・・・。 どうやら何度も繰り返して確保するとメモリ不足になるようだ。 いったん、最大サイズを割り当てたら、もうそれ以下では再割り当てはしないように。 （最初に1GB確保して、512MBだけ使うときは、何もしない） ・WindowsXPでは1GB以上をダイレクトに確保できない。Windows2000なら可能。（柿木さん） ２．利きの関数のループ展開 利き消す場合に、 3つ駒が利いている場合 kiki_m[0x34] = { 18, 25, 34, ...} // 18,25,34 番の駒が利いている 25番の利きを消したい、とします。 今までは、ループ展開していたのですが、これをループに変えたら4.2％高速化。 objファイルが80KBくらいから40KBくらいに半減して、 キャッシュに載りやすくなった？のもあるのかもしれません。 #ifdef KIKI_D_FOR_LOOP // エラーチェックなしでloopに。 #define KIKI_DM(x) p = kb_m[x]; \ pk = --kiki_m[x] + p; \ for (;z != *p; p++) ; \ *p = *pk; #else /* 18回検索して見つからなかったらエラー */ /* z = ban[z]; で駒番号 */ #define KIKI_DM(x) p=kb_m[x]; \ pk=--kiki_m[x]+p; \ if (z-*p) \ if (z-*++p) \ if (z-*++p) \ if (z-*++p) \ if (z-*++p) \ ... ３．関数ポインタ配列 今までは、下のように switch文で利きを消す駒の場合分けをしていました。 switch はif文が並んで遅いように見えるが、最適化されると on goto ... 形式になって速い。 void kikid(register int z) { register int s = init_ban[z]; switch (s) { case 0x01: fu_dm(z); // 先手の歩の利きを消す break; case 0x02: yari_dm(z); break; case 0x03: kei_dm(z); break; case 0x04: gin_dm(z); default: __assume(0); こう書くと、VCは強制的にswitchをjumpに変えてくれる。dafaultには 決して来ない、という意味で。ただし、1,2,4,5,6, などと欠けていると落ちる。(橋本さん） これを高速化のために関数を配列にしてON GOTO を真似る。---> 3%の高速化 #define kikid(z) (this->*func_kiki_delete[ init_ban[z] ])(z) 暗号のような形をしてますが、どこかの解説の丸写しです。 最初のthis、はSMP化した場合に、個々の盤面を示します。 実際には下のような感じです。 // さらにマクロにする（呼ぶ回数が詰将棋だと最大なので） #define kikiw(z) (this->*func_kiki_write[ init_ban[z] ])(z) #define kikid(z) (this->*func_kiki_delete[ init_ban[z] ])(z) 関数ポインタ配列 void (shogi::*func_kiki_delete[0x90])(int) = { &shogi::ekd, // 0x00 &shogi::fu_dm, // 0x01 先手の歩の利きを消す &shogi::yari_dm, &shogi::kei_dm, &shogi::gin_dm, &shogi::kin_dm, &shogi::ka_dm, &shogi::hi_dm, ... }; // 「型を返さずintの引数を1つもつ」関数へのポインタ、の配列 extern void (shogi::*func_kiki_write[0x90])(int); extern void (shogi::*func_kiki_delete[0x90])(int); void shogi::fu_wm( register int z ) // 歩の利きを消す関数 { register int zz; zz=z-0x10; z=ban[z]; KIKI_WM(zz) /* kb_m[ zz ][ kiki[ zz ]++ ]=ban[z] */ } 実際に利きを消す場合は、こんな感じ。 if ( (tk=ban[az]) != 0 ) kikid(az); // 取る駒の利きを消す ４．評価関数 王との距離をY座標2倍の相対座標で計算する。評価関数のループが19.8秒 ---> 18.9秒？！ shortをintにしたら19.2秒。 位置を z = y*16 + x で表している場合に、0x31 から 0x29 への相対距離を知りたい場合に 下のようにすれば一発で出せる。 z_2z = KYORI_2Z(z); // COMの王からCOMの駒までの距離を出して計算 n = base_ryuuma_mikata_2z[soutai_kyori_2z(comou_2z,z_2z)]; #define KYORI_2Z(x) (((x)&0xf0)+(x)) inline int soutai_kyori_2z(int from_2z, int king_2z) { return (BAN_SIZE_2Z_GETA + from_2z - king_2z); } 評価関数で大きなテーブルを参照すると、速度が逆に低下する。11.7秒 ---> 11.9秒 2歩データを常にテーブルに保持する場合。0.6%(終盤)〜1.2%(序盤)の高速化。12.4秒---> 12.2秒、47.2秒--->47.0秒。、 nifu_table[2][10]; // 歩があるx座標が1になる。 詰将棋の中で、王手の局面では千日手をチェックしない（この方が4%速い） ５．クリアしないテーブル あまり高速化とは関係ないのですが、盤面全体のテーブルを使用して、 毎回、どこかにフラグをセットするような場合、 セットする値を関数にくるたびに +1 してやることで、テーブルのクリアにかかる 時間をほとんど0に出来ます。 static int kokyu_iti_inc[BANMAX]; // 連の呼吸点を一時的に保存するための増えていくテーブル kokyu_iti_inc_base++; // 呼吸点の位置をこの関数の中だけで保存するテーブルで用いる基準値 if ( kokyu_iti_inc_base > KOKYU_ITI_INC_BASE_MAX ) { // めったに超えない for (i=0;ikokyu_iti[i]; kokyu_iti_inc[z] = kokyu_iti_inc_base; // 呼吸点の位置をテーブルに保存 } for (j<0;jkokyu_iti[j]; // 呼吸点の位置 if ( kokyu_iti_inc[z] != kokyu_iti_inc_base ) { // 重複していないので追加 ６．union を使って、ハッシュテーブルの使いまわし // int は 32ビットを前提にしている。hash の合計は32バイトになるように調節 typedef struct HASH { // タグ名を付けないと前方参照できなくて不便 // clear する時にアクセスする部分が 1 DWORD になるように配置調整 // char が連続するように。 // flag を最初に参照するので最初に置く（CPUのメモリのバースト転送を考慮） unsigned short int flag; // この評価値が正確な値か、もしかは上限下限か。0で未登録。 // 0000 0000 // 実際の探索用4bit 00... 未使用 01...正確な値 10 ...上限、又は下限 11...ハッシュOVER 100...最善手のみ登録 // 脊尾詰com 2bit 00... 未使用 01...使用 10 ...打歩詰フラグON // 脊尾詰man 2bit // 通常詰com 1bit 0 ... 未使用 1 ... 使用 // 通常詰man 1bit // 自分だけが使用しているか、又は誰も使用していなければ書きこみ可 // if ( (flag & 11110011)==0 ) OK! volatile char lock[1]; // SMPでのロック用。hashのみで使用。LockChar()を使う。 unsigned char hit_num; // このハッシュを参照した回数。(4バイトにするためのダミー) unsigned int hash_code1; // ハッシュコード 01。後手番は反転させる unsigned int hash_code2; // ハッシュコード 02。計64ﾋﾞｯﾄ。2^32局面を作って誤認確率は１％。 unsigned int motigoma; union { // 無名共用体（VCの専用らしいのでgccではだめ？かも） struct { unsigned int pn; unsigned int dn; unsigned int nodes; // この情報を得るのに探索した局面数 unsigned short min_distance; // 最小距離 unsigned short dummy; }; struct { int value; // 評価値 int depth; // 探索深さ（相対的な深さ）256の倍数で小数点を表す union { struct { unsigned char man_depth; // 詰将棋MAN用探索深さ（相対的） unsigned char com_depth; // COM用 unsigned char man_tume; // 詰め将棋の評価値（詰，切れ，不明，・・自由度） unsigned char com_tume; }; struct { unsigned int seo_nodes; // この情報を得るのに探索した局面数 }; }; TE best; // この局面での最善手 }; }; } HASH;