bit boards - what is betwen

[Don]

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.

[Gerd Isenberg]

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.

[Don]

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

[gladius]

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.

[hgm]

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

[Don]

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.

[diep]

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]

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.

[Gerd Isenberg]

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]

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.