X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Ftt.h;h=3e335b44696e3738b877bc9f2a1adaba527aefef;hb=HEAD;hp=03fe3e143d1b9a46e6165772e92fa676367b8938;hpb=ad926d34c0105d523bfa5cb92cbcf9f337d54c08;p=stockfish diff --git a/src/tt.h b/src/tt.h index 03fe3e14..1bece002 100644 --- a/src/tt.h +++ b/src/tt.h @@ -1,6 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2022 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2024 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -19,89 +19,80 @@ #ifndef TT_H_INCLUDED #define TT_H_INCLUDED -#include "misc.h" +#include +#include +#include + +#include "memory.h" #include "types.h" namespace Stockfish { -/// TTEntry struct is the 10 bytes transposition table entry, defined as below: -/// -/// key 16 bit -/// depth 8 bit -/// generation 5 bit -/// pv node 1 bit -/// bound type 2 bit -/// move 16 bit -/// value 16 bit -/// eval value 16 bit - -struct TTEntry { - - Move move() const { return (Move )move16; } - Value value() const { return (Value)value16; } - Value eval() const { return (Value)eval16; } - Depth depth() const { return (Depth)depth8 + DEPTH_OFFSET; } - bool is_pv() const { return (bool)(genBound8 & 0x4); } - Bound bound() const { return (Bound)(genBound8 & 0x3); } - void save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev); - -private: - friend class TranspositionTable; - - uint16_t key16; - uint8_t depth8; - uint8_t genBound8; - uint16_t move16; - int16_t value16; - int16_t eval16; +class ThreadPool; +struct TTEntry; +struct Cluster; + +// There is only one global hash table for the engine and all its threads. For chess in particular, we even allow racy +// updates between threads to and from the TT, as taking the time to synchronize access would cost thinking time and +// thus elo. As a hash table, collisions are possible and may cause chess playing issues (bizarre blunders, faulty mate +// reports, etc). Fixing these also loses elo; however such risk decreases quickly with larger TT size. +// +// `probe` is the primary method: given a board position, we lookup its entry in the table, and return a tuple of: +// 1) whether the entry already has this position +// 2) a copy of the prior data (if any) (may be inconsistent due to read races) +// 3) a writer object to this entry +// The copied data and the writer are separated to maintain clear boundaries between local vs global objects. + + +// A copy of the data already in the entry (possibly collided). `probe` may be racy, resulting in inconsistent data. +struct TTData { + Move move; + Value value, eval; + Depth depth; + Bound bound; + bool is_pv; }; -/// A TranspositionTable is an array of Cluster, of size clusterCount. Each -/// cluster consists of ClusterSize number of TTEntry. Each non-empty TTEntry -/// contains information on exactly one position. The size of a Cluster should -/// divide the size of a cache line for best performance, as the cacheline is -/// prefetched when possible. +// This is used to make racy writes to the global TT. +struct TTWriter { + public: + void write(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev, uint8_t generation8); -class TranspositionTable { + private: + friend class TranspositionTable; + TTEntry* entry; + TTWriter(TTEntry* tte); +}; - static constexpr int ClusterSize = 3; - struct Cluster { - TTEntry entry[ClusterSize]; - char padding[2]; // Pad to 32 bytes - }; +class TranspositionTable { - static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size"); + public: + ~TranspositionTable() { aligned_large_pages_free(table); } - // Constants used to refresh the hash table periodically - static constexpr unsigned GENERATION_BITS = 3; // nb of bits reserved for other things - static constexpr int GENERATION_DELTA = (1 << GENERATION_BITS); // increment for generation field - static constexpr int GENERATION_CYCLE = 255 + (1 << GENERATION_BITS); // cycle length - static constexpr int GENERATION_MASK = (0xFF << GENERATION_BITS) & 0xFF; // mask to pull out generation number + void resize(size_t mbSize, ThreadPool& threads); // Set TT size + void clear(ThreadPool& threads); // Re-initialize memory, multithreaded + int hashfull() + const; // Approximate what fraction of entries (permille) have been written to during this root search -public: - ~TranspositionTable() { aligned_large_pages_free(table); } - void new_search() { generation8 += GENERATION_DELTA; } // Lower bits are used for other things - TTEntry* probe(const Key key, bool& found) const; - int hashfull() const; - void resize(size_t mbSize); - void clear(); + void + new_search(); // This must be called at the beginning of each root search to track entry aging + uint8_t generation() const; // The current age, used when writing new data to the TT + std::tuple + probe(const Key key) const; // The main method, whose retvals separate local vs global objects + TTEntry* first_entry(const Key key) + const; // This is the hash function; its only external use is memory prefetching. - TTEntry* first_entry(const Key key) const { - return &table[mul_hi64(key, clusterCount)].entry[0]; - } + private: + friend struct TTEntry; -private: - friend struct TTEntry; + size_t clusterCount; + Cluster* table = nullptr; - size_t clusterCount; - Cluster* table; - uint8_t generation8; // Size must be not bigger than TTEntry::genBound8 + uint8_t generation8 = 0; // Size must be not bigger than TTEntry::genBound8 }; -extern TranspositionTable TT; - -} // namespace Stockfish +} // namespace Stockfish -#endif // #ifndef TT_H_INCLUDED +#endif // #ifndef TT_H_INCLUDED