Author: Miguel A. Ballicora
Date: 15:07:40 04/24/01
Go up one level in this thread
On April 23, 2001 at 19:30:20, Alex Boby wrote:
>
>I used to have this:
>
>------------
>void parseBitboard (int from, struct MoveList *ml, bitboard attack)
> {
> int i;
>
> for (i=0; i<64; i++)
> {
> if (attack&mask[i])
> [add move to list]
> }
> }
>------------
>and got this in the profile:
>7301.351 3.9 37127.739 19.6 538488 _parseBitboard (pierre.obj)
>
>and then, figuring I would get a significant speed increase, I switched to this:
>
>-----------------
>int findBitIndex(bitboard data)
> {
> int index;
>
> __asm
> {
> bsr edx, dword ptr data+4
> mov eax, 32
> jnz s1
> bsr edx, dword ptr data
> mov eax, 0
> jnz s1
> mov edx, -1
> s1: add edx, eax
> mov index, edx
> }
>
> return index;
> }
>
>void parseBitboard (int from, struct MoveList *ml, bitboard attack)
> {
> int index;
>
> while ((index = findBitIndex(attack))!=-1)
> {
> [add move to list]
> attack -= mask[index];
> }
> }
Using your example, I have the feeling that this would be faster:
(I am not sure if != -1 is the right comparison but you get the idea)
void parseBitboard (int from, struct MoveList *ml, bitboard attack)
{
int index;
unsigned long int firshalf = attack & 0xffffffff;
unsigned long int secondhalf = (attack >> 32) 0xffffffff;
while ((index = findBitIndex32(firsthalf))!=-1)
{
[add move to list using index]
firsthalf -= mask[index];
}
while ((index = findBitIndex32(secondhalf))!=-1)
{
[add move to list using index+32]
secondhalf -= mask[index];
}
}
findBitIndex32 would use a 32 bit unsigned integer that will be
pretty easy to code in assembler without any kind of jumps.
I think one or two lines with bsf would do it.
I have no experience on this (so take my suggestion with a grain of salt), but
reading material about optimizations it is obvious that is better to take the
"if's" out of the loops. In fact, the "ifs" are hidden here because they are
coded in assembler.
It would be an optimization like going from
i=0;
while (i<N) {
if (a)
x[i]=0
else
x[i]=1; /* you do something like this hidden in */
/* assembler*/
i++;
}
vs.
i=0;
if (a)
while (i<N) {x[i]=0; i++};
else
while (i<N) {x[i]=1; i++};
Regards,
Miguel
>-------------
>and then got this in the profile:
> 6763.331 4.4 32424.707 21.1 530420 _parseBitboard (pierre.obj)
> 1313.554 0.9 1313.554 0.9 3523746 _findBitIndex (pierre.obj)
>
>with about a 10% drop in nodes/sec.
>
>I thought that BSF & BSR were supposed to be fast! What am I doing wrong?
>This is on an Intel P3/500 w/ win2k.
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.