From c7866a4215c31d7d0af8e8550fbf8c13f6ea1d1a Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 5 Feb 2010 18:17:52 +0100 Subject: [PATCH] Delay sorting of negative scored non-captures We can do this only when needed, if we get a cut-off before we skip sorting entirely. This reduces sorting time of about 20%. No functional change. Signed-off-by: Marco Costalba --- src/move.h | 6 +++--- src/movepick.cpp | 7 ++++++- src/movepick.h | 2 +- 3 files changed, 10 insertions(+), 5 deletions(-) diff --git a/src/move.h b/src/move.h index 71def812..0cf6ac63 100644 --- a/src/move.h +++ b/src/move.h @@ -89,7 +89,7 @@ inline void insertion_sort(T* firstMove, T* lastMove) // Our dedicated sort in range [firstMove, lastMove), first splits // positive scores from ramining then order seaprately the two sets. template -inline void sort_moves(T* firstMove, T* lastMove) +inline void sort_moves(T* firstMove, T* lastMove, T** lastPositive) { T tmp; T *p, *d; @@ -114,9 +114,9 @@ inline void sort_moves(T* firstMove, T* lastMove) } while (p != d); - // Sort positives and non-positives separately + // Sort just positive scored moves, remaining only when we get there insertion_sort(firstMove, p); - insertion_sort(p, lastMove); + *lastPositive = p; } // Picks up the best move in range [curMove, lastMove), one per cycle. diff --git a/src/movepick.cpp b/src/movepick.cpp index 650218f4..582978e6 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -136,7 +136,7 @@ void MovePicker::go_next_phase() { case PH_NONCAPTURES: lastMove = generate_noncaptures(pos, moves); score_noncaptures(); - sort_moves(moves, lastMove); + sort_moves(moves, lastMove, &lastGoodNonCapture); return; case PH_BAD_CAPTURES: @@ -305,6 +305,11 @@ Move MovePicker::get_next_move() { break; case PH_NONCAPTURES: + + // Sort negative scored moves only when we get there + if (curMove == lastGoodNonCapture) + insertion_sort(lastGoodNonCapture, lastMove); + move = (curMove++)->move; if ( move != ttMoves[0].move && move != ttMoves[1].move diff --git a/src/movepick.h b/src/movepick.h index b2bfb5d1..69cf6ff6 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -64,7 +64,7 @@ private: MoveStack ttMoves[2], killers[2]; int phase; const uint8_t* phasePtr; - MoveStack *curMove, *lastMove, *lastBadCapture; + MoveStack *curMove, *lastMove, *lastGoodNonCapture, *lastBadCapture; Bitboard pinned; MoveStack moves[256], badCaptures[64]; }; -- 2.39.2