From ed0fb0b05fa72ccc6333bf5331eb9abeb7c86457 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sun, 30 Sep 2012 06:49:56 +0200 Subject: [PATCH] Add support for node limited search Handle also the SMP case. This has been quite tricky, not trivial to enforce the node limit in SMP case becuase with "helpful master" concept we can have recursive split points and we cannot lock them all at once so there is the risk of counting the same nodes more than once. Anyhow this patch should be race free and counted nodes are correct. No functional change. --- src/search.cpp | 44 +++++++++++++++++++++++++++++++++++++++----- src/thread.cpp | 14 +++++++------- src/thread.h | 2 ++ 3 files changed, 48 insertions(+), 12 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index 29dc00a9..3793766b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -279,6 +279,8 @@ void Search::think() { // used to check for remaining available thinking time. if (Limits.use_time_management()) Threads.set_timer(std::min(100, std::max(TimeMgr.available_time() / 16, TimerResolution))); + else if (Limits.nodes) + Threads.set_timer(2 * TimerResolution); else Threads.set_timer(100); @@ -566,10 +568,6 @@ namespace { (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; } - // Enforce node limit here. FIXME: This only works with 1 search thread. - if (Limits.nodes && pos.nodes_searched() >= Limits.nodes) - Signals.stop = true; - if (!RootNode) { // Step 2. Check for aborted search and immediate draw @@ -1712,6 +1710,10 @@ void Thread::idle_loop() { sp->mutex.lock(); + assert(sp->activePositions[idx] == NULL); + + sp->activePositions[idx] = &pos; + if (sp->nodeType == Root) search(pos, ss+1, sp->alpha, sp->beta, sp->depth); else if (sp->nodeType == PV) @@ -1724,6 +1726,7 @@ void Thread::idle_loop() { assert(is_searching); is_searching = false; + sp->activePositions[idx] = NULL; sp->slavesMask &= ~(1ULL << idx); sp->nodes += pos.nodes_searched(); @@ -1754,6 +1757,7 @@ void Thread::idle_loop() { void check_time() { static Time::point lastInfoTime = Time::now(); + int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning if (Time::now() - lastInfoTime >= 1000) { @@ -1764,6 +1768,35 @@ void check_time() { if (Limits.ponder) return; + if (Limits.nodes) + { + Threads.mutex.lock(); + + nodes = RootPosition.nodes_searched(); + + // Loop across all split points and sum accumulated SplitPoint nodes plus + // all the currently active slaves positions. + for (size_t i = 0; i < Threads.size(); i++) + for (int j = 0; j < Threads[i].splitPointsCnt; j++) + { + SplitPoint& sp = Threads[i].splitPoints[j]; + + sp.mutex.lock(); + + nodes += sp.nodes; + Bitboard sm = sp.slavesMask; + while (sm) + { + Position* pos = sp.activePositions[pop_lsb(&sm)]; + nodes += pos ? pos->nodes_searched() : 0; + } + + sp.mutex.unlock(); + } + + Threads.mutex.unlock(); + } + Time::point elapsed = Time::now() - SearchTime; bool stillAtFirstMove = Signals.firstRootMove && !Signals.failedLowAtRoot @@ -1773,6 +1806,7 @@ void check_time() { || stillAtFirstMove; if ( (Limits.use_time_management() && noMoreTime) - || (Limits.movetime && elapsed >= Limits.movetime)) + || (Limits.movetime && elapsed >= Limits.movetime) + || (Limits.nodes && nodes >= Limits.nodes)) Signals.stop = true; } diff --git a/src/thread.cpp b/src/thread.cpp index 8d522fa2..271890c6 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -42,7 +42,7 @@ namespace { extern "C" { // Thread c'tor starts a newly-created thread of execution that will call // the idle loop function pointed by start_fn going immediately to sleep. -Thread::Thread(Fn fn) { +Thread::Thread(Fn fn) : splitPoints() { is_searching = do_exit = false; maxPly = splitPointsCnt = 0; @@ -200,10 +200,10 @@ void ThreadPool::init() { void ThreadPool::exit() { + delete timer; // As first becuase check_time() accesses threads data + for (size_t i = 0; i < threads.size(); i++) delete threads[i]; - - delete timer; } @@ -327,8 +327,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta, // Try to allocate available threads and ask them to start searching setting // is_searching flag. This must be done under lock protection to avoid concurrent // allocation of the same slave by another master. - sp.mutex.lock(); mutex.lock(); + sp.mutex.lock(); for (size_t i = 0; i < threads.size() && !Fake; ++i) if (threads[i]->is_available_to(master)) @@ -346,8 +346,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta, master->splitPointsCnt++; - mutex.unlock(); sp.mutex.unlock(); + mutex.unlock(); // Everything is set up. The master thread enters the idle loop, from which // it will instantly launch a search, because its is_searching flag is set. @@ -365,8 +365,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta, // We have returned from the idle loop, which means that all threads are // finished. Note that setting is_searching and decreasing splitPointsCnt is // done under lock protection to avoid a race with Thread::is_available_to(). - sp.mutex.lock(); // To protect sp.nodes mutex.lock(); + sp.mutex.lock(); master->is_searching = true; master->splitPointsCnt--; @@ -374,8 +374,8 @@ Value ThreadPool::split(Position& pos, Stack* ss, Value alpha, Value beta, pos.set_nodes_searched(pos.nodes_searched() + sp.nodes); *bestMove = sp.bestMove; - mutex.unlock(); sp.mutex.unlock(); + mutex.unlock(); return sp.bestValue; } diff --git a/src/thread.h b/src/thread.h index 38a29e8d..f69012ae 100644 --- a/src/thread.h +++ b/src/thread.h @@ -75,6 +75,7 @@ struct SplitPoint { // Shared data Mutex mutex; + Position* activePositions[MAX_THREADS]; volatile uint64_t slavesMask; volatile int64_t nodes; volatile Value alpha; @@ -153,6 +154,7 @@ public: Depth depth, Move threatMove, int moveCount, MovePicker* mp, int nodeType); private: friend class Thread; + friend void check_time(); std::vector threads; Thread* timer; -- 2.39.2