Page 1 of 3

### Fastest pawn quiet move generation I was able to come with

Posted: Sat Jun 10, 2017 4:54 pm
Sure someone can improve this, but I think is really fast.

Code: Select all

``````b = bitboard of pawns
increment = 8 or 16

uint8_t cas;
uint8_t casd;
switch &#40;popcount&#40;b&#41;) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 6&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 5&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 4&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 3&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
cas = lsb&#40;b&#41;;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 0&#58;
return ml;
default&#58; //> 8 pawns for strange games or positions
altremovpeo2 &#58;
if &#40;b == 0&#41;
return ml;
cas = lsb&#40;b&#41;;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
b &= b - 1;
goto altremovpeo2;
&#125;``````

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 5:03 pm
Could do for brevity:

Code: Select all

``````case 8&#58;
case 7&#58;
case 6&#58;
...
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
...
``````

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 5:10 pm
cdani wrote:Sure someone can improve this, but I think is really fast.

Code: Select all

``````b = bitboard of pawns
increment = 8 or 16
...
``````
you unrolled the loop, how much faster it's respect to the original loop?
And the most important question, how much elo you gained agaisnt a more readable loop?

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 5:33 pm
"switch - case" is slow construction

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 5:35 pm
cdani wrote:Sure someone can improve this, but I think is really fast.
Well, a Duff machine
But where do you check that the squares in front of the pawns are empty?

Code: Select all

``````pawns & shift_backward&#40;~occupied&#41;
``````
What was the performance gain versus a loop? (and overall speed gain?)

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 6:08 pm
Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:

Code: Select all

``````switch&#40;&#40;p = popcount&#40;b&#41;)) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;7&#93;.moviment = MakeMove&#40;cas, casd&#41;;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;6&#93;.moviment = MakeMove&#40;cas, casd&#41;;
...
case 0&#58;
return ml += p;
``````
It is questionable whether an optimizer could do that from your code.

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 6:13 pm
hgm wrote:It is questionable whether an optimizer could do that from your code.
The optimizer will certainly not generate code that stores moves in the opposite order.

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 6:15 pm
hgm wrote:Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:

Code: Select all

``````switch&#40;&#40;p = popcount&#40;b&#41;)) &#123;
case 8&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;7&#93;.moviment = MakeMove&#40;cas, casd&#41;;
case 7&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml&#91;6&#93;.moviment = MakeMove&#40;cas, casd&#41;;
...
case 0&#58;
return ml += p;
``````
It is questionable whether an optimizer could do that from your code.
Hmm, I liked your original suggestion:

Code: Select all

``````ml += &#40;p = popcount&#40;b&#41;);
switch&#40;p&#41; &#123;
case 8&#58;
....
ml&#91;-8&#93;.m = ...;
...
case 0&#58;
return ml;
&#125;
``````

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 6:23 pm
mkchan wrote:Could do for brevity:

Code: Select all

``````case 8&#58;
case 7&#58;
case 6&#58;
...
case 2&#58;
cas = lsb&#40;b&#41;;
b &= b - 1;
casd = cas + increment;
ml->moviment = MakeMove&#40;cas, casd&#41;;
ml++;
case 1&#58;
...
``````
This does not work, as the idea is that case 8 executes the code in case 8 + code in case 7 + code in case 6..., and is not doing this with your code.

Kotlov wrote:"switch - case" is slow construction
Yes, but with jump tables is quite fast.

Code: Select all

``````	switch &#40;popcount&#40;b&#41;) &#123;
000000013FC0826B  movzx       ecx,al
000000013FC0826E  cmp         ecx,8
000000013FC08271  ja          peons_moviments_quiets_o_sense_peoalpas+13Bh &#40;013FC0839Bh&#41;
000000013FC08277  mov         eax,ecx
000000013FC08279  lea         rcx,&#91;__rg_language &#40;013FBF0000h&#41;&#93;
000000013FC08280  mov         r9d,dword ptr &#91;rcx+rax*4+183C8h&#93;
000000013FC0828B  jmp         r9
``````
mar wrote: But where do you check that the squares in front of the pawns are empty?

Code: Select all

``````pawns & shift_backward&#40;~occupied&#41;
``````
Yes, b variable has only pawns that can advance.
elcabesa wrote: you unrolled the loop, how much faster it's respect to the original loop?
And the most important question, how much elo you gained agaisnt a more readable loop?
mar wrote: What was the performance gain versus a loop? (and overall speed gain?)
Of course minimal, something like 1100000 n/s to 1100500 n/s to give an idea. Is more for fun than for anything other, and also is interesting to share and to have other ideas. Any elo gain is due to accumulating a few of those things.
hgm wrote:Rather than incrementing ml all the time, you could have stored the moves in the opposite order, and hard-code the offset w.r.t. the inintial ml:
mar wrote: Hmm, I liked your original suggestion:
Nice one! I will try, sure is even better! Thanks.

### Re: Fastest pawn quiet move generation I was able to come wi

Posted: Sat Jun 10, 2017 6:51 pm
mar wrote:Hmm, I liked your original suggestion:

Code: Select all

``````ml += &#40;p = popcount&#40;b&#41;);
switch&#40;p&#41; &#123;
case 8&#58;
....
ml&#91;-8&#93;.m = ...;
...
case 0&#58;
return ml;
&#125;
``````
OK, that is something the optimizer probably could do, in theory.