X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Ftt.h;h=a750b6c465706c1daa22947b082b42a8decbf641;hp=3953d1c90dabfcdb462484575c36d0a9963c9717;hb=573f0e364ff4c1e5928be2ca947f65c5d4e177d5;hpb=7f142d68179919a507204e7980fff4f79648dbbc diff --git a/src/tt.h b/src/tt.h index 3953d1c9..a750b6c4 100644 --- a/src/tt.h +++ b/src/tt.h @@ -1,7 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2004-2021 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 @@ -23,96 +22,82 @@ #include "misc.h" #include "types.h" -/// The TTEntry is the 128 bit transposition table entry, defined as below: +/// TTEntry struct is the 10 bytes transposition table entry, defined as below: /// -/// key: 32 bit -/// move: 16 bit -/// bound type: 8 bit -/// generation: 8 bit -/// value: 16 bit -/// depth: 16 bit -/// static value: 16 bit -/// static margin: 16 bit +/// 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 { - void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev, Value em) { - - key32 = (uint32_t)k; - move16 = (uint16_t)m; - bound8 = (uint8_t)b; - generation8 = (uint8_t)g; - value16 = (int16_t)v; - depth16 = (int16_t)d; - evalValue = (int16_t)ev; - evalMargin = (int16_t)em; - } - void set_generation(uint8_t g) { generation8 = g; } - - uint32_t key() const { return key32; } - Depth depth() const { return (Depth)depth16; } - Move move() const { return (Move)move16; } - Value value() const { return (Value)value16; } - Bound bound() const { return (Bound)bound8; } - int generation() const { return (int)generation8; } - Value eval_value() const { return (Value)evalValue; } - Value eval_margin() const { return (Value)evalMargin; } + 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: - uint32_t key32; + friend class TranspositionTable; + + uint16_t key16; + uint8_t depth8; + uint8_t genBound8; uint16_t move16; - uint8_t bound8, generation8; - int16_t value16, depth16, evalValue, evalMargin; + int16_t value16; + int16_t eval16; }; -/// A TranspositionTable consists of a power of 2 number of clusters and each -/// cluster consists of ClusterSize number of TTEntry. Each non-empty entry -/// contains information of exactly one position. Size of a cluster shall not be -/// bigger than a cache line size. In case it is less, it should be padded to -/// guarantee always aligned accesses. +/// 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. class TranspositionTable { - static const unsigned ClusterSize = 4; // A cluster is 64 Bytes - -public: - ~TranspositionTable() { free(mem); } - void new_search() { ++generation; } + static constexpr int ClusterSize = 3; - const TTEntry* probe(const Key key) const; - TTEntry* first_entry(const Key key) const; - void refresh(const TTEntry* tte) const; - void set_size(size_t mbSize); - void clear(); - void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV, Value kingD); + struct Cluster { + TTEntry entry[ClusterSize]; + char padding[2]; // Pad to 32 bytes + }; -private: - uint32_t hashMask; - TTEntry* table; - void* mem; - uint8_t generation; // Size must be not bigger than TTEntry::generation8 -}; + static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size"); -extern TranspositionTable TT; + // 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 +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(); -/// TranspositionTable::first_entry() returns a pointer to the first entry of -/// a cluster given a position. The lowest order bits of the key are used to -/// get the index of the cluster. - -inline TTEntry* TranspositionTable::first_entry(const Key key) const { - - return table + ((uint32_t)key & hashMask); -} - + TTEntry* first_entry(const Key key) const { + return &table[mul_hi64(key, clusterCount)].entry[0]; + } -/// TranspositionTable::refresh() updates the 'generation' value of the TTEntry -/// to avoid aging. Normally called after a TT hit. +private: + friend struct TTEntry; -inline void TranspositionTable::refresh(const TTEntry* tte) const { + size_t clusterCount; + Cluster* table; + uint8_t generation8; // Size must be not bigger than TTEntry::genBound8 +}; - const_cast(tte)->set_generation(generation); -} +extern TranspositionTable TT; #endif // #ifndef TT_H_INCLUDED