more STL code for Stockfish

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: more STL code for Stockfish

Post by mcostalba »

Rein Halbersma wrote:Just check the asm to make sure.
Ok, I have rewritten the code to _almost_ compile:

Code: Select all

/// generate<MV_LEGAL> computes a complete list of legal moves in the current position

struct is_not_legal_move&#58; public std&#58;&#58;binary_function<Position, MoveStack, bool>
&#123;
      bool operator&#40;)&#40;const Position& pos, MoveStack& cur&#41; const
      &#123;
         return !pos.pl_move_is_legal&#40;cur.move, pos.pinned_pieces&#40;pos.side_to_move&#40;)));
      &#125;
&#125;;

template<>
MoveStack* generate<MV_LEGAL>&#40;const Position& pos, MoveStack* mlist&#41; &#123;

  assert&#40;pos.is_ok&#40;));
 
  MoveStack* last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41;
                                   &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;;

  return std&#58;&#58;remove_if&#40;mlist, last, std&#58;&#58;bind1st&#40;is_not_legal_move&#40;), pos&#41;);
&#125; 
There is still a little detail left out: bind1st() makes an internal copy of Position !!! This is really a no-no.

Code does not compile just because copy c'tor of Position is declared private as a safe guard against hidden copies, and for a reason I would say ;-)
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: more STL code for Stockfish

Post by Rein Halbersma »

mcostalba wrote:
Rein Halbersma wrote:Just check the asm to make sure.
Ok, I have rewritten the code to _almost_ compile:

Code: Select all

/// generate<MV_LEGAL> computes a complete list of legal moves in the current position

struct is_not_legal_move&#58; public std&#58;&#58;binary_function<Position, MoveStack, bool>
&#123;
      bool operator&#40;)&#40;const Position& pos, MoveStack& cur&#41; const
      &#123;
         return !pos.pl_move_is_legal&#40;cur.move, pos.pinned_pieces&#40;pos.side_to_move&#40;)));
      &#125;
&#125;;

template<>
MoveStack* generate<MV_LEGAL>&#40;const Position& pos, MoveStack* mlist&#41; &#123;

  assert&#40;pos.is_ok&#40;));
 
  MoveStack* last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41;
                                   &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;;

  return std&#58;&#58;remove_if&#40;mlist, last, std&#58;&#58;not1&#40;std&#58;&#58;bind1st&#40;is_legal_move&#40;), pos&#41;() ));

&#125; 
There is still a little detail left out: bind1st() makes an internal copy of Position !!! This is really a no-no.

Code does not compile just because copy c'tor of Position is declared private as a safe guard against hidden copies, and for a reason I would say ;-)
Sorry, my post had 2 missing () pairs: one for the std::bind1st and one for the std::not1 function object. That's why it didn't compile. (Code corrected above) These 2 functors are passed-by-value (2 copies), but the position is passed-by-const-reference! The private constructor has nothing to do with this. Just let me know if the above compiles.

For reference about the function objects:
http://www.cplusplus.com/reference/std/ ... l/bind1st/
http://www.cplusplus.com/reference/std/functional/not1/
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: more STL code for Stockfish

Post by mcostalba »

Rein Halbersma wrote:Just let me know if the above compiles.
No sorry it doesn't, there are many errors, the trivial is that you decalred struct is_not_legal_move and then used is_legal_move(), perhasp _I_ have helped creating this when I simplified the original code removing std::not1.

But also with this fixed I still get a good chunk of encrypted error messages ;-)
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: more STL code for Stockfish

Post by Rein Halbersma »

mcostalba wrote:
Rein Halbersma wrote:Just let me know if the above compiles.
No sorry it doesn't, there are many errors, the trivial is that you decalred struct is_not_legal_move and then used is_legal_move(), perhasp _I_ have helped creating this when I simplified the original code removing std::not1.

But also with this fixed I still get a good chunk of encrypted error messages ;-)
OK Marco, the code below compiles (I checked using out-of-the-box VC++ 2010) but you will not be happy! :twisted:

Code: Select all

class Position &#123;

  //Position&#40;)  &#123;&#125;; // default ctor will not be generated anyway because of user-defined ctors
  //Position&#40;const Position& pos&#41;; // std&#58;&#58;bind1st generates copy-constructor

public&#58;
  // rest as current
  ...
&#125;;

/// generate<MV_LEGAL> computes a complete list of legal moves in the current position 
#include <algorithm> 
#include <functional> 

struct is_legal_move&#58; public std&#58;&#58;binary_function<Position, MoveStack, bool> 
&#123; 
      bool operator&#40;)&#40;const Position& pos, const MoveStack& cur&#41; const
      &#123; 
         return pos.pl_move_is_legal&#40;cur.move, pos.pinned_pieces&#40;pos.side_to_move&#40;))); 
      &#125; 
&#125;; 

template<> 
MoveStack* generate<MV_LEGAL>&#40;const Position& pos, MoveStack* mlist&#41; &#123; 

  assert&#40;pos.is_ok&#40;)); 
  
  MoveStack* last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41; 
                                   &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;; 

  return std&#58;&#58;remove_if&#40;mlist, last, std&#58;&#58;not1&#40;std&#58;&#58;bind1st&#40;is_legal_move&#40;), pos&#41;)); 
&#125; 

Changes: removed explicit suppression of default ctor. This is unnecessary because the compiler will never generate these for you as long as you define at least one constructor yourself. Even if you define a new position by accident somewhere, your code will not compile.

However, the copy constructor will be automatically generated whenever it is needed, even if you have a self-defined constructor, so that original comment was warranted. But I also removed explicit suppression of the copy constructor because it turns out that std::bindst1 has this nasty code:

Code: Select all

		// TEMPLATE FUNCTION bind1st
template<class _Fn2,
	class _Ty> inline
	binder1st<_Fn2> bind1st&#40;const _Fn2& _Func, const _Ty& _Left&#41;
		&#123;	// return a binder1st functor adapter
		typename _Fn2&#58;&#58;first_argument_type _Val&#40;_Left&#41;;
		return (_STD binder1st<_Fn2>(_Func, _Val&#41;);
		&#125;
Here, MSVC++ declares a copy Val_ of _Left just to be able to express the return type of the function object. In reality, this temporary will not be created and fully optimized away, but the compiler first needs the copy constructor to make this happen :roll:

Finally I changed is_legal_move to take a const-reference to MoveStack to make the argument deduction on the std::remove_if easier (it got confused what kind of iterator was needed).

So... (deep breath) if you are brave enough to compile and look at the assembly, you will see that no needless copies arise.

Rein
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: more STL code for Stockfish

Post by mcostalba »

Rein Halbersma wrote: So... (deep breath) if you are brave enough to compile and look at the assembly, you will see that no needless copies arise.
Yes, thanks ! It works as expected and also temporary is optimized away in the produced assembly....but I don't think I am brave enough to commit it ;-), as I guess you can imagine

P.S: Apart form removing useless Position default c'tor declaration that, as you correctly pointed out, is not needed.
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: more STL code for Stockfish

Post by Rein Halbersma »

mcostalba wrote:
Rein Halbersma wrote: So... (deep breath) if you are brave enough to compile and look at the assembly, you will see that no needless copies arise.
Yes, thanks ! It works as expected and also temporary is optimized away in the produced assembly....but I don't think I am brave enough to commit it ;-), as I guess you can imagine

P.S: Apart form removing useless Position default c'tor declaration that, as you correctly pointed out, is not needed.
Look ma, no copy constructor needed! :P

Code: Select all

/// generate<MV_LEGAL> computes a complete list of legal moves in the current position 
#include <algorithm> 
#include <functional> 

// overload of pl_move_is_legal&#40;) with a self-supplied pinned pieces Bitboard
bool Position&#58;&#58;pl_move_is_legal&#40;const MoveStack& m&#41; const
&#123; 
        return pl_move_is_legal&#40;m.move, pinned_pieces&#40;side_to_move&#40;))); 
&#125;

template<> 
MoveStack* generate<MV_LEGAL>&#40;const Position& pos, MoveStack* mlist&#41; &#123; 

  assert&#40;pos.is_ok&#40;)); 
  
  MoveStack* last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41; 
                                   &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;; 

  return std&#58;&#58;remove_if&#40;mlist, last, std&#58;&#58;bind&#40;std&#58;&#58;mem_fun&#40;&Position&#58;&#58;pl_move_is_legal&#41;, &pos, std&#58;&#58;placeholders&#58;&#58;_1&#41;); 
&#125; 
The above code overloads pl_move_is_legal for a single Position argument, and passes this to std::bind, together with a pointer to the position. This fixes all worries. Except of course that std::bind is strictly speaking only available for C++0x. But for the last 5 years or so, this code would have worked on MSVC, g++ and Intel through the library std::tr1, so I have no idea if you would consider this OK or not.
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: more STL code for Stockfish

Post by mcostalba »

Rein Halbersma wrote: Look ma, no copy constructor needed! :P
:-) :-)

Yes, it works as expected (after changing the logic in discarding _non_ legal moves), below the full working patch:

Code: Select all

--- a/src/movegen.cpp
+++ b/src/movegen.cpp
@@ -16,6 +16,8 @@
   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http&#58;//www.gnu.org/licenses/>.
 */
+#include <algorithm>
+#include <functional>
 
 #include <cassert>
 
@@ -312,25 +314,20 @@ MoveStack* generate<MV_EVASION>&#40;const Position& pos, MoveStack* mlist&#41; &#123;
 
 /// generate<MV_LEGAL> computes a complete list of legal moves in the current position
 
+bool Position&#58;&#58;pl_move_is_not_legal&#40;const MoveStack& m&#41; const
+&#123;
+  return !pl_move_is_legal&#40;m.move, pinned_pieces&#40;side_to_move&#40;)));
+&#125;
+
 template<>
 MoveStack* generate<MV_LEGAL>&#40;const Position& pos, MoveStack* mlist&#41; &#123;
 
   assert&#40;pos.is_ok&#40;));
 
-  MoveStack *last, *cur = mlist;
-  Bitboard pinned = pos.pinned_pieces&#40;pos.side_to_move&#40;));
-
-  last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41;
-                        &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;;
-
-  // Remove illegal moves from the list
-  while &#40;cur != last&#41;
-      if (!pos.pl_move_is_legal&#40;cur->move, pinned&#41;)
-          cur->move = (--last&#41;->move;
-      else
-          cur++;
+  MoveStack* last = pos.in_check&#40;) ? generate<MV_EVASION>&#40;pos, mlist&#41;
+                                   &#58; generate<MV_NON_EVASION>&#40;pos, mlist&#41;;
 
-  return last;
+  return std&#58;&#58;remove_if&#40;mlist, last, std&#58;&#58;tr1&#58;&#58;bind&#40;std&#58;&#58;mem_fun&#40;&Position&#58;&#58;pl_move_is_not_legal&#41;, &pos, std&#58;&#58;tr1&#58;&#58;placeholders&#58;&#58;_1&#41;);
 &#125;
 
 
diff --git a/src/position.h b/src/position.h
index 9ed7239..14d82a3 100644
--- a/src/position.h
+++ b/src/position.h
@@ -153,6 +153,7 @@ public&#58;
 
   // Properties of moves
   bool pl_move_is_legal&#40;Move m, Bitboard pinned&#41; const;
+  bool pl_move_is_not_legal&#40;const MoveStack& m&#41; const;
   bool move_is_pl&#40;const Move m&#41; const;
   bool move_gives_check&#40;Move m, const CheckInfo& ci&#41; const;
   bool move_is_capture&#40;Move m&#41; const;

Unfortunatly complier is not smart enough to move out of the loop the pinned_pieces() call:

Code: Select all

bool Position&#58;&#58;pl_move_is_not_legal&#40;const MoveStack& m&#41; const
&#123;
004251A0  push        ebp  
004251A1  mov         ebp,esp 
004251A3  and         esp,0FFFFFFF8h 
004251A6  push        ecx  
004251A7  push        esi  
004251A8  mov         esi,ecx 
  return !pl_move_is_legal&#40;m.move, pinned_pieces&#40;side_to_move&#40;)));
004251AA  mov         eax,dword ptr &#91;esi+0F00h&#93; 
004251B0  push        eax  
004251B1  mov         edx,esi 
004251B3  call        Position&#58;&#58;hidden_checkers<1> &#40;40F520h&#41;  <--- HERE !
004251B8  mov         ecx,dword ptr &#91;m&#93; 
004251BB  push        edx  
004251BC  push        eax  
004251BD  mov         eax,dword ptr &#91;ecx&#93; 
004251BF  mov         ecx,esi 
004251C1  call        Position&#58;&#58;pl_move_is_legal &#40;41D310h&#41; 
004251C6  xor         edx,edx 
004251C8  test        al,al 
004251CA  sete        dl   
004251CD  mov         al,dl 
&#125;
004251CF  pop         esi  
004251D0  mov         esp,ebp 
004251D2  pop         ebp  
004251D3  ret         4  

And I am not smart enough to read the new code comfortably and with good confidence I am understanding what I see :-)

But I have to say this is one of the most interesting threads on the languages (apart from the polls ;-) ) that I have seen here. It is a discussion with real code examples, not words, as I like more !
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: more STL code for Stockfish

Post by Rein Halbersma »

mcostalba wrote: And I am not smart enough to read the new code comfortably and with good confidence I am understanding what I see :-)

But I have to say this is one of the most interesting threads on the languages (apart from the polls ;-) ) that I have seen here. It is a discussion with real code examples, not words, as I like more !
So conclusion of this thread: STL algorithms can make your life easier, but beware of hidden use of copy ctors (even if they are optimized away in practice). Explicitly circumventing the copy ctor for position by doing std::mem_fun and pointer trickery, will introduce another hidden copy of pinnend_pieces.

BTW, if you want to be really safe on hidden position copies, you should also privately declare (but not define) an assignment operator=(const Position&). In Boost this is done by privately inheriting from boost::noncopyable.
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: more STL code for Stockfish

Post by mcostalba »

Rein Halbersma wrote: BTW, if you want to be really safe on hidden position copies, you should also privately declare (but not define) an assignment operator=(const Position&). In Boost this is done by privately inheriting from boost::noncopyable.
Yes this is another "defect" you found, I missed this (that is instead correctly added elsewhere, see tt.h) probably because there was a time when the assignment operator was actually used...so we removed the need but forgot to add the safe guard in class declaration.
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: more STL code for Stockfish

Post by bob »

One quick note. The new code seems to do a lot more memory references than the old code, at first glance.

Those are always slow, even when coming from cache, when compared to just register accesses.