Better code for hash table generation
authormattginsberg <mlginsberg@gmail.com>
Thu, 11 Feb 2021 21:29:28 +0000 (22:29 +0100)
committerStéphane Nicolet <cassio@free.fr>
Thu, 11 Feb 2021 21:29:35 +0000 (22:29 +0100)
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
src/tt.cpp
src/tt.h

diff --git a/AUTHORS b/AUTHORS
index d2b26469ea59a8bc23c9c1b6fd95402a33737dca..5f21c0485b30db09e7635a8e1ac2d52dbcb9c828 100644 (file)
--- a/AUTHORS
+++ b/AUTHORS
@@ -113,6 +113,7 @@ Maciej Żenczykowski (zenczykowski)
 Malcolm Campbell (xoto10)
 Mark Tenzer (31m059)
 marotear
 Malcolm Campbell (xoto10)
 Mark Tenzer (31m059)
 marotear
+Matt Ginsberg (mattginsberg)
 Matthew Lai (matthewlai)
 Matthew Sullivan (Matt14916)
 Maxim Molchanov (Maxim)
 Matthew Lai (matthewlai)
 Matthew Sullivan (Matt14916)
 Maxim Molchanov (Maxim)
index d1ba9ebbabaa6876f9f4f0d5b82602c3053d997f..cb5af5c85905620a1537d06a7339ce6bca17176f 100644 (file)
@@ -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)
       {
   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];
       }
 
           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
   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;
           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)
   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;
 }
 
   return cnt / ClusterSize;
 }
index 5f9525a6fbdbd3e37705ebddc6007c81747bdf24..a750b6c465706c1daa22947b082b42a8decbf641 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -72,9 +72,15 @@ class TranspositionTable {
 
   static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size");
 
 
   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); }
 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);
   TTEntry* probe(const Key key, bool& found) const;
   int hashfull() const;
   void resize(size_t mbSize);