Author: Dieter Buerssner
Date: 08:20:53 06/26/01
Go up one level in this thread
On June 26, 2001 at 08:48:19, Uri Blass wrote:
>This question is important for my move generator
>
>dirnow is a 16 bit non negative integer and I want to translate it to an array
>that include the place of it's digit.
>example:
>Suppose dirnow=131=2^7+2^1+2^0
>I want to get from dirnow the following information:
> directionsq[0]=7
> directionsq[1]=1
> directionsq[2]=0
>
>In most of the cases dirnow is a number with a lot of 0's and only few 1's.
>
>How to do it in the fastest way?
I think, the methods you have shown are about as fast, as you can get,
by using high level language. If you want to use (inline)-assembler, you
might want to have a look at the Crafty source code for FirstOne/LastOne.
>one possible way is to use big arrays
>a[65536][16]
>weight[65536];
>
>This arrays should be calculated only one time and I get
>
>a[131][0]=7
>a[131][1]=1
>a[131][2]=0
>weight[131]=3
>
>in this case I only need to do
>i=0;
>while (i<weight[dirnow])
> directionsq[i]==a[dirnow][i];
You may gain a few CPU-cycles, by assuming that at least one bit is set.
Also, the comparision i<weight[dirnow] might not be obtimized well, when the
compiler cannot easily prove, that directionsq and weight cannot overlap
("alias").
So, slightly less readable, and also taking some adress calculations out
of the inner loop in C:
/* Assume dirnow != 0, totally untested */
extern int weight[];
extern int a[][16];
void set_directions(int *directionsq, unsigned int dirnow)
{
int i;
int *ap;
ap = a[dirnow];
i = weight[dirnow];
do
{
*directionsq++ = *ap++;
}
while (--i != 0);
*directionsq = -1; /* Flag the end of the array, of course you could
also return the count of set bits */
}
>The number of commands seem to be very small but I am afraid that big arrays may
>do the program slower.
This could well be the case. Your second method will have a smaller
cache-footprint, and may perform faster.
>
>Another way is to use the following small arrays
>a[256][8]
>weight[256]
>
>In this case I need to do something like
>i=0;
>While (i<weight[dirnow&(1<<16-1<<8)>>8])
> directionsq[i]=8+a[(dirnow&(1<<16-1<<8))>>8][i];
If you know, that dirnow will never be bigger than 2^16-1 (which is very likely
from what you are saying), you can leave the & mask out. When dirnow is really
is an unsigned integer type of 16 bit, the compiler will probably do this
anyway. If not (on 32-bit CPUs using a 32 bit type will probably be faster), the
compiler won't be able to figure this out. The method I shown above should also
be able to speed this up a bit. However, you cannot use the do while anymore
here, because the low or hight part of dirnow may be zero. So
while (--i >= 0)
might be the fastest.
>j=0;
>While (j<weight[dirnow&255])
> directionsq[i+j]=a[(dirnow&255)][j];
>
>I decided to write 1<<16-1<<8 to do it more simple to understand and I think to
>use an exact number in my move generator.
I think, this is debatable. I personally would find
(dirnow >> 8) & 255
easier to read, but this certainly is a matter of taste.
Regards,
Dieter
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.