Use 32 bit key in TT

Shrink key to 32 bits instead of 64. To still avoid
collisions use the high 32 bits of position key as the
TT key and the low 32 bits to retrieve the correct
cluster index in the table.

With this patch size og TTentry shrinks to 96 bits instead
of 128 and the cluster of 4 TTEntry sums to 48 bytes instead
of 64.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/tt.cpp b/src/tt.cpp
index 1e98aa24901549c888a3704576b5215619f6a6bf..49dae31d70ffb5b634709e339c7815d8d5e5184d 100644 (file)
--- a/src/tt.cpp
+++ b/src/tt.cpp
@@ -30,6 +30,10 @@
 #include "tt.h"
 
 
 #include "tt.h"
 
 

+/// This is the number of TTEntry slots for each position
+static const int ClusterSize = 4;
+
+

 ////
 //// Functions
 ////
 ////
 //// Functions
 ////


@@ -56,16 +60,16 @@ void TranspositionTable::set_size(unsigned mbSize) {
 
   unsigned newSize = 1024;
 
 
   unsigned newSize = 1024;
 

-  // We store a cluster of 4 TTEntry for each position and newSize is
-  // the maximum number of storable positions
-  while ((2 * newSize) * 4 * (sizeof(TTEntry)) <= (mbSize << 20))
+  // We store a cluster of ClusterSize number of TTEntry for each position
+  // and newSize is the maximum number of storable positions.
+  while ((2 * newSize) * ClusterSize * (sizeof(TTEntry)) <= (mbSize << 20))

       newSize *= 2;
 
   if (newSize != size)
   {
       size = newSize;
       delete [] entries;
       newSize *= 2;
 
   if (newSize != size)
   {
       size = newSize;
       delete [] entries;

-      entries = new TTEntry[size * 4];
+      entries = new TTEntry[size * ClusterSize];

       if (!entries)
       {
           std::cerr << "Failed to allocate " << mbSize
       if (!entries)
       {
           std::cerr << "Failed to allocate " << mbSize


@@ -84,7 +88,7 @@ void TranspositionTable::set_size(unsigned mbSize) {
 
 void TranspositionTable::clear() {
 
 
 void TranspositionTable::clear() {
 

-  memset(entries, 0, size * 4 * sizeof(TTEntry));
+  memset(entries, 0, size * ClusterSize * sizeof(TTEntry));

 }
 
 
 }
 
 


@@ -101,11 +105,12 @@ void TranspositionTable::clear() {
 void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d, Move m) {
 
   TTEntry *tte, *replace;
 void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d, Move m) {
 
   TTEntry *tte, *replace;

+  uint32_t posKey32 = posKey >> 32; // Use the high 32 bits as key

 
   tte = replace = first_entry(posKey);
 
   tte = replace = first_entry(posKey);

-  for (int i = 0; i < 4; i++, tte++)
+  for (int i = 0; i < ClusterSize; i++, tte++)

   {
   {

-      if (!tte->key() || tte->key() == posKey) // empty or overwrite old
+      if (!tte->key() || tte->key() == posKey32) // empty or overwrite old

       {
           // Do not overwrite when new type is VALUE_TYPE_EVAL
           if (tte->key() && t == VALUE_TYPE_EVAL)
       {
           // Do not overwrite when new type is VALUE_TYPE_EVAL
           if (tte->key() && t == VALUE_TYPE_EVAL)


@@ -114,7 +119,7 @@ void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d,
           if (m == MOVE_NONE)
               m = tte->move();
 
           if (m == MOVE_NONE)
               m = tte->move();
 

-          *tte = TTEntry(posKey, v, t, d, m, generation);
+          *tte = TTEntry(posKey32, v, t, d, m, generation);

           return;
       }
       else if (i == 0)  // replace would be a no-op in this common case
           return;
       }
       else if (i == 0)  // replace would be a no-op in this common case


@@ -127,7 +132,7 @@ void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d,
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }

-  *replace = TTEntry(posKey, v, t, d, m, generation);
+  *replace = TTEntry(posKey32, v, t, d, m, generation);

   writes++;
 }
 
   writes++;
 }
 


@@ -138,10 +143,11 @@ void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d,
 
 TTEntry* TranspositionTable::retrieve(const Key posKey) const {
 
 
 TTEntry* TranspositionTable::retrieve(const Key posKey) const {
 

+  uint32_t posKey32 = posKey >> 32;

   TTEntry *tte = first_entry(posKey);
 
   TTEntry *tte = first_entry(posKey);
 

-  for (int i = 0; i < 4; i++, tte++)
-      if (tte->key() == posKey)
+  for (int i = 0; i < ClusterSize; i++, tte++)
+      if (tte->key() == posKey32)

           return tte;
 
   return NULL;
           return tte;
 
   return NULL;


@@ -149,11 +155,12 @@ TTEntry* TranspositionTable::retrieve(const Key posKey) const {
 
 
 /// TranspositionTable::first_entry returns a pointer to the first
 
 
 /// TranspositionTable::first_entry returns a pointer to the first

-/// entry of a cluster given a position.
+/// entry of a cluster given a position. The low 32 bits of the key
+/// are used to get the index in the table.

 
 inline TTEntry* TranspositionTable::first_entry(const Key posKey) const {
 
 
 inline TTEntry* TranspositionTable::first_entry(const Key posKey) const {
 

-  return entries + (int(posKey & (size - 1)) << 2);
+  return entries + ((uint32_t(posKey) & (size - 1)) * ClusterSize);

 }
 
 /// TranspositionTable::new_search() is called at the beginning of every new
 }
 
 /// TranspositionTable::new_search() is called at the beginning of every new


@@ -224,6 +231,6 @@ void TranspositionTable::extract_pv(const Position& pos, Move pv[]) {
 
 int TranspositionTable::full() const {
 
 
 int TranspositionTable::full() const {
 

-  double N = double(size) * 4.0;
+  double N = double(size) * ClusterSize;

   return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N))));
 }
   return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N))));
 }

diff --git a/src/tt.h b/src/tt.h
index 08121f66f699a9bcf7e6b1e54893b0636f75f80b..4a8699fb2dfce4468d70b6e2a73889586d61e26d 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -36,12 +36,12 @@
 
 /// The TTEntry class is the class of transposition table entries
 ///
 
 /// The TTEntry class is the class of transposition table entries
 ///

-/// A TTEntry needs 128 bits to be stored
+/// A TTEntry needs 96 bits to be stored

 ///
 ///

-/// bit    0-63: key
-/// bit   64-95: data
-/// bit  96-111: value
-/// bit 112-127: depth
+/// bit  0-31: key
+/// bit 32-63: data
+/// bit 64-79: value
+/// bit 80-95: depth

 ///
 /// the 32 bits of the data field are so defined
 ///
 ///
 /// the 32 bits of the data field are so defined
 ///


@@ -54,11 +54,11 @@ class TTEntry {
 
 public:
   TTEntry() {}
 
 public:
   TTEntry() {}

-  TTEntry(Key k, Value v, ValueType t, Depth d, Move m, int generation)
+  TTEntry(uint32_t k, Value v, ValueType t, Depth d, Move m, int generation)

         : key_ (k), data((m & 0x1FFFF) | (t << 20) | (generation << 23)),
           value_(int16_t(v)), depth_(int16_t(d)) {}
 
         : key_ (k), data((m & 0x1FFFF) | (t << 20) | (generation << 23)),
           value_(int16_t(v)), depth_(int16_t(d)) {}
 

-  Key key() const { return key_; }
+  uint32_t key() const { return key_; }

   Depth depth() const { return Depth(depth_); }
   Move move() const { return Move(data & 0x1FFFF); }
   Value value() const { return Value(value_); }
   Depth depth() const { return Depth(depth_); }
   Move move() const { return Move(data & 0x1FFFF); }
   Value value() const { return Value(value_); }


@@ -66,7 +66,7 @@ public:
   int generation() const { return (data >> 23); }
 
 private:
   int generation() const { return (data >> 23); }
 
 private:

-  Key key_;
+  uint32_t key_;

   uint32_t data;
   int16_t value_;
   int16_t depth_;
   uint32_t data;
   int16_t value_;
   int16_t depth_;