X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Ftt.cpp;h=9f0bc4ba63091919a123fad9a2185f5f8e1e4fa6;hp=a0cc7922395cb2a86bba11a1adbd29eacd78f305;hb=2af2c67650c4ac2531e6ab2753830f91c0999876;hpb=a88e762b4ea4a3696ecc0431237f54090a5aa1e2 diff --git a/src/tt.cpp b/src/tt.cpp index a0cc7922..9f0bc4ba 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -1,7 +1,8 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008 Marco Costalba + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -17,180 +18,115 @@ along with this program. If not, see . */ +#include // For std::memset +#include +#include -//// -//// Includes -//// - -#include -#include -#include - +#include "bitboard.h" +#include "misc.h" #include "tt.h" +#include "uci.h" +TranspositionTable TT; // Our global transposition table -//// -//// Functions -//// - -TranspositionTable::TranspositionTable() { - size = writes = 0; - entries = 0; - generation = 0; -} - -TranspositionTable::~TranspositionTable() { +/// TranspositionTable::resize() sets the size of the transposition table, +/// measured in megabytes. Transposition table consists of a power of 2 number +/// of clusters and each cluster consists of ClusterSize number of TTEntry. - delete [] entries; -} +void TranspositionTable::resize(size_t mbSize) { + clusterCount = mbSize * 1024 * 1024 / sizeof(Cluster); -/// TranspositionTable::set_size sets the size of the transposition table, -/// measured in megabytes. + free(mem); + mem = malloc(clusterCount * sizeof(Cluster) + CacheLineSize - 1); -void TranspositionTable::set_size(unsigned mbSize) { - - assert(mbSize >= 4 && mbSize <= 4096); - - unsigned newSize = 1024; - - // We store a cluster of 4 TTEntry for each position and newSize is - // the maximum number of storable positions - while ((2 * newSize) * 4 * (sizeof(TTEntry)) <= (mbSize << 20)) - newSize *= 2; - - if (newSize != size) + if (!mem) { - size = newSize; - delete [] entries; - entries = new TTEntry[size * 4]; - if (!entries) - { - std::cerr << "Failed to allocate " << mbSize - << " MB for transposition table." << std::endl; - Application::exit_with_failure(); - } - clear(); + std::cerr << "Failed to allocate " << mbSize + << "MB for transposition table." << std::endl; + exit(EXIT_FAILURE); } + + table = (Cluster*)((uintptr_t(mem) + CacheLineSize - 1) & ~(CacheLineSize - 1)); + clear(); } -/// TranspositionTable::clear overwrites the entire transposition table -/// with zeroes. It is called whenever the table is resized, or when the +/// TranspositionTable::clear() overwrites the entire transposition table +/// with zeros. It is called whenever the table is resized, or when the /// user asks the program to clear the table (from the UCI interface). -/// Perhaps we should also clear it when the "ucinewgame" command is recieved? +/// It starts as many threads as allowed by the Threads option. void TranspositionTable::clear() { - memset(entries, 0, size * 4 * sizeof(TTEntry)); -} - - -/// TranspositionTable::store writes a new entry containing a position, -/// a value, a value type, a search depth, and a best move to the -/// transposition table. Transposition table is organized in clusters of -/// four TTEntry objects, and when a new entry is written, it replaces -/// the least valuable of the four entries in a cluster. A TTEntry t1 is -/// considered to be more valuable than a TTEntry t2 if t1 is from the -/// current search and t2 is from a previous search, or if the depth of t1 -/// is bigger than the depth of t2. A TTEntry of type VALUE_TYPE_EVAL -/// never replaces another entry for the same position. - -void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d, Move m) { - - TTEntry *tte, *replace; - - tte = replace = first_entry(posKey); - for (int i = 0; i < 4; i++, tte++) + const size_t stride = clusterCount / Options["Threads"]; + std::vector threads; + for (size_t idx = 0; idx < Options["Threads"]; idx++) { - if (!tte->key() || tte->key() == posKey) // empty or overwrite old - { - // Do not overwrite when new type is VALUE_TYPE_EVAL - if (tte->key() && t == VALUE_TYPE_EVAL) - return; - - if (m == MOVE_NONE) - m = tte->move(); - - *tte = TTEntry(posKey, v, t, d, m, generation); - return; - } - else if (i == 0) // replace would be a no-op in this common case - continue; - - int c1 = (replace->generation() == generation ? 2 : 0); - int c2 = (tte->generation() == generation ? -2 : 0); - int c3 = (tte->depth() < replace->depth() ? 1 : 0); - - if (c1 + c2 + c3 > 0) - replace = tte; + const size_t start = stride * idx, + len = idx != Options["Threads"] - 1 ? + stride : + clusterCount - start; + threads.push_back(std::thread([this, idx, start, len]() { + if (Options["Threads"] >= 8) + WinProcGroup::bindThisThread(idx); + std::memset(&table[start], 0, len * sizeof(Cluster)); + })); } - *replace = TTEntry(posKey, v, t, d, m, generation); - writes++; -} - - -/// TranspositionTable::retrieve looks up the current position in the -/// transposition table. Returns a pointer to the TTEntry or NULL -/// if position is not found. - -TTEntry* TranspositionTable::retrieve(const Key posKey) const { - - TTEntry *tte = first_entry(posKey); - - for (int i = 0; i < 4; i++, tte++) - if (tte->key() == posKey) - return tte; - return NULL; + for (std::thread& th: threads) + th.join(); } +/// TranspositionTable::probe() looks up the current position in the transposition +/// table. It returns true and a pointer to the TTEntry if the position is found. +/// Otherwise, it returns false and a pointer to an empty or least valuable TTEntry +/// to be replaced later. The replace value of an entry is calculated as its depth +/// minus 8 times its relative age. TTEntry t1 is considered more valuable than +/// TTEntry t2 if its replace value is greater than that of t2. -/// TranspositionTable::first_entry returns a pointer to the first -/// entry of a cluster given a position. +TTEntry* TranspositionTable::probe(const Key key, bool& found) const { -inline TTEntry* TranspositionTable::first_entry(const Key posKey) const { + TTEntry* const tte = first_entry(key); + const uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster - return entries + (int(posKey & (size - 1)) << 2); -} - -/// TranspositionTable::new_search() is called at the beginning of every new -/// search. It increments the "generation" variable, which is used to -/// distinguish transposition table entries from previous searches from -/// entries from the current search. + for (int i = 0; i < ClusterSize; ++i) + if (!tte[i].key16 || tte[i].key16 == key16) + { + if ((tte[i].genBound8 & 0xFC) != generation8 && tte[i].key16) + tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh -void TranspositionTable::new_search() { + return found = (bool)tte[i].key16, &tte[i]; + } - generation++; - writes = 0; + // Find an entry to be replaced according to the replacement strategy + TTEntry* replace = tte; + for (int i = 1; i < ClusterSize; ++i) + // Due to our packed storage format for generation and its cyclic + // nature we add 259 (256 is the modulus plus 3 to keep the lowest + // two bound bits from affecting the result) to calculate the entry + // age correctly even after generation8 overflows into the next cycle. + if ( replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2 + > tte[i].depth8 - ((259 + generation8 - tte[i].genBound8) & 0xFC) * 2) + replace = &tte[i]; + + return found = false, replace; } -/// TranspositionTable::insert_pv() is called at the end of a search -/// iteration, and inserts the PV back into the PV. This makes sure -/// the old PV moves are searched first, even if the old TT entries -/// have been overwritten. - -void TranspositionTable::insert_pv(const Position& pos, Move pv[]) { +/// TranspositionTable::hashfull() returns an approximation of the hashtable +/// occupation during a search. The hash is x permill full, as per UCI protocol. - StateInfo st; - Position p(pos); +int TranspositionTable::hashfull() const { - for (int i = 0; pv[i] != MOVE_NONE; i++) + int cnt = 0; + for (int i = 0; i < 1000 / ClusterSize; i++) { - store(p.get_key(), VALUE_NONE, VALUE_TYPE_NONE, Depth(-127*OnePly), pv[i]); - p.do_move(pv[i], st); + const TTEntry* tte = &table[i].entry[0]; + for (int j = 0; j < ClusterSize; j++) + if ((tte[j].genBound8 & 0xFC) == generation8) + cnt++; } -} - - -/// TranspositionTable::full() returns the permill of all transposition table -/// entries which have received at least one write during the current search. -/// It is used to display the "info hashfull ..." information in UCI. - -int TranspositionTable::full() const { - - double N = double(size) * 4.0; - return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N)))); + return cnt; }