Winboard Forum

strelka has a big array Distance[64][64] to calculate distance between squares

I have the following definition in movei to calculate the same thing

#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define FileDistance(a,b) abs(((a)&7) - ((b)&7))
#define RankDistance(a,b) abs(((a)>>3) - ((b)>>3))
#define Distance(a,b) Max(FileDistance(a,b),RankDistance(a,b))

I added this definition to strelka and found that Distance(i,j) in my code is always equal to Distance[i][j] in strelka for 0<=i,j<=63

My question is which code is better for speed.

Uri

Uri Blass wrote:strelka has a big array Distance[64][64] to calculate distance between squares

I have the following definition in movei to calculate the same thing

#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define FileDistance(a,b) abs(((a)&7) - ((b)&7))
#define RankDistance(a,b) abs(((a)>>3) - ((b)>>3))
#define Distance(a,b) Max(FileDistance(a,b),RankDistance(a,b))

I added this definition to strelka and found that Distance(i,j) in my code is always equal to Distance[i][j] in strelka for 0<=i,j<=63

My question is which code is better for speed.

Uri

Hi Uri,
I guess you need to run the program to see which version is faster. I too have such a distance array in my engine and what I noticed is that it seems to matter from where you access such an array.

While I had a tremendous speedup by using the distance array in my move generation when generating legal moves it didn't gave me a speedup when calling the array directly from the search when generating pseudo legal moves. It was not faster than calling attack() (to check if the move leads/leaves in check) after making every move.

So I guess you need to actually test to conclude which version is faster.

regards
Roman

The problem I see with your macros is that you introduce several branches, and if you use that very often, the branches multiply. The commonly-used array elements will be cached and become almost free.

Too many interactions can influence the results. My advice is to test both ways. I _always_ do that if I want to make a decision on which is faster... it has to be faster in my program, not just faster on paper. Often things turn out differently than expected when tested.

bob wrote:The problem I see with your macros is that you introduce several branches, and if you use that very often, the branches multiply. The commonly-used array elements will be cached and become almost free.

Too many interactions can influence the results. My advice is to test both ways. I _always_ do that if I want to make a decision on which is faster... it has to be faster in my program, not just faster on paper. Often things turn out differently than expected when tested.

Interesting way to do branchless compare/move:
http://www.x86.org/secrets/opcodes/fcmov.htm

Of course, even if you benchmark both routines in your code, the answer may change when you run it on a different machine with a bigger cache or even change your compiler.

Uri Blass wrote:strelka has a big array Distance[64][64] to calculate distance between squares

I have the following definition in movei to calculate the same thing

#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define FileDistance(a,b) abs(((a)&7) - ((b)&7))
#define RankDistance(a,b) abs(((a)>>3) - ((b)>>3))
#define Distance(a,b) Max(FileDistance(a,b),RankDistance(a,b))

I added this definition to strelka and found that Distance(i,j) in my code is always equal to Distance[i][j] in strelka for 0<=i,j<=63

My question is which code is better for speed.

Uri

Likely the lookup is fastest here.

There are branchless ways to compute max and abs with a better chance to compute things in parallel but that takes registers. So it heavily depends whether the context does more register- or memory/cache stuff or whether your L1-cache are already heavily polluted.

Other option is to use 0x88 difference as index of much smaller table[240] and/or to make array of structs with similar stuff like taxiDistance to safe some cacheline here and there.

Code: Select all

0x88delta = sq2+(sq2&56)-sq1-(sq1&56)+120


See also the discussion on squares between two squares with similar issues:
http://wbforum.vpittlik.org/viewtopic.p ... 856&t=6573