DIRECT BITBOARD MOVEGENERATION

[Desperado]

hi.

i am testing bitboard generating methods.
The last work i did was experimenting with magic bitboards,
and now some tests on the Hyberbola-Q idea.

So if you look at the return value of the function below,
can someone explain to me why the factor can raise like
in the comments made to the function ?
Can i do something against ?

Code: Select all

#define BB&#40;SQ64&#41;   (&#40;BTB&#41;1<<&#40;SQ64&#41;)
#define LO64&#40;SQ64&#41; &#40;BB&#40;SQ64&#41;-1&#41;
#define HI64&#40;SQ64&#41; (&#40;bH8-BB&#40;SQ64&#41;)<<1&#41;

BTB rook_trial&#40;const BTB occ,const SQR_T sq64&#41;
	&#123;
	 
	 static const BTB cfle = &#40;bR1|bR8&#41;;
	 static const BTB crnk = &#40;bAF|bHF&#41;;

	 static BTB fle,rnk,lo,hi;
	 
	 //FILE

	 &#40;lo = LO64&#40;sq64&#41; & &#40;occ|cfle&#41; & msk.msk_file&#91;sq64&#93;) ? lo &#58; lo = BB&#40;sq64&#41;;
	 &#40;hi = HI64&#40;sq64&#41; & &#40;occ|cfle&#41; & msk.msk_file&#91;sq64&#93;) ? hi &#58; hi = BB&#40;sq64&#41;;
	
	 hi &= -hi;
	 lo  = BB&#40;bsr64&#40;lo&#41;);
	 fle = ((&#40;hi<<1&#41;-lo&#41; & msk.msk_file&#91;sq64&#93;);


	 //RANK

	 &#40;lo = LO64&#40;sq64&#41; & &#40;occ|crnk&#41; & msk.msk_rank&#91;sq64&#93;) ? lo &#58; lo = BB&#40;sq64&#41;;
	 &#40;hi = HI64&#40;sq64&#41; & &#40;occ|crnk&#41; & msk.msk_rank&#91;sq64&#93;) ? hi &#58; hi = BB&#40;sq64&#41;;
	
	 hi &= -hi;
	 lo  = BB&#40;bsr64&#40;lo&#41;);
	 rnk = ((&#40;hi<<1&#41;-lo&#41; & msk.msk_rank&#91;sq64&#93;);

	 //return&#40;rnk&#41;; //performs factor 1
	 //return&#40;fle&#41;; //performs factor 1

	 return&#40;fle|rnk&#41;; //performs about factor 20...? why not 2 or 3 ???
	&#125;

(all file/rank masks are excluding the square itself)

Anyway i would be happy if someone would made some interesting
annotations about the code, so we may discuss some ideas,pros,cons THX
I will also try to ask (edit: haha answer of course) any questions about the code.
(my goal at the moment is to have an acceptable direct computing method, without any lookups)

PS: of course i would be happy if someone tries out, and tells me if the performence is well or not(independent on the "performance problem" i ve descriped above)

[Gerd Isenberg]

1+1=20?
May be the optimizing compiler is as obfuscated as I am after watching your code
If you make separate routines for file and rank, and "or" them together, what happens then? Non inlined versus inlined? Some more comments on the code appreciated, explain each line in words. I found statements like

Code: Select all

( a = expression) ? a : (a = otherExpression );

rather confusing and would prefere

Code: Select all

a = expression ? expression : otherExpression;

[Desperado]

thx for reply.

ok, the conditional operator isnt my best friend .

i will add some description for the "file" code. The rank
is analoge as you can see.

i am suprised too, about "1+1 = 20". ??? that s why i posted it. i cannot
explain, therefore i asked for any help.

And yes, i tried out things you mentioned. same effect...

Well, all i can add at the moment is, that independent on inline/non-inlining, seperate routines/one routine...
put the results together -> 1+1 = 20!

Code: Select all

#define BB&#40;SQ64&#41;   (&#40;BTB&#41;1<<&#40;SQ64&#41;)
#define LO64&#40;SQ64&#41; &#40;BB&#40;SQ64&#41;-1&#41;
#define HI64&#40;SQ64&#41; (&#40;bH8-BB&#40;SQ64&#41;)<<1&#41;

	 //FILE

	 //******************************************************************************
	 //*																		    
	 //* STATEMENTS																	 
	 //*																			
	 //*																			
	 //* STEP_1&#58;																	
	 //*																			
	 //*																			
	 //*																			
	 //* LO64&#40;sq64&#41;	-> bitboard all bits set below sq-index &#40;excluding sq&#41;			
	 //* HI64&#40;sq64&#41;	-> bitboard all bits set above sq-index &#40;excluding sq&#41;			
	 //* occ|cfle	-> makes sure file has at least set the bit on rank8 and rank1	
	 //* msk_file	-> all bit set, excluding the sq with the slider&#40;rook&#41; on file	
	 //*																			
	 //* lo			-> all occupancy bits on file below sq							
	 //*				-> if lo == 0 the rook is on border. So border-square is set
	 //* hi			-> same as for lo, but bits above sq.							
	 //*																			
	 //******************************************************************************

	 &#40;lo = LO64&#40;sq64&#41; & &#40;occ|cfle&#41; & msk.msk_file&#91;sq64&#93;) ? lo &#58; lo = BB&#40;sq64&#41;;
	 &#40;hi = HI64&#40;sq64&#41; & &#40;occ|cfle&#41; & msk.msk_file&#91;sq64&#93;) ? hi &#58; hi = BB&#40;sq64&#41;;
	
	 //******************************************************************************
	 //*
	 //*STEP_2&#58;
	 //*
	 //*hi&#58;  -> extract the lsb-board of all bits above sq
	 //*lo&#58;  -> extract the msb-board of all bits below sq
	 //*fle&#58; -> connect by sub
	 //*fle&#58; -> &#40;hi<<1&#41; is just for including the nn-blocker.
	 //******************************************************************************

	 hi &= -hi;									//lsb of bits above sq
	 lo  = BB&#40;bsr64&#40;lo&#41;);						//msb of bits below sq
	 fle = ((&#40;hi<<1&#41;-lo&#41; & msk.msk_file&#91;sq64&#93;); //connecting bits 

pls, what do you mean with _the optimizing compiler is as obfuscated_ ?

[rvida]

Im a PASCAL guy, I dont use C, but let me guess...

If you return ONLY "rnk", compiler will optimize away whole "fle" calculation.
If you return ONLY "fle", compiler will optimize away whole "rnk" calculation.

If you return logical OR of both, it must include both calculations.

[Gerd Isenberg]

Thanks, I understand your code now. Your conditional assignments made me confused, and may also hard to understand for the optimizing compiler to produce reasonable code with x86 cmov instruction for instance. Also the semantics of cfle and crnk was unclear first.

I would write it that way (and think about a branchless solution).

Code: Select all

(lo = LO64(sq64) & (occ|cfle) & msk.msk_file[sq64]) ? lo : lo = BB(sq64); 

lo = LO64(sq64) & (occ|cfle) & msk.msk_file[sq64];
if ( lo == 0 ) lo = BB(sq64);

The idea is fine. To subtract the most significant occupied bit of the negative (low) ray from the least significant occupied bit of the positive (high) ray times two, but I fear it is too expensive due to four conditional branches per rook or bishop, likely hard to predict if used for multiple white and black rooks. Usually with reasonable small branchless code, one may improve ipc if processing independent stuff in parallel, so that in best case
1 + 1 = 1
however branches avoid parallel scheduling, and branches may become much more expensive, if they are too complicated to predict in combination. But still
1 + 1 = 20
seems a bit strange. How do you measure the timing?

[Desperado]

hi rvida. think excactly that happens, but doesnt explain the jump in time.

hi gerd. ok maybe somethink with "branching" code causes the problem.
An indicator for that is, that i first coded it like you suggested!.
That was worse than using the conditional operator.

maybe by using the operator a second time, the compiler cannot optimize
the same way?! i will try out, and try a solution avoiding any branches.

For measuring the time i just used the below code.
So far now, have to go to work... til later.

Code: Select all

	 srand((unsigned)time(NULL));

	 for&#40;UI_16 i=0;i<1024;i++) &#123;r&#91;i&#93; = rnd64&#40;);s&#91;i&#93;=rand&#40;)%64;r&#91;i&#93;|=BB&#40;s&#91;i&#93;);&#125;

	 start = clock&#40;);
	 for&#40;UI_64 i=0;i<1500000000;i++)
		&#123;
		 bb = rook_trial&#40;r&#91;i&1023&#93;,s&#91;i&1023&#93;);
		&#125;
	 end = clock&#40;);

	 print_bb&#40;bb&#41;;
	 printf&#40;"\nTIME&#58; %d ",end-start,x&#41;;getchar&#40;);

[Gerd Isenberg]

hi rvida. think excactly that happens, but doesnt explain the jump in time.

hi gerd. ok maybe somethink with "branching" code causes the problem.
An indicator for that is, that i first coded it like you suggested!.
That was worse than using the conditional operator.

maybe by using the operator a second time, the compiler cannot optimize
the same way?! i will try out, and try a solution avoiding any branches.

For measuring the time i just used the below code.
So far now, have to go to work... til later.

Code: Select all

	 srand((unsigned)time(NULL));

	 for&#40;UI_16 i=0;i<1024;i++) &#123;r&#91;i&#93; = rnd64&#40;);s&#91;i&#93;=rand&#40;)%64;r&#91;i&#93;|=BB&#40;s&#91;i&#93;);&#125;

	 start = clock&#40;);
	 for&#40;UI_64 i=0;i<1500000000;i++)
		&#123;
		 bb = rook_trial&#40;r&#91;i&1023&#93;,s&#91;i&1023&#93;);
		&#125;
	 end = clock&#40;);

	 print_bb&#40;bb&#41;;
	 printf&#40;"\nTIME&#58; %d ",end-start,x&#41;;getchar&#40;);

Such loop test sucks. Compiler likely unrolls the loop and there are code L1 issues. Better use Agner Fog's Test programs for measuring clock cycles and performance monitoring.

On the routine. A branchless, untested proposal:

Code: Select all

U64 fileAttacks(U64 occ, enumSquare sq) {
{
	U64 high = smsk&#91;sq&#93;.fileMaskEx & occ & (-2ULL << sq&#41;; 
	U64 low  = smsk&#91;sq&#93;.fileMaskEx & occ & (&#40;1ULL << sq&#41; - 1&#41;;
	high  = high & -high;          // ls1b of high &#40;if any&#41;
	low   = -1ULL << bsr64&#40;low|1&#41;; // ms1b of low &#40;at least bit zero&#41;
	return smsk&#91;sq&#93;.fileMaskEx & &#40;2*high+low&#41;; // lea
&#125;

Even if this works, simple count the operations compared to bswap hyperbola quintessence:

Code: Select all

U64 fileAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].fileMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= 1ULL << sq;
   reverse -= _byteswap_uint64&#40;1ULL << sq&#41;; 
   forward ^= _byteswap_uint64&#40;reverse&#41;;
   forward &= smsk&#91;sq&#93;.fileMaskEx;
   return forward;
&#125;

The advantage is that it works for all lines, while the bswap does not cover ranks, which are cheap by lookup anyway.

[Gerd Isenberg]

For measuring the time i just used the below code.
So far now, have to go to work... til later.

Code: Select all

	 srand((unsigned)time(NULL));

	 for&#40;UI_16 i=0;i<1024;i++) &#123;r&#91;i&#93; = rnd64&#40;);s&#91;i&#93;=rand&#40;)%64;r&#91;i&#93;|=BB&#40;s&#91;i&#93;);&#125;

	 start = clock&#40;);
	 for&#40;UI_64 i=0;i<1500000000;i++)
		&#123;
		 bb = rook_trial&#40;r&#91;i&1023&#93;,s&#91;i&1023&#93;);
		&#125;
	 end = clock&#40;);

	 print_bb&#40;bb&#41;;
	 printf&#40;"\nTIME&#58; %d ",end-start,x&#41;;getchar&#40;);

A smart compiler would even optimize the whole loop away, to only execute the last index. better use bb ^= rook_trial.

[wgarvin]

For measuring the time i just used the below code.
So far now, have to go to work... til later.

Code: Select all

	 srand((unsigned)time(NULL));

	 for&#40;UI_16 i=0;i<1024;i++) &#123;r&#91;i&#93; = rnd64&#40;);s&#91;i&#93;=rand&#40;)%64;r&#91;i&#93;|=BB&#40;s&#91;i&#93;);&#125;

	 start = clock&#40;);
	 for&#40;UI_64 i=0;i<1500000000;i++)
		&#123;
		 bb = rook_trial&#40;r&#91;i&1023&#93;,s&#91;i&1023&#93;);
		&#125;
	 end = clock&#40;);

	 print_bb&#40;bb&#41;;
	 printf&#40;"\nTIME&#58; %d ",end-start,x&#41;;getchar&#40;);

A smart compiler would even optimize the whole loop away, to only execute the last index. better use bb ^= rook_trial.

That might not be a good way to test it either, because it introduces a loop-carried dependence where there isn't really a need for one.

My suggestion is to replace "bb" with a volatile global variable and use an ordinary assignment (not the ^= assignment). The compiler will not be able to optimize away the store instruction, but it should be able to optimize everything else. (At least on 64-bit systems... does the compiler generate slower code for a volatile int64 than a non-volatile one 32-bit systems? I have no idea.) Another possibility is to invoke the rook_trial a bunch of times within each loop (maybe 8 times?) and store each return value in one of 8 different temporaries. Then there is a loop-carried dependence for each temporary, but there is lots of other calculation to do between def and use so they won't limit the throughput.

[Edit: actually it doesn't read from bb inside the loop other than the read-modify-write of the ^=, so maybe it would be fine that way. If you want to be on the safe side, you could do maybe 2 or 4 calls to rook_trial and use bb1 ^= rook_trial, bb2 ^= rook_trial, etc.]

[Gerd Isenberg]

On the routine. A branchless, untested proposal:

Code: Select all

U64 fileAttacks(U64 occ, enumSquare sq) {
{
	U64 high = smsk&#91;sq&#93;.fileMaskEx & occ & (-2ULL << sq&#41;; 
	U64 low  = smsk&#91;sq&#93;.fileMaskEx & occ & (&#40;1ULL << sq&#41; - 1&#41;;
	high  = high & -high;          // ls1b of high &#40;if any&#41;
	low   = -1ULL << bsr64&#40;low|1&#41;; // ms1b of low &#40;at least bit zero&#41;
	return smsk&#91;sq&#93;.fileMaskEx & &#40;2*high+low&#41;; // lea
&#125;

Even if this works, simple count the operations compared to bswap hyperbola quintessence:

The advantage is that it works for all lines, while the bswap does not cover ranks, which are cheap by lookup anyway.

For intels with fast bsr but slower bswap, this approach might be not that bad as I initially thought. Alternatively one can save 5 ops by upper/lower lookups from the very same cacheline to end up with 9 ops per line (file, rank, dia, antidia) and two independent instruction chains until the final lea/and:

Code: Select all

U64 lineAttacks(U64 occ, enumLine line, enumSquare sq) {
   U64 low, high;
   low  = smsk[sq][line].lower & occ;
   high = smsk[sq][line].upper & occ;
   low  = -C64&#40;1&#41; << bsr64&#40;low|1&#41;; // ms1b of low &#40;at least bit zero&#41; -> -low
   high = high & -high;            // ls1b of high &#40;if any&#41;
   return smsk&#91;sq&#93;&#91;line&#93;.maskEx & &#40;2*high+low&#41;; // lea option due to add -low
&#125; 

This is how it works, e.g. on a file from rook d4:

Code: Select all

occupancy              fileMaskEx(d4)           occupancy d-file
 . . . 1 . 1 . .       . . . 1 . . . .          . . . 1 . . . . 
 1 . 1 . . 1 1 .       . . . 1 . . . .          . . . . . . . . 
 . 1 . 1 . . . 1       . . . 1 . . . .          . . . 1 . . . . 
 . . . . . 1 . .       . . . 1 . . . .          . . . . . . . . 
 . 1 . 1 . . . .   &   . . . . . . . .    =     . . . R . . . .   
 . . . . . . 1 .       . . . 1 . . . .          . . . . . . . . 
 1 1 . 1 . 1 . 1       . . . 1 . . . .          . . . 1 . . . . 
 . . . 1 1 . 1 .       . . . 1 . . . .          . . . 1 . . . . 
                       
occupancy d-file      occupancy d-file    
 . . . 1 . . . .       . . . 1 . . . .   
 . . . . . . . .       . . . . . . . .    
 . . . 1 . . . .       . . . 1 . . . .    
 . . . . . . . .       . . . . . . . .      
 . . . R . . . .       . . . R . . . .        
 . . . . . . . .       . . . . . . . .      
 . . . 1 . . . .       . . . 1 . . . .      
 . . . 1 . . . .       . . . 1 . . . .         
                                                      
high = -2 << d4       low = &#40;1<<d4&#41;-1  
 1 1 1 1 1 1 1 1       . . . . . . . .    
 1 1 1 1 1 1 1 1       . . . . . . . .          
 1 1 1 1 1 1 1 1       . . . . . . . .      
 1 1 1 1 1 1 1 1       . . . . . . . .       
 . . . . 1 1 1 1       1 1 1 . . . . .      
 . . . . . . . .       1 1 1 1 1 1 1 1         
 . . . . . . . .       1 1 1 1 1 1 1 1         
 . . . . . . . .       1 1 1 1 1 1 1 1          
                                             
occupancy high         occupancy low                   
 . . . 1 . . . .       . . . . . . . .     
 . . . . . . . .       . . . . . . . .        
 . . . 1 . . . .       . . . . . . . .          
 . . . . . . . .       . . . . . . . .      
 . . . . . . . .       . . . . . . . .      
 . . . . . . . .       . . . . . . . .       
 . . . . . . . .       . . . 1 . . . .         
 . . . . . . . .       . . . 1 . . . .  
                                           
LS1B high              MS1B low&#58; 1 << bsr&#40;low|1&#41;       
 . . . . . . . .       . . . . . . . .    
 . . . . . . . .       . . . . . . . .      
 . . . 1 . . . .       . . . . . . . .      
 . . . . . . . .       . . . . . . . .     
 . . . . . . . .       . . . . . . . .      
 . . . . . . . .       . . . . . . . .        
 . . . . . . . .       . . . 1 . . . .       
 . . . . . . . .       1 . . . . . . .           
                                           
2* LS1B high           MS1B low              
 . . . . . . . .       . . . . . . . .         . . . . . . . .     
 . . . . . . . .       . . . . . . . .         . . . . . . . .    
 . . . . 1 . . .       . . . . . . . .         1 1 1 1 . . . .    
 . . . . . . . .       . . . . . . . .         1 1 1 1 1 1 1 1   
 . . . . . . . .   -   . . . . . . . .    =    1 1 1 1 1 1 1 1       
 . . . . . . . .       . . . . . . . .         1 1 1 1 1 1 1 1    
 . . . . . . . .       . . . 1 . . . .         . . . 1 1 1 1 1 
 . . . . . . . .       . . . . . . . .         . . . . . . . .  
          
                          
2*high-low             fileMaskEx              fileAttacks
 . . . . . . . .       . . . 1 . . . .         . . . . . . . . 
 . . . . . . . .       . . . 1 . . . .         . . . . . . . . 
 1 1 1 1 . . . .       . . . 1 . . . .         . . . 1 . . . . 
 1 1 1 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . . 
 1 1 1 1 1 1 1 1   &   . . . . . . . .    =    . . . . . . . .   
 1 1 1 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . . 
 . . . 1 1 1 1 1       . . . 1 . . . .         . . . 1 . . . . 
 . . . . . . . .       . . . 1 . . . .         . . . . . . . .