bit boards - what is betwen

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

bit boards - what is betwen

Post by Don » Sun Dec 02, 2012 4:04 pm

What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Gerd Isenberg
Posts: 2104
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: bit boards - what is betwen

Post by Gerd Isenberg » Sun Dec 02, 2012 9:06 pm

Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: bit boards - what is betwen

Post by Don » Sun Dec 02, 2012 9:58 pm

Gerd Isenberg wrote:
Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
That is an excellent idea, similar to the mailbox attack array indexed by the difference in the squares location.

Thanks,

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

gladius
Posts: 535
Joined: Tue Dec 12, 2006 9:10 am

Re: bit boards - what is betwen

Post by gladius » Mon Dec 03, 2012 4:06 pm

Gerd Isenberg wrote:
Don wrote:What is the fastest way with bitboards to return a bit board of the points between any 2 squares? If the pieces are not on the same diagonal or orthogonal we return 0 of course. If the pieces are touching of course there is nothing between either.

I use a simple 64x64 array but wonder if there is anything clever than can be done without memory access. The array method seems unduly slow although I cannot imagine that it should be. Maybe it's not very cache friendly. I cannot think of anything else that does not require quite a bit of bit fiddling but you can do a lot of calculation in the time you lose with a cache miss.
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
Thanks for the idea Gerd! I ended up trying this in Stockfish, and got a small speed win. I ended up using an array of size 120, as I couldn't see how to avoid a conditional on the shift even when using size 240.

Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.

User avatar
hgm
Posts: 22184
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: bit boards - what is betwen

Post by hgm » Mon Dec 03, 2012 4:34 pm

What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: bit boards - what is betwen

Post by Don » Mon Dec 03, 2012 4:47 pm

hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: bit boards - what is betwen

Post by diep » Mon Dec 03, 2012 6:07 pm

Don wrote:
hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Why would a 64x64 array be slower than executing more code with smaller array access?

The real problem of modern processors is mainly decode speed of instructions.

Gerd Isenberg
Posts: 2104
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: bit boards - what is betwen

Post by Gerd Isenberg » Mon Dec 03, 2012 9:03 pm

gladius wrote:
Gerd Isenberg wrote:Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
Thanks for the idea Gerd! I ended up trying this in Stockfish, and got a small speed win. I ended up using an array of size 120, as I couldn't see how to avoid a conditional on the shift even when using size 240.

Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.
Its a matter of correct initialization, to make the rotate left approach with 240 element lookup work, f.i.:

Code: Select all

       . . . . . . . .    . . . . . . . .
       . . . . . . . .    . . . . . . . 1
       . . . . . . . .    . . . . . . 1 .
       . . . . . . . .    . . . . . 1 . .
       . . . 1 . . . .    . . . . . . . .
       . . 1 . . . . .    . . . . . . . .
       . 1 . . . . . .    . . . . . . . .
       . . . . . . . .    . . . . . . . .

between   (0, 36) 		  (36, 0) 	
lookup -> { 9, 18, 27}    {37, 46, 55}
rotl   -> { 9, 18, 27}    { 9, 18, 27}  

between   (10, 46)        (46, 10) 
lookup -> { 9, 18, 27}    {37, 46, 55}
rotl   -> {19, 28, 37}    {19, 28, 37}

between   (27, 63)        (63, 27)
lookup -> { 9, 18, 27}    {37, 46, 55}
rotl   -> {36, 45, 54}    {36, 45, 54}
Otherwise, with 120, to avoid that branch, better use std:abs of the +/- difference.
Last edited by Gerd Isenberg on Mon Dec 03, 2012 9:13 pm, edited 1 time in total.

Gerd Isenberg
Posts: 2104
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: bit boards - what is betwen

Post by Gerd Isenberg » Mon Dec 03, 2012 9:11 pm

diep wrote:
Don wrote:
hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
I meant without memory access but I would settle for anything that produced a speedup on modern processors.

The mailbox programs would index a much smaller array by using (destination - origin) as the index. To work with a 6 bit square a little bit twiddling would do the job. So if having a small array is a win, it might still be a win despite some additional bit twiddling to convert a 6 bit square to a 7 bit square but it's hard to believe that would make any difference.
Why would a 64x64 array be slower than executing more code with smaller array access?

The real problem of modern processors is mainly decode speed of instructions.
Really? I thought still branches and L1, L2 misses - at least in chess programs.

Sometimes smaller memory pays off, 32K vs. < 2K, likely more often in L1. A few additional instructions may improve ipc and hide latencies. How much is a L1 miss on todays processors?

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: bit boards - what is betwen

Post by wgarvin » Mon Dec 03, 2012 10:03 pm

Why not AND together two masks? Even if they both come from lookup tables, those will be really small (e.g. 512 bytes each) and you ought to be able to keep them in L1 all the time.

With a bit of care, you can probably get routine(s) that are inclusive or exclusive at each end, or produce the opposite mask, etc. all with the same cost of two loads (or two shifts) and one logic-op.

Post Reply