more STL code for Stockfish

[Rein Halbersma]

Microsoft's std::swap is found in their <utility> header, and looks like this (I fixed the indenting):

Code: Select all

// TEMPLATE FUNCTION swap &#40;from <algorithm>)
template<class _Ty> inline
void swap&#40;_Ty& _Left, _Ty& _Right&#41;
&#123;
    // exchange values stored at _Left and _Right
    if (&_Left != &_Right&#41;
    &#123;
        // different, worth swapping
        _Ty _Tmp = _Left;
        _Left = _Right;
        _Right = _Tmp;
    &#125;
&#125;

Bloody hell! This conditional swap was what I proposed at first, and Marco removed the if() statement, only for MSVC to reintroduce it again! Nice catch!

[wgarvin]

Bloody hell! This conditional swap was what I proposed at first, and Marco removed the if() statement, only for MSVC to reintroduce it again! Nice catch!

SGI's description of std::swap does not mention anything about checking to see if the arguments have the same object identity (i.e. address) or not. However, it does say you can specialize std::swap for custom types for efficiency reasons.

[2] This implementation of swap makes one call to a copy constructor and two calls to an assignment operator; roughly, then, it should be expected to take about the same amount of time as three assignments. In many cases, however, it is possible to write a specialized version of swap that is far more efficient. Consider, for example, swapping two vector<double>s each of which has N elements. The unspecialized version requires 3*N assignments of double, but a specialized version requires only nine pointer assignments. This is important because swap is used as a primitive operation in many other STL algorithms, and because containers of containers (list<vector<char> >, for example) are very common. The STL includes specialized versions of swap for all container classes. User-defined types should also provide specialized versions of swap whenever it is possible to write one that is more efficient than the general version.

I also stumbled on this page from 2001 which looks interesting, though possibly out-dated:
http://accu.org/index.php/journals/466

[mcostalba]

PS just words, no code this time. If you want to see code, PM me and I can give you access to my repository for my draughts engine.

I have wrote you a pm.

[mcostalba]

Bloody hell! This conditional swap was what I proposed at first, and Marco removed the if() statement, only for MSVC to reintroduce it again! Nice catch!

SGI's description of std::swap does not mention anything about checking to see if the arguments have the same object identity (i.e. address) or not. However, it does say you can specialize std::swap for custom types for efficiency reasons.

My guess that this guard is needed in case the assignment operator of a complex type is implemented with some form of memcpy().

In this case the standard says that if source and destination overlaps behavior is undefined.

Regarding specializing std::swap, also if it is technically possible, I'd consider polluting std namespace a bad guideline.

[Rein Halbersma]

Bloody hell! This conditional swap was what I proposed at first, and Marco removed the if() statement, only for MSVC to reintroduce it again! Nice catch!

SGI's description of std::swap does not mention anything about checking to see if the arguments have the same object identity (i.e. address) or not. However, it does say you can specialize std::swap for custom types for efficiency reasons.

My guess that this guard is needed in case the assignment operator of a complex type is implemented with some form of memcpy().

In this case the standard says that if source and destination overlaps behavior is undefined.

Regarding specializing std::swap, also if it is technically possible, I'd consider polluting std namespace a bad guideline.

The standard C++ idiom is to provide a member function swap and a non-member function swap like this:

Code: Select all

class MyClass
{
public:
  void Swap( MyClass& );
  // ...
};

// NOTE: Not in namespace std.
swap( MyClass& a, MyClass& b )
{
  a.Swap( b );
}

There is an elaborate item on this in Scott Meyers' Effective C++, also explaining the name-lookup details (std::swap should not even come into the picture with the above definition).

[mcostalba]

There is an elaborate item on this in Scott Meyers' Effective C++, also explaining the name-lookup details (std::swap should not even come into the picture with the above definition).

Thanks for clarification. But I would consider this difficult for me: what if there is some using std somewhere in the code or if you use swap with some type that is not exactly the one in the signature but an implicitly converted one ? In this case the tempeltized version whould be preferred.

Name-lookup in C++ is one of the most difficult topics of the language, at least for me, and I feel more conformtable to avoid messing with its subtleties. So better define something like my_swap() and go with that. It is not very "elegant" but if you are not a _very_ skilled developer name loookup could bite you hard when you try to push it to the limits.

[Rein Halbersma]

There is an elaborate item on this in Scott Meyers' Effective C++, also explaining the name-lookup details (std::swap should not even come into the picture with the above definition).

Thanks for clarification. But I would consider this difficult for me: what if there is some using std somewhere in the code or if you use swap with some type that is not exactly the one in the signature but an implicitly converted one ? In this case the tempeltized version whould be preferred.

Name-lookup in C++ is one of the most difficult topics of the language, at least for me, and I feel more conformtable to avoid messing with its subtleties. So better define something like my_swap() and go with that. It is not very "elegant" but if you are not a _very_ skilled developer name loookup could bite you hard when you try to push it to the limits.

Fortunately, the item is online somewhere:

http://codeidol.com/cpp/effective-cpp/D ... wing-swap/

This should relieve your concerns

[Rein Halbersma]

OK, time for some more code! A small opportunity to introduce std::remove_if in generate<MV_LEGAL>

Code: Select all

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

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++;

  return last;
&#125;

should be equivalent to this

Code: Select all

/// 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, 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, pos&#41;));
&#125;

This nicely hides the temporaries and pinned pieces Bitboard. Of course, the std::not1 can be removed if the is_legal_move is changed to is_illegal_move and returns !pos.pl_move_is_legal.

[mcostalba]

OK, time for some more code! A small opportunity to introduce std::remove_if in generate<MV_LEGAL>

Unfortunatly pos.pinned_pieces() is a consuming function (not so slow but neither a pure getter), so with your code you end up calculating for each move. A solution is of course to calculate once in struct is_legal_move c'tor and store there as a memeber, but perhaps is becoming too complex so that the original version is easier.

BTW as you may have seen in dev snapshots there is a new API to access legal moves (now through an object and no more a function).

[Rein Halbersma]

OK, time for some more code! A small opportunity to introduce std::remove_if in generate<MV_LEGAL>

Unfortunatly pos.pinned_pieces() is a consuming function (not so slow but neither a pure getter), so with your code you end up calculating for each move. A solution is of course to calculate once in struct is_legal_move c'tor and store there as a memeber, but perhaps is becoming too complex so that the original version is easier.

BTW as you may have seen in dev snapshots there is a new API to access legal moves (now through an object and no more a function).

Usually with these kind of situations, it's good not to pessimize too prematurely. My experience is that the STL implementers know what they are being paid for!

In this case, std::remove_if is such a simple algorithm that the entire code is most likely completely inlined. Plus the Position is passed as a const-reference, so the compiler should detect that pos.pinnned_pieces() is a loop invariant. There's a very good chance that it gets optimized away into the loop initialization. Just check the asm to make sure.