前回の記事で、符号なし64bit整数を8x8 bitboardとみなして転置する方法として、基本RISC命令のみでやる方法と、AVX2のmovemask命令などを使う方法があるという話について書きました。今回はそれの続きで、ハッカーのたのしみ第7章7.5を改良した方法も加えてベンチマークを取ってみました。
前回の記事：
ハッカーのたのしみ第7章7.5の改良についての記事：
提案手法
ハッカーのたのしみ7章7.5では、「ワードの一般的順列演算」と筆者らが呼んでいる演算の方法が紹介されていました。その詳細と改良点については上記の記事に書いてあります。それを使うと行列転置はsag関数3回で書けます。平たく書くと以下のようになります。
uint64_t transpose_bitboard_pext(uint64_t x) { //引数が8x8 bitboardだとして、転置して返す。 constexpr uint64_t p = 0xAAAA'AAAA'AAAA'AAAAULL; x = (_pext_u64(x, p) << 32) | _pext_u64(x, ~p); x = (_pext_u64(x, p) << 32) | _pext_u64(x, ~p); x = (_pext_u64(x, p) << 32) | _pext_u64(x, ~p); return x; }
実験結果
ベンチマークでは、xorshift64で生成した乱数を転置させる処理を2^30回行いました。このとき、転置させた結果の値を次の乱数生成への入力にする・しないの両方を試してみました。「しない」場合でも全ての転置結果をxorした値を最後に出力します。CPUは Xeon Gold 6136 (2017年発売、SkyLake世代)で、コンパイラはgcc-8.2.0でした。
| basic | AVX2 | pext | |
|---|---|---|---|
| する (ms) | 6119 | 4582 | 6368 |
| しない (ms) | 3199 | 1987 | 1901 |
考察
pextをL1T0.5とかにしてほしい（わがまま）
