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 <mcostalba@gmail.com>

diff --git a/src/move.h b/src/move.h
index 71def812d85743708d1a6ed22622aba696c2f6d0..0cf6ac6301b4baa350788e6352b57b7098a8d3c5 100644 (file)
--- 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<typename T>
-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<T>(firstMove, p);
-    insertion_sort<T>(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 650218f48f468f4d36bbae33a6167c219c890d70..582978e69d0c3f1fb2c6535c82d71f564cc85aa7 100644 (file)
--- 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 b2bfb5d1d167c36efdeedd47c23427d93abe7036..69cf6ff67404ea740850aa169e9f8f8dcb90f542 100644 (file)
--- 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];
 };