Moderators: hgm, Rebel, chrisw
Fascinating! Not sure if it's exactly optimal, for sparsely populated bitboards.Gerd Isenberg wrote:I see. How about brute force simd approach (8 xmm-regs) to expand the bitboard to a wordboard alá SSE2-dot-product, to mask the expanded words (0xffff for a binary one, 0x0000 for binary zero) with a word[64]-vector, containing order bytes ( > 0) in the upper half and the bitindex (0..63) in the lower half. Then sort the vector by a small SSE2 bubble sort
Code: Select all
int bitscan_pri_z(bb_t bb)
{
int bit, res = 0;
bb_t r;
/* Unroll this! */
for (bit = 5; bit >= 0; bit--) {
r = (bb & pri_mask[bit]) != 0;
bb &= pri_mask[bit] | (r - 1);
res = res << 1 | r;
}
return rev_priority[res];
}
bb_t bitscan_pri_so(bb_t bb)
{
int bit;
bb_t r;
/* Unroll this! */
for (bit = 5; bit >= 0; bit--) {
r = (bb & pri_mask[bit]) != 0;
bb &= pri_mask[bit] | (r - 1);
}
return (bb);
}
int bitscan_pri_s(bb_t bb)
{
int bit;
bb_t r;
/* Unroll this! */
for (bit = 5; bit >= 0; bit--) {
r = (bb & pri_mask[bit]) != 0;
bb &= pri_mask[bit] | (r - 1);
}
return bsfq(bb);
}
int bitscan_pri_m(bb_t bb)
{
int bit, res = 0, r;
/* Unroll this! */
for (bit = 5; bit >= 0; bit--) {
r = (bb & pri_mask_a[bit][1]) != 0;
bb &= pri_mask_a[bit][r];
res = res << 1 | r;
}
return rev_priority[res];
}
int bitscan_pri_sm(bb_t bb)
{
int bit, r;
/* Unroll this! */
for (bit = 5; bit >= 0; bit--) {
r = (bb & pri_mask_a[bit][1]) != 0;
bb &= pri_mask_a[bit][r];
}
return bsfq(bb);
}
Code: Select all
t = clock();
for (i = 0; i < 10000000; i++) {
bb_t b = -1;
x = 0;
while (b) {
b &= ~(1ull << x);
x++;
}
}
int overhead = clock() - t;
int time;
t = clock();
for (i = 0; i < 10000000; i++) {
bb_t b = -1;
while (b) {
int s = bitscan_pri_z(b);
b &= ~(1ull << s);
}
}
time = clock() - t - overhead;
printf("zach: overhead=%i, time=%i\n",overhead, time);
Code: Select all
zach: overhead=54, time=1037
steffan orig: overhead=54, time=873
steffan: overhead=54, time=903
marco: overhead=54, time=1389
s/m: overhead=54, time=1769Propably the bubble sort of 64 shorts is a bit too slowZach Wegner wrote:Fascinating! Not sure if it's exactly optimal, for sparsely populated bitboards.Gerd Isenberg wrote:I see. How about brute force simd approach (8 xmm-regs) to expand the bitboard to a wordboard alá SSE2-dot-product, to mask the expanded words (0xffff for a binary one, 0x0000 for binary zero) with a word[64]-vector, containing order bytes ( > 0) in the upper half and the bitindex (0..63) in the lower half. Then sort the vector by a small SSE2 bubble sort
Thanks for testing !Zach Wegner wrote: Surprisingly, the bsfq in Steffan's is very cheap, and the combination of Steffan and Marco's proposals was much slower than the original. Steffan looks like the winner here though.
Code: Select all
void rol32(uint64_t& bb) {
bb = (bb << 32) | (bb >> 32);
}
int bitScanReverse32(uint32_t b) {
const uint32_t U16 = 0xFFFF0000;
const uint32_t U08 = 0xFF00FF00;
const uint32_t U04 = 0xF0F0F0F0;
const uint32_t U02 = 0xCCCCCCCC;
const uint32_t U01 = 0x88888888;
const uint64_t L16 = (uint64_t(~U16) << 32) + U16;
const uint64_t L08 = (uint64_t(~U08) << 32) + U08;
const uint64_t L04 = (uint64_t(~U04) << 32) + U04;
const uint64_t L02 = (uint64_t(~U02) << 32) + U02;
const uint64_t L01 = (uint64_t(~U01) << 32) + U01;
int ret = 0;
uint64_t bb = (uint64_t(b) << 32) | b;
bb &= L16;
if (unsigned(bb)) ret += 1; else rol32(bb);
bb = (bb << 32) | unsigned(bb);
ret <<= 1;
bb &= L08;
if (unsigned(bb)) ret += 1; else rol32(bb);
bb = (bb << 32) | unsigned(bb);
ret <<= 1;
bb &= L04;
if (unsigned(bb)) ret += 1; else rol32(bb);
bb = (bb << 32) | unsigned(bb);
ret <<= 1;
bb &= L02;
if (unsigned(bb)) ret += 1; else rol32(bb);
bb = (bb << 32) | unsigned(bb);
return (ret << 1) + (unsigned(bb & L01) != 0);
}
int bitScanReverse(uint64_t b) {
const uint32_t hb = b >> 32;
return hb ? 32 + bitScanReverse32(hb) : bitScanReverse32(uint32_t(b));
}