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.
bit boards - what is betwen
Moderators: hgm, Rebel, chrisw
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
bit boards - what is betwen
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: bit boards - what is betwen
Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: bit boards - what is betwen
That is an excellent idea, similar to the mailbox attack array indexed by the difference in the squares location.Gerd Isenberg wrote:Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.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.
Thanks,
Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
-
- Posts: 568
- Joined: Tue Dec 12, 2006 10:10 am
- Full name: Gary Linscott
Re: bit boards - what is betwen
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.Gerd Isenberg wrote:Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.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.
Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: bit boards - what is betwen
What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: bit boards - what is betwen
I meant without memory access but I would settle for anything that produced a speedup on modern processors.hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
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.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: bit boards - what is betwen
Why would a 64x64 array be slower than executing more code with smaller array access?Don wrote:I meant without memory access but I would settle for anything that produced a speedup on modern processors.hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
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.
The real problem of modern processors is mainly decode speed of instructions.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: bit boards - what is betwen
Its a matter of correct initialization, to make the rotate left approach with 240 element lookup work, f.i.:gladius wrote: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.Gerd Isenberg wrote:Indexing an array of 240 bitboards by 0x88 square difference and rotate might we worth a try.
Github commit here: https://github.com/glinscott/Stockfish/ ... b79b7606c4.
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}
Last edited by Gerd Isenberg on Mon Dec 03, 2012 10:13 pm, edited 1 time in total.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: bit boards - what is betwen
Really? I thought still branches and L1, L2 misses - at least in chess programs.diep wrote:Why would a 64x64 array be slower than executing more code with smaller array access?Don wrote:I meant without memory access but I would settle for anything that produced a speedup on modern processors.hgm wrote:What do you mean by 'without memory access', then? Surely indexing a table counts as a memory access...
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.
The real problem of modern processors is mainly decode speed of instructions.
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?
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: bit boards - what is betwen
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.
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.