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 wrote:
Microsoft's std::swap is found in their <utility> header, and looks like this (I fixed the indenting):Code: Select all
// TEMPLATE FUNCTION swap (from <algorithm>) template<class _Ty> inline void swap(_Ty& _Left, _Ty& _Right) { // exchange values stored at _Left and _Right if (&_Left != &_Right) { // different, worth swapping _Ty _Tmp = _Left; _Left = _Right; _Right = _Tmp; } }
more STL code for Stockfish
Moderators: hgm, Rebel, chrisw
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: more STL code for Stockfish
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: more STL code for Stockfish
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.Rein Halbersma wrote: 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!
I also stumbled on this page from 2001 which looks interesting, though possibly out-dated:[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.
http://accu.org/index.php/journals/466
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: more STL code for Stockfish
I have wrote you a pm.Rein Halbersma wrote: 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.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: more STL code for Stockfish
My guess that this guard is needed in case the assignment operator of a complex type is implemented with some form of memcpy().wgarvin wrote: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.Rein Halbersma wrote: 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!
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.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: more STL code for Stockfish
The standard C++ idiom is to provide a member function swap and a non-member function swap like this:mcostalba wrote:My guess that this guard is needed in case the assignment operator of a complex type is implemented with some form of memcpy().wgarvin wrote: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.Rein Halbersma wrote: 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!
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.
Code: Select all
class MyClass
{
public:
void Swap( MyClass& );
// ...
};
// NOTE: Not in namespace std.
swap( MyClass& a, MyClass& b )
{
a.Swap( b );
}
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: more STL code for Stockfish
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.Rein Halbersma wrote: 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).
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.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: more STL code for Stockfish
Fortunately, the item is online somewhere:mcostalba wrote: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.Rein Halbersma wrote: 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).
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.
http://codeidol.com/cpp/effective-cpp/D ... wing-swap/
This should relieve your concerns
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: more STL code for Stockfish
OK, time for some more code! A small opportunity to introduce std::remove_if in generate<MV_LEGAL>
should be equivalent to this
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.
Code: Select all
/// generate<MV_LEGAL> computes a complete list of legal moves in the current position
template<>
MoveStack* generate<MV_LEGAL>(const Position& pos, MoveStack* mlist) {
assert(pos.is_ok());
MoveStack *last, *cur = mlist;
Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
last = pos.in_check() ? generate<MV_EVASION>(pos, mlist)
: generate<MV_NON_EVASION>(pos, mlist);
// Remove illegal moves from the list
while (cur != last)
if (!pos.pl_move_is_legal(cur->move, pinned))
cur->move = (--last)->move;
else
cur++;
return last;
}
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: public std::binary_function<Position, MoveStack, bool>
{
bool operator()(const Position& pos, MoveStack* cur) const
{
return pos.pl_move_is_legal(cur->move, pos.pinned_pieces(pos.side_to_move()));
}
}
template<>
MoveStack* generate<MV_LEGAL>(const Position& pos, MoveStack* mlist) {
assert(pos.is_ok());
MoveStack* last = pos.in_check() ? generate<MV_EVASION>(pos, mlist)
: generate<MV_NON_EVASION>(pos, mlist);
return std::remove_if(mlist, last, std::not1(std::bind1st(is_legal_move, pos)));
}
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: more STL code for Stockfish
Rein Halbersma wrote: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).
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: more STL code for Stockfish
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!mcostalba wrote:Rein Halbersma wrote: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).
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.