From: Marco Costalba Date: Tue, 24 Nov 2009 12:39:47 +0000 (+0100) Subject: Speed up sorting of non-captures X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=55b5b03273e9740b63663ee84a17788c5424eec3 Speed up sorting of non-captures Becasue we have a lot of zero scores (around 30% of moves) it is a good idea to do a couple a presorting loops across the move list and shuffle the moves a bit so that with a small effort we end up with 3 groups of moves: positives scores, zero scores and negative scores. We have two advantages 1) We don't need to sort zero scores 2) Sort two small groups is faster then sort a single big one Speed up is of about 2% Because equal scored moves could be reordered in a different way this is not a "no functional change" although I have verified the output list is always correctly sorted. Signed-off-by: Marco Costalba --- diff --git a/src/move.h b/src/move.h index d70bb81e..9702d9fb 100644 --- a/src/move.h +++ b/src/move.h @@ -65,9 +65,9 @@ struct MoveStack { // Note that operator< is set up such that sorting will be in descending order inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; } -// Our stable insertion sort in range [firstMove, lastMove), platform independent +// An helper insertion sort implementation template -inline void sort_moves(T* firstMove, T* lastMove) +inline void insertion_sort(T* firstMove, T* lastMove) { T value; T *cur, *p, *d; @@ -86,6 +86,59 @@ inline void sort_moves(T* firstMove, T* lastMove) } } +// Our dedicated sort in range [firstMove, lastMove), it is well +// tuned for non-captures where we have a lot of zero scored moves. +template +inline void sort_moves(T* firstMove, T* lastMove) +{ + T tmp; + T *p, *d; + + d = lastMove; + p = firstMove - 1; + + d->score = -1; // right guard + + // Split positives vs non-positives + do { + while ((++p)->score > 0); + + if (p != d) + { + while (--d != p && d->score <= 0); + + tmp = *p; + *p = *d; + *d = tmp; + } + + } while (p != d); + + // Sort positives + insertion_sort(firstMove, p); + + d = lastMove; + p--; + + // Split zero vs negatives + do { + while ((++p)->score == 0); + + if (p != d) + { + while (--d != p && d->score < 0); + + tmp = *p; + *p = *d; + *d = tmp; + } + + } while (p != d); + + // Sort negatives + insertion_sort(p, lastMove); +} + // Picks up the best move in range [curMove, lastMove), one per cycle. // It is faster then sorting all the moves in advance when moves are few, // as normally are the possible captures. Note that is not a stable alghoritm.