シフトが表引きより速くなる理由

edaxというオセロソフトがあるのですが、そこでは『1を左シフトする操作』が表引きで実装されています。マクロがbit.hで宣言されていて、表の実体はbit.cにあります。

https://github.com/abulmo/edax-reversi/blob/master/src/bit.h

extern const unsigned long long X_TO_BIT[];
/** Return a bitboard with bit x set. */
#define x_to_bit(x) X_TO_BIT[x]

//#define x_to_bit(x) (1ULL << (x)) // 1% slower on Sandy Bridge

https://github.com/abulmo/edax-reversi/blob/master/src/bit.c

/** coordinate to bit table converter */
const unsigned long long X_TO_BIT[] = {
	0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
	0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
	0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
	0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
	0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
	0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
	0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
	0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
	0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
	0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
	0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
	0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
	0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
	0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
	0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
	0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL,
	0, 0 // <- hack for passing move & nomove
};

この"1% slower on Sandy Bridge"が本当かと思ったのでSkyLakeで比較してみました。このリポジトリのコードと完全に同じではないので断言できませんが、単に上記のdefineのコメントアウトを切り替えて比較した場合、表引きよりシフトのほうが1%くらい速かったです。（fforum-40-59.obf を完全読みする実行時間で比較しました）

ちなみに、マジで#defineの左の"//"を切り替えるだけだと右側の"// 1% slower on Sandy Bridge"も挿入されてバグります。あと、下の配列定義では要素数が64でなく66になっていて、[64]と[65]はそれぞれパスと"NOMOVE"（センチネルとして使われている）を意味しています。その[64]と[65]は0ですが、(1ULL << 64)は0ではなく1になってしまいます。ゆえにこのdefineを切り替えるときにはx_to_bitマクロに64とかが入らないようにする必要があって、それには呼び出し元であるedaxのコードを適切にいじる必要があります。

flip関数（？）について

オセロソフトのビット演算トピックはいくつかありますが、最も重要なのはflipと呼ばれる機能です。flipとは、プレイヤーがある座標に石を置いたときにひっくり返る石を全列挙する計算のことです。edaxのリポジトリにはflipだけを実装した.cファイルがいくつも存在していて、そのどれか1つが#board.c内のincludeディレクティブで挿入される仕掛けになっています。どれが挿入されるのかはsettings.hに書かれたdefineマクロで制御されています。

https://github.com/abulmo/edax-reversi/blob/master/src/flip_sse.c

「決め打ちした特定の座標のためだけの関数」を64通り（実際には66通り）書き下したうえで、一番下にある関数ポインタ配列でジャンプさせるというやべー感じになっています。fforum-40-59.obf 完全読みでパフォーマンスプロファイリングしたところ、このflip関数（？）が総実行時間の10%以上を占めていました。ちなみに単一の関数（？）としては最も大きく、次がhash_getで7%とかでした。

AVX2を活用したflip関数はこの本家edaxのリポジトリにはありませんが、別の人が書いたものが公開されています。

https://github.com/okuhara/edax-reversi-AVX/blob/master/src/flip_avx.c

AVX2版flipのx_to_bitは表引きのほうがなぜか速かった

このAVX2版flip関数は、宿主のedaxのX_TO_BIT配列をそのまま表引きしています。ゆえに、AVX2版flip関数を採用した状態でx_to_bitマクロを切り替えても、マクロを介さずに表引きしているこいつだけは切り替わらないわけです。偶然気付いたのですが、その状態が最速でした。つまり、

ocontig = _mm256_set1_epi64x(1ULL << pos);
ocontig = _mm256_set1_epi64x(X_TO_BIT[pos]);
ocontig = _mm256_slli_epi64(_mm256_set1_epi64x(1), pos);

こんな感じの3通りが考えられるわけですが、真ん中の表引きが最速でした。にもかかわらず、x_to_bitマクロ自体は左シフトに切り替えたほうが確かに高速でした。（ちなみに、flipの呼び出し元もPASSとかを渡しうる実装になっているので、真ん中以外に切り替えるときにはそれらを適切にいじっておく必要があります）

bts命令

理由はたぶん、bts命令に書き換えられるかどうかです。edaxの探索処理のなかでx_to_bitマクロが呼ばれる大部分は盤面を更新するところです。例えば以下の関数の1行目です。ちなみにboard->playerは手番側の石のビットボードで、move->flippedはひっくり返る石のビットボードで、move->xは石を置く座標です。

https://github.com/abulmo/edax-reversi/blob/master/src/board.c

void board_update(Board *board, const Move *move)
{
	board->player ^= (move->flipped | x_to_bit(move->x));
	board->opponent ^= move->flipped;
	board_swap_players(board);

	board_check(board);
}

x_to_bitの返り値を即座にorすることは、レジスタの特定のビット位置を1にセットすることと等価です。それはx86ではbtsという命令でできます。実際この盤面更新部とAVX2版flipの逆アセンブルを見ると、前者だけbtsが使われていました。結論としては

  • x | (1 << y) の形になっていれば、コンパイラはそれをbtsに変更できて表引きより速くなる
  • btsが使えないケースでは、1をロードしてシフトするよりも表引きのほうが速い
  • （たぶん）sandy bridgeの頃はコンパイラがbtsを活用してくれなかったので常に表引きのほうが速かった

最後のは推測ですが、確かめるのはだるすぎるのでこのままにしておきます。

余談

将棋ソフトでは盤面のビットボードがuint64_tに収まらないので、__m128iを各自工夫して使う感じになっています。そのため1マスぶんのビット変更も __m128i[81] を表引きしてxorなどするのが普通です。