From f6e98a924af233a5e69f3494168cf5d80168c705 Mon Sep 17 00:00:00 2001
From: Joona Kiiski <joona.kiiski@gmail.com>
Date: Sat, 3 May 2014 18:29:31 +0100
Subject: [PATCH] Allow a slave to 'late join' another splitpoint

Instead of waiting to be allocated, actively search
for another split point to join when finishes its
search. Also modify split conditions.

This patch has been tested with 7 threads SMP and
passed both STC:

LLR: 2.97 (-2.94,2.94) [-1.50,4.50]
Total: 2885 W: 519 L: 410 D: 1956

And a reduced-LTC at  25+0.05
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 4401 W: 684 L: 566 D: 3151

Was then retested against regression in 3 thread case
at standard LTC of  60+0.05:

LLR: 2.96 (-2.94,2.94) [-4.00,0.00]
Total: 40809 W: 5446 L: 5406 D: 29957

bench: 8802105
---
 src/search.cpp | 48 ++++++++++++++++++++++++++++++++++++++++++++++--
 src/thread.cpp |  7 ++++---
 src/thread.h   |  4 +++-
 3 files changed, 53 insertions(+), 6 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index fbe6b2c0..60d1a868 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -984,8 +984,10 @@ moves_loop: // When in check and at SpNode search starts from here
 
       // Step 19. Check for splitting the search
       if (   !SpNode
+          &&  Threads.size() >= 2
           &&  depth >= Threads.minimumSplitDepth
-          &&  Threads.available_slave(thisThread)
+          &&  (   !thisThread->activeSplitPoint
+               || !thisThread->activeSplitPoint->allowLatejoin)
           &&  thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
       {
           assert(bestValue > -VALUE_INFINITE && bestValue < beta);
@@ -1527,9 +1529,9 @@ void Thread::idle_loop() {
 
           assert(searching);
 
-          searching = false;
           activePosition = NULL;
           sp->slavesMask.reset(idx);
+          sp->allowLatejoin = false;
           sp->nodes += pos.nodes_searched();
 
           // Wake up the master thread so to allow it to return from the idle
@@ -1547,6 +1549,10 @@ void Thread::idle_loop() {
           // the sp master. Also accessing other Thread objects is unsafe because
           // if we are exiting there is a chance that they are already freed.
           sp->mutex.unlock();
+
+          // Try to late join to another splitpoint
+          if (Threads.size() <= 2 || !attempt_to_latejoin()) // FIXME: attempt_to_latejoin() is theoretically unsafe when were are exiting the program...
+              searching = false;
       }
 
       // If this thread is the master of a split point and all slaves have finished
@@ -1562,6 +1568,44 @@ void Thread::idle_loop() {
   }
 }
 
+bool Thread::attempt_to_latejoin()
+{
+    SplitPoint *sp;
+    size_t i;
+    bool success = false;
+
+    for (i = 0; i < Threads.size(); ++i)
+    {
+        int size = Threads[i]->splitPointsSize; // Make a local copy to prevent size from changing under our feet.
+
+        sp = size ? &Threads[i]->splitPoints[size - 1] : NULL;
+
+        if (   sp
+            && sp->allowLatejoin
+            && available_to(Threads[i], true))
+            break;
+    }
+
+    if (i == Threads.size())
+        return false; // No suitable splitpoint found!
+
+    // Recheck conditions under lock protection
+    Threads.mutex.lock();
+    sp->mutex.lock();
+
+    if (   sp->allowLatejoin
+        && available_to(Threads[i], true))
+    {
+         activeSplitPoint = sp;
+         sp->slavesMask.set(this->idx);
+         success = true;
+    }
+
+    sp->mutex.unlock();
+    Threads.mutex.unlock();
+
+    return success;
+}
 
 /// check_time() is called by the timer thread when the timer triggers. It is
 /// used to print debug info and, more importantly, to detect when we are out of
diff --git a/src/thread.cpp b/src/thread.cpp
index 432d573d..f5aab2b1 100644
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -112,9 +112,9 @@ bool Thread::cutoff_occurred() const {
 // which are busy searching the split point at the top of slave's split point
 // stack (the "helpful master concept" in YBWC terminology).
 
-bool Thread::available_to(const Thread* master) const {
+bool Thread::available_to(const Thread* master, bool latejoin) const {
 
-  if (searching)
+  if (searching && !latejoin)
       return false;
 
   // Make a local copy to be sure it doesn't become zero under our feet while
@@ -239,7 +239,7 @@ void ThreadPool::read_uci_options() {
 Thread* ThreadPool::available_slave(const Thread* master) const {
 
   for (const_iterator it = begin(); it != end(); ++it)
-      if ((*it)->available_to(master))
+      if ((*it)->available_to(master, false))
           return *it;
 
   return NULL;
@@ -292,6 +292,7 @@ void Thread::split(Position& pos, const Stack* ss, Value alpha, Value beta, Valu
   Threads.mutex.lock();
   sp.mutex.lock();
 
+  sp.allowLatejoin = true; // Only set this under lock protection
   ++splitPointsSize;
   activeSplitPoint = &sp;
   activePosition = NULL;
diff --git a/src/thread.h b/src/thread.h
index 44aa6883..edc4ee31 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -77,6 +77,7 @@ struct SplitPoint {
   // Shared data
   Mutex mutex;
   std::bitset<MAX_THREADS> slavesMask;
+  volatile bool allowLatejoin;
   volatile uint64_t nodes;
   volatile Value alpha;
   volatile Value bestValue;
@@ -113,8 +114,9 @@ struct Thread : public ThreadBase {
 
   Thread();
   virtual void idle_loop();
+  bool attempt_to_latejoin();
   bool cutoff_occurred() const;
-  bool available_to(const Thread* master) const;
+  bool available_to(const Thread* master, bool latejoin) const;
 
   template <bool Fake>
   void split(Position& pos, const Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,
-- 
2.39.2