From e2e249eabd2493e2bb9e5e017aafaac074a706ef Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 10 Oct 2009 15:29:43 +0100 Subject: [PATCH] Use std::stable_sort() instead of std::sort() Standard does not mandate std::sort() to be stable, so we can have, and actually do have different node count on different platforms. So use the platform independent std::stable_sort() and gain same functionality on any platform (Windows, Unix, Mac OS) and with any compiler (MSVC, gcc or Intel C++). This sort is teoretically slower, but profiling shows only a very minimal drop in performance, probably due to the fact that the set to sort is very small, mainly only captures and with less frequency non-captures, anyhow we are talking of 30-40 moves in the worst average case. Sorting alghortims are build to work on thousands or even milions of elements. With such small sets performance difference seems not noticable. After 999 games at 1+0 Mod vs Orig +234 =523 -242 -3 ELO Signed-off-by: Marco Costalba --- src/move.h | 2 +- src/movepick.cpp | 10 +++++----- src/ucioption.cpp | 2 +- 3 files changed, 7 insertions(+), 7 deletions(-) diff --git a/src/move.h b/src/move.h index 672eade6..03df770d 100644 --- a/src/move.h +++ b/src/move.h @@ -62,7 +62,7 @@ struct MoveStack { int score; }; -// Note that operator< is set up such that std::sort() will sort in descending order +// Note that operator< is set up such that std::stable_sort() will sort in descending order inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; } diff --git a/src/movepick.cpp b/src/movepick.cpp index ea435026..0dd44bbd 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -123,7 +123,7 @@ void MovePicker::go_next_phase() { case PH_GOOD_CAPTURES: lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, lastMove); + std::stable_sort(moves, lastMove); return; case PH_KILLERS: @@ -134,7 +134,7 @@ void MovePicker::go_next_phase() { case PH_NONCAPTURES: lastMove = generate_noncaptures(pos, moves); score_noncaptures(); - std::sort(moves, lastMove); + std::stable_sort(moves, lastMove); return; case PH_BAD_CAPTURES: @@ -142,20 +142,20 @@ void MovePicker::go_next_phase() { // to get SEE move ordering. curMove = badCaptures; lastMove = lastBadCapture; - std::sort(badCaptures, lastMove); + std::stable_sort(badCaptures, lastMove); return; case PH_EVASIONS: assert(pos.is_check()); lastMove = generate_evasions(pos, moves, pinned); score_evasions(); - std::sort(moves, lastMove); + std::stable_sort(moves, lastMove); return; case PH_QCAPTURES: lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, lastMove); + std::stable_sort(moves, lastMove); return; case PH_QCHECKS: diff --git a/src/ucioption.cpp b/src/ucioption.cpp index 1b866554..6e727954 100644 --- a/src/ucioption.cpp +++ b/src/ucioption.cpp @@ -210,7 +210,7 @@ void print_uci_options() { for (Options::const_iterator it = options.begin(); it != options.end(); ++it) vec.push_back(it->second); - std::sort(vec.begin(), vec.end()); + std::stable_sort(vec.begin(), vec.end()); for (std::vector