popcntを用いたbitboardに対するforeachの高速化手法の提案

1であるbit位置を探す命令としてbsf(BitScanForward)がある。bitboardに対するforeachはこれを用いて行なう。bsr(BitScanReverse)ではなく、bsfを使うのは、bsfなら、そのあとそのbitを0にするのに、u &= u -1;という技が使えるからである。(→ http://d.hatena.ne.jp/LS3600/20091117 )


しかし、bsfのlatencyは3で、ループのなかでこれを使うとループの終了判定自体が待たされて、ループが抜けるのか抜けないのかが確定しないので、次の命令を先読みするわけにもいかず、回数の多いループ(特に駒を打つ指し手を生成するgen_drop)では、この部分でずいぶんとロスをする。典型的には、bsf + 条件ブランチ命令の直後にnpad疑似命令(≒ nop)が挿入される。


SSE4.2の命令には、1であるbitを数える命令としてpopcnt(PopuCount)がある。VC++2010β2で確認したところ、x64環境であれば、次のようにすれば使える。(そのマシンがSSE4.2に対応している必要があるが) もちろん、きちんとpopcnt命令に変換され、該当部分に埋め込まれる。

#include "intrin.h"

// 1であるbitを数える。
inline u64 PopuCount64(u64 u)
{

	// __MACHINEX86X_X64(int _mm_popcnt_u32(unsigned int v))
	// __MACHINEX64(__int64 _mm_popcnt_u64(unsigned __int64 v))

	/*
	int counter = 0;
	while ( u ) { counter++;  u &= u - 1U; }
	return counter;
	*/

	return _mm_popcnt_u64(u);
}

popcntの32bit版のlatencyは3。64bit版のほうのlatencyは公開されていないが、たぶん3だと思う。1であるbitが多いことがわかっているbitboardに対してforeachをしたいときは事前にこれによってループ回数を確定させておくことによって、ループをunrollすることが出来てbsfのlatencyを実質的に隠匿できる場合がある。


私の実験によると、これによりgendropが13%程度改善した。ただ、40通りに展開しているgendropのコードサイズがさらに膨らんだので私はこの変更は取り入れないと思う。