Author: Miguel A. Ballicora
Date: 09:00:03 12/04/02
Go up one level in this thread
On December 03, 2002 at 17:00:45, Gerd Isenberg wrote:
>Hi Miguel,
>
>interesting serialisation approach. Soo many ways to Rome ;-)
>
>Some thoughts:
>
>Even if the instructions are cheap, you obviously run for every set bit through
>the inner loop, where the *ps++ = r | c; instruction occurs. Also it seems the
>runtime of your loops depend on the bit-positions (eg. bit 0 terminates earlier
>than bit 31 if they are exclusively set in one 32bit-word).
>
>Next point is you write terminated square arrays into memory, and you have to
>traverse this arrays later, looking for the terminator, or do i miss something?
>So you need a second, but of course cheaper loop.
Yes, that is right. Finding the bits and doing something with them are
separated. The idea is that when you find the bits all at the same time, you can
split the 64 bits integer in two 32 bits integer.
In theory even if you use BSR() there should be an advantage. It should be
better to do bsr32() on all the bits from the lower half and later on all the
bits from the upper half than do it all at once with a bsr64(), since this
bsr64() that is in the inner loop contains some kind of branching or some trick
to work on two halves of 32 bits.
In other words,
int squares[64+1];
long long unsigned bb;
long unsigned half1, half2;
for (i = 0, half1 = getlowerhalf(bb); half1; i++) {
squares[i] = bitSearchAndReset32(half1);
}
for ( half2 = getupperhalf(bb); half2; i++) {
squares[i] = 32 + bitSearchAndReset32(half2);
}
squares[i] = 64;
for (int i=0; squares[i]; ++i)
doSomething( squares[i] );
/*--------------------------------------*
Should be better than
*--------------------------------------*/
int squares[64+1];
long long unsigned bb;
for (i = 0; bb; i++) {
squares[i] = bitSearchAndReset64(bb);
}
squares[i] = 64;
for (int i=0; squares[i]; ++i)
doSomething( squares[i] );
The optimization comes from the difference between bitsearchAndReset32()
and bitsearchAndReset64().
bitsearchAndReset32 could use any of the techniques you posted. Mine most
probably is not the better, I did it because it was portable but you posted some
that are portable too.
Regards,
Miguel
>If i look to Walters routine, so few instructions to get a bit index, i believe
>this direct bitscan approach is cheaper. Also the outer control structure seems
>IMHO easier and more readable, but that may be a matter of taste.
>
>while (bb)
> doSomething( bitSearchAndReset(bb) );
>
>
>If i would do it in that way, your approach may preferable:
>
>int squares[64+1];
>for (int i=0; bb; ++i)
> squares[i] = bitSearchAndReset(bb);
>squares[i] = 0;
>for (int i=0; squares[i]; ++i)
> doSomething( squares[i] );
>
>Anyway, interesting algorithm to get the square indicies, thanks for sharing.
>
>Regards,
>Gerd
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.