From 573f0e364ff4c1e5928be2ca947f65c5d4e177d5 Mon Sep 17 00:00:00 2001 From: mattginsberg Date: Thu, 11 Feb 2021 22:29:28 +0100 Subject: [PATCH] Better code for hash table generation This patch removes some magic numbers in TT bit management and introduce proper constants in the code, to improve documentation and ease further modifications. No function change --- AUTHORS | 1 + src/tt.cpp | 15 ++++++++------- src/tt.h | 8 +++++++- 3 files changed, 16 insertions(+), 8 deletions(-) diff --git a/AUTHORS b/AUTHORS index d2b26469..5f21c048 100644 --- a/AUTHORS +++ b/AUTHORS @@ -113,6 +113,7 @@ Maciej Żenczykowski (zenczykowski) Malcolm Campbell (xoto10) Mark Tenzer (31m059) marotear +Matt Ginsberg (mattginsberg) Matthew Lai (matthewlai) Matthew Sullivan (Matt14916) Maxim Molchanov (Maxim) diff --git a/src/tt.cpp b/src/tt.cpp index d1ba9ebb..cb5af5c8 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -123,7 +123,7 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { for (int i = 0; i < ClusterSize; ++i) if (tte[i].key16 == key16 || !tte[i].depth8) { - tte[i].genBound8 = uint8_t(generation8 | (tte[i].genBound8 & 0x7)); // Refresh + tte[i].genBound8 = uint8_t(generation8 | (tte[i].genBound8 & (GENERATION_DELTA - 1))); // Refresh return found = (bool)tte[i].depth8, &tte[i]; } @@ -132,11 +132,12 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { TTEntry* replace = tte; for (int i = 1; i < ClusterSize; ++i) // Due to our packed storage format for generation and its cyclic - // nature we add 263 (256 is the modulus plus 7 to keep the unrelated - // lowest three bits from affecting the result) to calculate the entry - // age correctly even after generation8 overflows into the next cycle. - if ( replace->depth8 - ((263 + generation8 - replace->genBound8) & 0xF8) - > tte[i].depth8 - ((263 + generation8 - tte[i].genBound8) & 0xF8)) + // nature we add GENERATION_CYCLE (256 is the modulus, plus what + // is needed to keep the unrelated lowest n bits from affecting + // the result) to calculate the entry age correctly even after + // generation8 overflows into the next cycle. + if ( replace->depth8 - ((GENERATION_CYCLE + generation8 - replace->genBound8) & GENERATION_MASK) + > tte[i].depth8 - ((GENERATION_CYCLE + generation8 - tte[i].genBound8) & GENERATION_MASK)) replace = &tte[i]; return found = false, replace; @@ -151,7 +152,7 @@ int TranspositionTable::hashfull() const { int cnt = 0; for (int i = 0; i < 1000; ++i) for (int j = 0; j < ClusterSize; ++j) - cnt += table[i].entry[j].depth8 && (table[i].entry[j].genBound8 & 0xF8) == generation8; + cnt += table[i].entry[j].depth8 && (table[i].entry[j].genBound8 & GENERATION_MASK) == generation8; return cnt / ClusterSize; } diff --git a/src/tt.h b/src/tt.h index 5f9525a6..a750b6c4 100644 --- a/src/tt.h +++ b/src/tt.h @@ -72,9 +72,15 @@ class TranspositionTable { static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size"); + // 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 += 8; } // Lower 3 bits are used by PV flag and Bound + 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); -- 2.39.2