Use a timer to avoid polling
authorMarco Costalba <mcostalba@gmail.com>
Sat, 5 Nov 2011 10:19:21 +0000 (11:19 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 5 Nov 2011 17:19:38 +0000 (18:19 +0100)
The timer will be fired asynchronously to handle
time management flags, while other threads are
searching.

This implementation uses a thread waiting on a
timed condition variable instead of real timers.
This approach allow to reduce platform dependant
code to a minimum and also is the most portable given
that timers libraries are very different among platforms
and also the best ones are not compatible with olds
Windows.

Also retire the now unused polling code.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/lock.h
src/misc.cpp
src/misc.h
src/search.cpp
src/search.h
src/thread.cpp
src/thread.h
src/timeman.cpp

index b64293cf71f8c014e36bd61722b44dca2c5b37bc..e05db4696c2d4ac46b8cb1c1dbc6264635463426 100644 (file)
@@ -35,6 +35,7 @@ typedef pthread_cond_t WaitCondition;
 #  define cond_init(x) pthread_cond_init(x, NULL)
 #  define cond_signal(x) pthread_cond_signal(x)
 #  define cond_wait(x,y) pthread_cond_wait(x,y)
+#  define cond_timedwait(x,y,z) pthread_cond_timedwait(x,y,z)
 
 #else
 
@@ -57,7 +58,8 @@ typedef CONDITION_VARIABLE WaitCondition;
 #  define cond_destroy(x) (x)
 #  define cond_init(x) InitializeConditionVariable(x)
 #  define cond_signal(x) WakeConditionVariable(x)
-#  define cond_wait(x,y) SleepConditionVariableSRW(x, y, INFINITE,0)
+#  define cond_wait(x,y) SleepConditionVariableSRW(x,y,INFINITE,0)
+#  define cond_timedwait(x,y,z) SleepConditionVariableSRW(x,y,z,0)
 
 // Fallback solution to build for Windows XP and older versions, note that
 // cond_wait() is racy between lock_release() and WaitForSingleObject().
@@ -74,6 +76,8 @@ typedef HANDLE WaitCondition;
 #  define cond_destroy(x) CloseHandle(*x)
 #  define cond_signal(x) SetEvent(*x)
 #  define cond_wait(x,y) { lock_release(y); WaitForSingleObject(*x, INFINITE); lock_grab(y); }
+#  define cond_timedwait(x,y,z) { lock_release(y); WaitForSingleObject(*x,z); lock_grab(y); }
+
 #endif
 
 #endif
index 610cc2402778768a54d4125268c0cd9aa5883ac4..5e851f12f6ded08dfdebb1c967e12bd822b30367 100644 (file)
@@ -175,6 +175,39 @@ int cpu_count() {
 }
 
 
+/// timed_wait() waits for msec milliseconds. It is mainly an helper to wrap
+/// conversion from milliseconds to struct timespec, as used by pthreads.
+
+#if defined(_MSC_VER)
+
+void timed_wait(WaitCondition* sleepCond, Lock* sleepLock, int msec) {
+  cond_timedwait(sleepCond, sleepLock, msec);
+}
+
+#else
+
+void timed_wait(WaitCondition* sleepCond, Lock* sleepLock, int msec) {
+
+  struct timeval t;
+  struct timespec abstime;
+
+  gettimeofday(&t, NULL);
+
+  abstime.tv_sec = t.tv_sec + (msec / 1000);
+  abstime.tv_nsec = (t.tv_usec + (msec % 1000) * 1000) * 1000;
+
+  if (abstime.tv_nsec > 1000000000LL)
+  {
+      abstime.tv_sec += 1;
+      abstime.tv_nsec -= 1000000000LL;
+  }
+
+  cond_timedwait(sleepCond, sleepLock, &abstime);
+}
+
+#endif
+
+
 /// prefetch() preloads the given address in L1/L2 cache. This is a non
 /// blocking function and do not stalls the CPU waiting for data to be
 /// loaded from memory, that can be quite slow.
index 0c89922bfeb9112fc8da7626c1b160c31653dd32..92b97461faee9e883b6fbc85adcd22c35d731212 100644 (file)
 
 #include <fstream>
 #include <string>
+
+#include "lock.h"
 #include "types.h"
 
 extern const std::string engine_name();
 extern const std::string engine_authors();
 extern int get_system_time();
 extern int cpu_count();
+extern void timed_wait(WaitCondition*, Lock*, int);
 extern void prefetch(char* addr);
 
 extern void dbg_hit_on(bool b);
index 320f480c2df854ac575ab4f4776f120d5c933a84..fefc886424e9935116191a27c44594b7ad6d887b 100644 (file)
@@ -170,11 +170,6 @@ namespace {
   int SkillLevel;
   bool SkillLevelEnabled;
 
-  // Node counters, used only by thread[0] but try to keep in different cache
-  // lines (64 bytes each) from the heavy multi-thread read accessed variables.
-  int NodesSincePoll;
-  int NodesBetweenPolls = 30000;
-
   // History table
   History H;
 
@@ -199,13 +194,12 @@ namespace {
   void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
   void do_skill_level(Move* best, Move* ponder);
 
-  int current_search_time(int set = 0);
+  int elapsed_search_time(int set = 0);
   string score_to_uci(Value v, Value alpha = -VALUE_INFINITE, Value beta = VALUE_INFINITE);
   string speed_to_uci(int64_t nodes);
   string pv_to_uci(const Move pv[], int pvNum, bool chess960);
   string pretty_pv(Position& pos, int depth, Value score, int time, Move pv[]);
   string depth_to_uci(Depth depth);
-  void poll(const Position& pos);
   void wait_for_stop_or_ponderhit();
 
   // MovePickerExt template class extends MovePicker and allows to choose at compile
@@ -363,24 +357,13 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) {
 
   // Initialize global search-related variables
   StopOnPonderhit = StopRequest = QuitRequest = AspirationFailLow = false;
-  NodesSincePoll = 0;
-  current_search_time(get_system_time());
+  elapsed_search_time(get_system_time());
   Limits = limits;
   TimeMgr.init(Limits, pos.startpos_ply_counter());
 
   // Set output steram in normal or chess960 mode
   cout << set960(pos.is_chess960());
 
-  // Set best NodesBetweenPolls interval to avoid lagging under time pressure
-  if (Limits.maxNodes)
-      NodesBetweenPolls = std::min(Limits.maxNodes, 30000);
-  else if (Limits.time && Limits.time < 1000)
-      NodesBetweenPolls = 1000;
-  else if (Limits.time && Limits.time < 5000)
-      NodesBetweenPolls = 5000;
-  else
-      NodesBetweenPolls = 30000;
-
   // Look for a book move
   if (Options["OwnBook"].value<bool>())
   {
@@ -398,6 +381,12 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) {
       }
   }
 
+  // Set best timer interval to avoid lagging under time pressure
+  if (TimeMgr.available_time())
+      Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 8, 20)));
+  else
+      Threads.set_timer(100);
+
   // Read UCI options
   UCIMultiPV = Options["MultiPV"].value<int>();
   SkillLevel = Options["Skill Level"].value<int>();
@@ -447,14 +436,16 @@ bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]) {
   Move ponderMove = MOVE_NONE;
   Move bestMove = id_loop(pos, searchMoves, &ponderMove);
 
+  Threads.set_timer(0);
+
   // Write final search statistics and close log file
   if (Options["Use Search Log"].value<bool>())
   {
-      int t = current_search_time();
+      int e = elapsed_search_time();
 
       Log log(Options["Search Log Filename"].value<string>());
       log << "Nodes: "          << pos.nodes_searched()
-          << "\nNodes/second: " << (t > 0 ? pos.nodes_searched() * 1000 / t : 0)
+          << "\nNodes/second: " << (e > 0 ? pos.nodes_searched() * 1000 / e : 0)
           << "\nBest move: "    << move_to_san(pos, bestMove);
 
       StateInfo st;
@@ -591,7 +582,7 @@ namespace {
                 // if we have a fail high/low and we are deep in the search. UCI
                 // protocol requires to send all the PV lines also if are still
                 // to be searched and so refer to the previous search's score.
-                if ((value > alpha && value < beta) || current_search_time() > 2000)
+                if ((value > alpha && value < beta) || elapsed_search_time() > 2000)
                     for (int i = 0; i < std::min(UCIMultiPV, (int)Rml.size()); i++)
                     {
                         bool updated = (i <= MultiPVIdx);
@@ -644,7 +635,7 @@ namespace {
         if (Options["Use Search Log"].value<bool>())
         {
             Log log(Options["Search Log Filename"].value<string>());
-            log << pretty_pv(pos, depth, value, current_search_time(), &Rml[0].pv[0]) << endl;
+            log << pretty_pv(pos, depth, value, elapsed_search_time(), &Rml[0].pv[0]) << endl;
         }
 
         // Init easyMove at first iteration or drop it if differs from the best move
@@ -663,9 +654,9 @@ namespace {
                 && easyMove == bestMove
                 && (   Rml.size() == 1
                     ||(   Rml[0].nodes > (pos.nodes_searched() * 85) / 100
-                       && current_search_time() > TimeMgr.available_time() / 16)
+                       && elapsed_search_time() > TimeMgr.available_time() / 16)
                     ||(   Rml[0].nodes > (pos.nodes_searched() * 98) / 100
-                       && current_search_time() > TimeMgr.available_time() / 32)))
+                       && elapsed_search_time() > TimeMgr.available_time() / 32)))
                 StopRequest = true;
 
             // Take in account some extra time if the best move has changed
@@ -674,7 +665,7 @@ namespace {
 
             // Stop search if most of available time is already consumed. We probably don't
             // have enough time to search the first move at the next iteration anyway.
-            if (current_search_time() > (TimeMgr.available_time() * 62) / 100)
+            if (elapsed_search_time() > (TimeMgr.available_time() * 62) / 100)
                 StopRequest = true;
 
             // If we are allowed to ponder do not stop the search now but keep pondering
@@ -743,7 +734,7 @@ namespace {
     if (PvNode && thread.maxPly < ss->ply)
         thread.maxPly = ss->ply;
 
-    // Step 1. Initialize node and poll. Polling can abort search
+    // Step 1. Initialize node
     if (!SpNode)
     {
         ss->currentMove = ss->bestMove = threatMove = (ss+1)->excludedMove = MOVE_NONE;
@@ -759,12 +750,6 @@ namespace {
         goto split_point_start;
     }
 
-    if (pos.thread() == 0 && ++NodesSincePoll > NodesBetweenPolls)
-    {
-        NodesSincePoll = 0;
-        poll(pos);
-    }
-
     // Step 2. Check for aborted search and immediate draw
     if ((   StopRequest
          || pos.is_draw<false>()
@@ -1031,7 +1016,7 @@ split_point_start: // At split points actual search starts from here
           nodes = pos.nodes_searched();
 
           // For long searches send current move info to GUI
-          if (pos.thread() == 0 && current_search_time() > 2000)
+          if (pos.thread() == 0 && elapsed_search_time() > 2000)
               cout << "info" << depth_to_uci(depth)
                    << " currmove " << move
                    << " currmovenumber " << moveCount + MultiPVIdx << endl;
@@ -1745,7 +1730,7 @@ split_point_start: // At split points actual search starts from here
   // current_search_time() returns the number of milliseconds which have passed
   // since the beginning of the current search.
 
-  int current_search_time(int set) {
+  int elapsed_search_time(int set) {
 
     static int searchStartTime;
 
@@ -1784,7 +1769,7 @@ split_point_start: // At split points actual search starts from here
   string speed_to_uci(int64_t nodes) {
 
     std::stringstream s;
-    int t = current_search_time();
+    int t = elapsed_search_time();
 
     s << " nodes " << nodes
       << " nps " << (t > 0 ? int(nodes * 1000 / t) : 0)
@@ -1910,49 +1895,6 @@ split_point_start: // At split points actual search starts from here
     return s.str();
   }
 
-  // poll() performs two different functions: It polls for user input, and it
-  // looks at the time consumed so far and decides if it's time to abort the
-  // search.
-
-  void poll(const Position& pos) {
-
-    static int lastInfoTime;
-    int t = current_search_time();
-
-    // Print search information
-    if (t < 1000)
-        lastInfoTime = 0;
-
-    else if (lastInfoTime > t)
-        // HACK: Must be a new search where we searched less than
-        // NodesBetweenPolls nodes during the first second of search.
-        lastInfoTime = 0;
-
-    else if (t - lastInfoTime >= 1000)
-    {
-        lastInfoTime = t;
-
-        dbg_print_mean();
-        dbg_print_hit_rate();
-    }
-
-    // Should we stop the search?
-    if (Limits.ponder)
-        return;
-
-    bool stillAtFirstMove =    FirstRootMove
-                           && !AspirationFailLow
-                           &&  t > TimeMgr.available_time();
-
-    bool noMoreTime =   t > TimeMgr.maximum_time()
-                     || stillAtFirstMove;
-
-    if (   (Limits.useTimeManagement() && noMoreTime)
-        || (Limits.maxTime && t >= Limits.maxTime)
-        || (Limits.maxNodes && pos.nodes_searched() >= Limits.maxNodes)) // FIXME
-        StopRequest = true;
-  }
-
 
   // wait_for_stop_or_ponderhit() is called when the maximum depth is reached
   // while the program is pondering. The point is to work around a wrinkle in
@@ -2225,10 +2167,10 @@ void Thread::idle_loop(SplitPoint* sp) {
 }
 
 
-// ThreadsManager::do_uci_async_cmd() processes the commands from GUI received
-// by listener thread while the other threads are searching.
+// do_uci_async_cmd() is called by listener thread when in async mode and 'cmd'
+// input line is received from the GUI.
 
-void ThreadsManager::do_uci_async_cmd(const std::string& cmd) {
+void do_uci_async_cmd(const std::string& cmd) {
 
   if (cmd == "quit")
   {
@@ -2254,3 +2196,37 @@ void ThreadsManager::do_uci_async_cmd(const std::string& cmd) {
           StopRequest = true;
   }
 }
+
+
+// do_timer_event() is called by the timer thread when the timer triggers
+
+void do_timer_event() {
+
+  static int lastInfoTime;
+  int e = elapsed_search_time();
+
+  // Print debug information every second
+  if (get_system_time() - lastInfoTime >= 1000)
+  {
+      lastInfoTime = get_system_time();
+
+      dbg_print_mean();
+      dbg_print_hit_rate();
+  }
+
+  // Should we stop the search?
+  if (Limits.ponder)
+      return;
+
+  bool stillAtFirstMove =    FirstRootMove
+                         && !AspirationFailLow
+                         &&  e > TimeMgr.available_time();
+
+  bool noMoreTime =   e > TimeMgr.maximum_time()
+                   || stillAtFirstMove;
+
+  if (   (Limits.useTimeManagement() && noMoreTime)
+      || (Limits.maxTime && e >= Limits.maxTime)
+         /* missing nodes limit */ ) // FIXME
+      StopRequest = true;
+}
index 1688534b59b0782ac0de81f59a63f49853e0a194..757aeb002ae110896c7f89d0b0afb019da1e523e 100644 (file)
@@ -67,5 +67,7 @@ struct SearchLimits {
 extern void init_search();
 extern int64_t perft(Position& pos, Depth depth);
 extern bool think(Position& pos, const SearchLimits& limits, Move searchMoves[]);
+extern void do_uci_async_cmd(const std::string& cmd);
+extern void do_timer_event();
 
 #endif // !defined(SEARCH_H_INCLUDED)
index 49a598f1d41da631a8416794686af24ff8f77079..df76dcca7a2e1fe990c4859bd23219afcc8188f8 100644 (file)
@@ -19,6 +19,7 @@
 
 #include <iostream>
 
+#include "search.h"
 #include "thread.h"
 #include "ucioption.h"
 
@@ -28,7 +29,8 @@ namespace { extern "C" {
 
  // start_routine() is the C function which is called when a new thread
  // is launched. It simply calls idle_loop() of the supplied thread. The
- // last thread is dedicated to I/O and so runs in listener_loop().
+ // last two threads are dedicated to read input from GUI and to mimic a
+ // timer, so they run in listener_loop() and timer_loop() respectively.
 
 #if defined(_MSC_VER)
   DWORD WINAPI start_routine(LPVOID thread) {
@@ -38,6 +40,9 @@ namespace { extern "C" {
 
     if (((Thread*)thread)->threadID == MAX_THREADS)
         ((Thread*)thread)->listener_loop();
+
+    else if (((Thread*)thread)->threadID == MAX_THREADS + 1)
+        ((Thread*)thread)->timer_loop();
     else
         ((Thread*)thread)->idle_loop(NULL);
 
@@ -149,7 +154,7 @@ void ThreadsManager::init() {
   lock_init(&threadsLock);
 
   // Initialize sleep and split point locks
-  for (int i = 0; i <= MAX_THREADS; i++)
+  for (int i = 0; i < MAX_THREADS + 2; i++)
   {
       lock_init(&threads[i].sleepLock);
       cond_init(&threads[i].sleepCond);
@@ -165,7 +170,7 @@ void ThreadsManager::init() {
 
   // Create and launch all the threads but the main that is already running,
   // threads will go immediately to sleep.
-  for (int i = 1; i <= MAX_THREADS; i++)
+  for (int i = 1; i < MAX_THREADS + 2; i++)
   {
       threads[i].is_searching = false;
       threads[i].threadID = i;
@@ -190,7 +195,7 @@ void ThreadsManager::init() {
 
 void ThreadsManager::exit() {
 
-  for (int i = 0; i <= MAX_THREADS; i++)
+  for (int i = 0; i < MAX_THREADS + 2; i++)
   {
       if (i != 0)
       {
@@ -349,10 +354,39 @@ template Value ThreadsManager::split<false>(Position&, SearchStack*, Value, Valu
 template Value ThreadsManager::split<true>(Position&, SearchStack*, Value, Value, Value, Depth, Move, int, MovePicker*, int);
 
 
-// Thread::listner_loop() is where the last thread, used for IO, waits for input.
-// Input is read in sync with main thread (that blocks) when is_searching is set
-// to false, otherwise IO thread reads any input asynchronously and processes
-// the input line calling do_uci_async_cmd().
+// Thread::timer_loop() is where the timer thread waits maxPly milliseconds
+// and then calls do_timer_event().
+
+void Thread::timer_loop() {
+
+  while (!do_terminate)
+  {
+      lock_grab(&sleepLock);
+      timed_wait(&sleepCond, &sleepLock, maxPly ? maxPly : INT_MAX);
+      lock_release(&sleepLock);
+      do_timer_event();
+  }
+}
+
+
+// ThreadsManager::set_timer() is used to set the timer to trigger after msec
+// milliseconds. If msec is 0 then timer is stopped.
+
+void ThreadsManager::set_timer(int msec) {
+
+  Thread& timer = threads[MAX_THREADS + 1];
+
+  lock_grab(&timer.sleepLock);
+  timer.maxPly = msec;
+  cond_signal(&timer.sleepCond); // Wake up and restart the timer
+  lock_release(&timer.sleepLock);
+}
+
+
+// Thread::listener_loop() is where the listener thread, used for I/O, waits for
+// input. When is_searching is false then input is read in sync with main thread
+// (that blocks), otherwise the listener thread reads any input asynchronously
+// and processes the input line calling do_uci_async_cmd().
 
 void Thread::listener_loop() {
 
@@ -390,7 +424,7 @@ void Thread::listener_loop() {
           if (cmd == "quit")
               is_searching = false;
 
-          Threads.do_uci_async_cmd(cmd);
+          do_uci_async_cmd(cmd);
           cmd = ""; // Input has been consumed
       }
 
index 124815b4215d368125dbc38a2d4a50cf2d4a3fc8..46ce03aa318c07ea1d66a29a6439b886d4e496c0 100644 (file)
@@ -70,6 +70,7 @@ struct Thread {
   bool is_available_to(int master) const;
   void idle_loop(SplitPoint* sp);
   void listener_loop();
+  void timer_loop();
 
   SplitPoint splitPoints[MAX_ACTIVE_SPLIT_POINTS];
   MaterialInfoTable materialTable;
@@ -115,9 +116,9 @@ public:
   bool available_slave_exists(int master) const;
 
   void getline(std::string& cmd);
-  void do_uci_async_cmd(const std::string& cmd);
   void start_listener();
   void stop_listener();
+  void set_timer(int msec);
 
   template <bool Fake>
   Value split(Position& pos, SearchStack* ss, Value alpha, Value beta, Value bestValue,
@@ -125,7 +126,7 @@ public:
 private:
   friend struct Thread;
 
-  Thread threads[MAX_THREADS + 1];
+  Thread threads[MAX_THREADS + 2]; // Last 2 are the listener and the timer
   Lock threadsLock;
   Depth minimumSplitDepth;
   int maxThreadsPerSplitPoint;
index b69169007e2ec15b0e353986d5ccd9b18ed5fa2a..edbc34e42b5cba142804c62e20f9ec9a7a65f50d 100644 (file)
@@ -79,8 +79,8 @@ namespace {
 
 void TimeManager::pv_instability(int curChanges, int prevChanges) {
 
-    unstablePVExtraTime =  curChanges  * (optimumSearchTime / 2)
-                         + prevChanges * (optimumSearchTime / 3);
+  unstablePVExtraTime =  curChanges  * (optimumSearchTime / 2)
+                       + prevChanges * (optimumSearchTime / 3);
 }