Allow for general transposition table sizes. (#1341)

For efficiency reasons current master only allows for transposition table sizes that are N = 2^k in size, the index computation can be done efficiently as (hash % N) can be written instead as (hash & 2^k - 1). On a typical computer (with 4, 8... etc Gb of RAM), this implies roughly half the RAM is left unused in analysis.

This issue was mentioned on fishcooking by Mindbreaker:
http://tests.stockfishchess.org/tests/view/5a3587de0ebc590ccbb8be04

Recently a neat trick was proposed to map a hash into the range [0,N[ more efficiently than (hash % N) for general N, nearly as efficiently as (hash % 2^k):

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

namely computing (hash * N / 2^32) for 32 bit hashes. This patch implements this trick and now allows for general hash sizes. Note that for N = 2^k this just amounts to using a different subset of bits from the hash. Master will use the lower k bits, this trick will use the upper k bits (of the 32 bit hash).

There is no slowdown as measured with [-3, 1] test:

http://tests.stockfishchess.org/tests/view/5a3587de0ebc590ccbb8be04
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 128498 W: 23332 L: 23395 D: 81771

There are two (smaller) caveats:

1) the patch is implemented for a 32 bit hash (so that a 64 bit multiply can be used), this effectively limits the number of clusters that can be used to 2^32 or to 128Gb of transpostion table. That's a change in the maximum allowed TT size, which could bother those using 256Gb or more regularly.

2) Already in master, an excluded move is hashed into the position key in rather simple way, essentially only affecting the lower 16 bits of the key. This is OK in master, since bits 0-15 end up in the index, but not in the new scheme, which picks the higher bits. This is 'fixed' by shifting the excluded move a few bits up. Eventually a better hashing scheme seems wise.

Despite these two caveats, I think this is a nice improvement in usability.

Bench: 5346341

diff --git a/src/search.cpp b/src/search.cpp
index 8b3b8fb4864436c17c6964a24151a85db92f873f..1aa3e92e69487b51e504acebc5e1127bb2b6f033 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -557,7 +557,7 @@ namespace {
     // search to overwrite a previous full search TT value, so we use a different
     // position key in case of an excluded move.
     excludedMove = ss->excludedMove;
-    posKey = pos.key() ^ Key(excludedMove);
+    posKey = pos.key() ^ Key(excludedMove << 16); // isn't a very good hash
     tte = TT.probe(posKey, ttHit);
     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
     ttMove =  rootNode ? thisThread->rootMoves[thisThread->PVIdx].pv[0]

diff --git a/src/tt.cpp b/src/tt.cpp
index f283d0c6d71c21881d84a8f448cfbb2b537a461e..a1ef44422832781d1325232da2d30a3a48582149 100644 (file)
--- a/src/tt.cpp
+++ b/src/tt.cpp
@@ -33,7 +33,7 @@ TranspositionTable TT; // Our global transposition table
 
 void TranspositionTable::resize(size_t mbSize) {
 
-  size_t newClusterCount = size_t(1) << msb((mbSize * 1024 * 1024) / sizeof(Cluster));
+  size_t newClusterCount = mbSize * 1024 * 1024 / sizeof(Cluster);
 
   if (newClusterCount == clusterCount)
       return;

diff --git a/src/tt.h b/src/tt.h
index 24045ed0f40c879056dbbca5e6e7cfa776e5641e..e1bef323af5092474f07a96db48ff2d8fb8b4e9f 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -104,9 +104,9 @@ public:
   void resize(size_t mbSize);
   void clear();
 
-  // The lowest order bits of the key are used to get the index of the cluster
+  // The 32 lowest order bits of the key are used to get the index of the cluster
   TTEntry* first_entry(const Key key) const {
-    return &table[(size_t)key & (clusterCount - 1)].entry[0];
+    return &table[(uint32_t(key) * uint64_t(clusterCount)) >> 32].entry[0];
   }
 
 private:

diff --git a/src/ucioption.cpp b/src/ucioption.cpp
index b902677f93cd878b4b52540cc7a6475dbc49bafa..f85ede1813c39e44dc6c820383de74081de95ab8 100644 (file)
--- a/src/ucioption.cpp
+++ b/src/ucioption.cpp
@@ -55,7 +55,8 @@ bool CaseInsensitiveLess::operator() (const string& s1, const string& s2) const
 
 void init(OptionsMap& o) {
 
-  const int MaxHashMB = Is64Bit ? 1024 * 1024 : 2048;
+  // at most 2^32 clusters.
+  const int MaxHashMB = Is64Bit ? 131072 : 2048;
 
   o["Debug Log File"]        << Option("", on_logger);
   o["Contempt"]              << Option(0, -100, 100);