okuhara / edax-reversi-AVX

Automatically exported from code.google.com/p/okuharaandroid-edax-reversi
GNU General Public License v3.0
19 stars 5 forks source link

SSE get_moves #4

Closed acepck closed 1 month ago

acepck commented 2 months ago

board_sse2.txt SSE get_movesの全部SSEバージョンを書いてみました intelのCPUでは概ねいくらか速くなるようですが特に古めのamdではどうでしょう? SSEが多分速くないと思うので遅くなりそうな気がしますが pentiumDでもgccだと元のコードより遅くなります pentiumDはSSE使わないバージョンが一番速いようですが

pentiumD e26: 399939952 nodes in 0:42.658 ( 9375497 nodes/s). clang orig e26: 399939952 nodes in 0:42.430 ( 9425877 nodes/s). clang all sse e26: 399939952 nodes in 0:41.214 ( 9703983 nodes/s). clang gpr e26: 399939952 nodes in 0:45.122 ( 8863524 nodes/s). gcc orig e26: 399939952 nodes in 0:46.634 ( 8576145 nodes/s). gcc all sse e26: 399939952 nodes in 0:44.012 ( 9087066 nodes/s). gcc gpr

core2 e28: 2483354531 nodes in 2:07.564 (19467519 nodes/s). clang orig e28: 2483354531 nodes in 2:03.739 (20069295 nodes/s). clang all sse e28: 2483354531 nodes in 2:09.057 (19242308 nodes/s). gcc orig e28: 2483354531 nodes in 2:06.682 (19603058 nodes/s). gcc all sse

ivybridge e28: 2483354531 nodes in 1:37.282 (25527379 nodes/s). clang orig e28: 2483354531 nodes in 1:34.144 (26378256 nodes/s). clang all sse e28: 2483354531 nodes in 1:33.564 (26541774 nodes/s). gcc orig e28: 2483354531 nodes in 1:31.294 (27201728 nodes/s). gcc all sse

okuhara commented 2 months ago

またすばらしいアイデアありがとうございます。 私がこのコードを書いていたころは Athlon 64 X2 とかで評価していて、ご指摘の通り SSE が遅かったのでそれに合わせたチューニングになっているかもしれません。 デフォルトでイネーブルするかどうかは別として、ソース中と解説ページには acepck さんのコードを入れようと思います。 で、ご提案のより重要な意味に気付いたのですが、左方向 +1 のキャリー伝搬は CPU にも適用できるので、CPU による get_moves はすべてそうするべきと。今までなぜキャリーによる方法を思いつかなかったのか・・

`unsigned long long get_moves(const unsigned long long P, const unsigned long long O) { unsigned long long moves, mO; unsigned long long flip1, flip7, flip9, flip8, pre1, pre7, pre9, pre8;

mO = O & 0x7e7e7e7e7e7e7e7eULL;
flip7  = mO & (P << 7);     flip9  = mO & (P << 9);     flip8  = O & (P << 8);      flip1  = mO & (P << 1);
flip7 |= mO & (flip7 << 7); flip9 |= mO & (flip9 << 9); flip8 |= O & (flip8 << 8);  moves  = mO + flip1;
pre7 = mO & (mO << 7);      pre9 = mO & (mO << 9);      pre8 = O & (O << 8);
flip7 |= pre7 & (flip7 << 14);  flip9 |= pre9 & (flip9 << 18);  flip8 |= pre8 & (flip8 << 16);
flip7 |= pre7 & (flip7 << 14);  flip9 |= pre9 & (flip9 << 18);  flip8 |= pre8 & (flip8 << 16);
moves |= flip7 << 7;        moves |= flip9 << 9;        moves |= flip8 << 8;
flip7  = mO & (P >> 7);     flip9  = mO & (P >> 9);     flip8  = O & (P >> 8);      flip1  = mO & (P >> 1);
flip7 |= mO & (flip7 >> 7); flip9 |= mO & (flip9 >> 9); flip8 |= O & (flip8 >> 8);  flip1 |= mO & (flip1 >> 1);
pre7 >>= 7;         pre9 >>= 9;         pre8 >>= 8;         pre1 = mO & (mO >> 1);
flip7 |= pre7 & (flip7 >> 14);  flip9 |= pre9 & (flip9 >> 18);  flip8 |= pre8 & (flip8 >> 16);  flip1 |= pre1 & (flip1 >> 2);
flip7 |= pre7 & (flip7 >> 14);  flip9 |= pre9 & (flip9 >> 18);  flip8 |= pre8 & (flip8 >> 16);  flip1 |= pre1 & (flip1 >> 2);
moves |= flip7 >> 7;        moves |= flip9 >> 9;        moves |= flip8 >> 8;        moves |= flip1 >> 1;

return moves & ~(P|O);  // mask with empties

} `

okuhara commented 1 month ago

02e6c670439468ce73a7202e95188419266a5653 で採用し、bitboard 解説ページ に解説を追加しました。