Prefetch pawn hash key
authorMarco Costalba <mcostalba@gmail.com>
Sat, 21 Aug 2010 17:57:52 +0000 (19:57 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Sun, 22 Aug 2010 13:04:06 +0000 (14:04 +0100)
Plus a bunch of other minor optimizations.

With this power pack we have an increase
of a whopping 1.4%  :-)

...and it took 3 good hours of profiling + hacking to get it out !

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/evaluate.cpp
src/material.cpp
src/material.h
src/misc.h
src/pawns.cpp
src/pawns.h
src/position.cpp

index 43ef3c4..375c236 100644 (file)
@@ -229,10 +229,6 @@ namespace {
   MaterialInfoTable* MaterialTable[MAX_THREADS];
   PawnInfoTable* PawnTable[MAX_THREADS];
 
-  // Sizes of pawn and material hash tables
-  const int PawnTableSize = 16384;
-  const int MaterialTableSize = 1024;
-
   // Function prototypes
   template<bool HasPopCnt>
   Value do_evaluate(const Position& pos, EvalInfo& ei);
@@ -268,6 +264,14 @@ namespace {
 //// Functions
 ////
 
+
+/// Prefetches in pawn hash tables
+
+void prefetchPawn(Key key, int threadID) {
+
+    PawnTable[threadID]->prefetch(key);
+}
+
 /// evaluate() is the main evaluation function. It always computes two
 /// values, an endgame score and a middle game score, and interpolates
 /// between them based on the remaining material.
@@ -412,9 +416,9 @@ void init_eval(int threads) {
         continue;
     }
     if (!PawnTable[i])
-        PawnTable[i] = new PawnInfoTable(PawnTableSize);
+        PawnTable[i] = new PawnInfoTable();
     if (!MaterialTable[i])
-        MaterialTable[i] = new MaterialInfoTable(MaterialTableSize);
+        MaterialTable[i] = new MaterialInfoTable();
   }
 }
 
@@ -682,15 +686,11 @@ namespace {
 
     Bitboard undefended, b, b1, b2, safe;
     bool sente;
-    int attackUnits, shelter = 0;
+    int attackUnits;
     const Square ksq = pos.king_square(Us);
 
     // King shelter
-    if (relative_rank(Us, ksq) <= RANK_4)
-    {
-        shelter = ei.pi->get_king_shelter(pos, Us, ksq);
-        ei.value += Sign[Us] * make_score(shelter, 0);
-    }
+    ei.value += Sign[Us] * ei.pi->king_shelter(pos, Us, ksq);
 
     // King safety. This is quite complicated, and is almost certainly far
     // from optimally tuned.
@@ -717,7 +717,7 @@ namespace {
         attackUnits =  Min(25, (ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them]) / 2)
                      + 3 * (ei.kingAdjacentZoneAttacksCount[Them] + count_1s_max_15<HasPopCnt>(undefended))
                      + InitKingDanger[relative_square(Us, ksq)]
-                     - shelter / 32;
+                     - mg_value(ei.pi->king_shelter(pos, Us, ksq)) / 32;
 
         // Analyse enemy's safe queen contact checks. First find undefended
         // squares around the king attacked by enemy queen...
@@ -779,7 +779,7 @@ namespace {
     const Color Them = (Us == WHITE ? BLACK : WHITE);
 
     Bitboard squaresToQueen, defendedSquares, unsafeSquares, supportingPawns;
-    Bitboard b = ei.pi->passed_pawns() & pos.pieces_of_color(Us);
+    Bitboard b = ei.pi->passed_pawns(Us);
 
     while (b)
     {
index ffc549c..ab0f5a8 100644 (file)
@@ -23,6 +23,7 @@
 ////
 
 #include <cassert>
+#include <cstring>
 #include <sstream>
 #include <map>
 
@@ -134,15 +135,14 @@ template<> const SFMap& EndgameFunctions::get<SF>() const { return maps.second;
 
 /// MaterialInfoTable c'tor and d'tor, called once by each thread
 
-MaterialInfoTable::MaterialInfoTable(unsigned int numOfEntries) {
+MaterialInfoTable::MaterialInfoTable() {
 
-  size = numOfEntries;
-  entries = new MaterialInfo[size];
+  entries = new MaterialInfo[MaterialTableSize];
   funcs = new EndgameFunctions();
 
   if (!entries || !funcs)
   {
-      cerr << "Failed to allocate " << numOfEntries * sizeof(MaterialInfo)
+      cerr << "Failed to allocate " << MaterialTableSize * sizeof(MaterialInfo)
            << " bytes for material hash table." << endl;
       Application::exit_with_failure();
   }
@@ -181,7 +181,7 @@ Phase MaterialInfoTable::game_phase(const Position& pos) {
 MaterialInfo* MaterialInfoTable::get_material_info(const Position& pos) {
 
   Key key = pos.get_material_key();
-  unsigned index = unsigned(key & (size - 1));
+  unsigned index = unsigned(key & (MaterialTableSize - 1));
   MaterialInfo* mi = entries + index;
 
   // If mi->key matches the position's material hash key, it means that we
@@ -191,7 +191,8 @@ MaterialInfo* MaterialInfoTable::get_material_info(const Position& pos) {
       return mi;
 
   // Clear the MaterialInfo object, and set its key
-  mi->clear();
+  memset(mi, 0, sizeof(MaterialInfo));
+  mi->factor[WHITE] = mi->factor[BLACK] = uint8_t(SCALE_FACTOR_NORMAL);
   mi->key = key;
 
   // Store game phase
index 5e8eb5f..48be349 100644 (file)
@@ -33,6 +33,8 @@
 //// Types
 ////
 
+const int MaterialTableSize = 1024;
+
 /// MaterialInfo is a class which contains various information about a
 /// material configuration. It contains a material balance evaluation,
 /// a function pointer to a special endgame evaluation function (which in
@@ -48,8 +50,6 @@ class MaterialInfo {
   friend class MaterialInfoTable;
 
 public:
-  MaterialInfo() : key(0) { clear(); }
-
   Score material_value() const;
   ScaleFactor scale_factor(const Position& pos, Color c) const;
   int space_weight() const;
@@ -58,8 +58,6 @@ public:
   Value evaluate(const Position& pos) const;
 
 private:
-  inline void clear();
-
   Key key;
   int16_t value;
   uint8_t factor[2];
@@ -78,14 +76,13 @@ class EndgameFunctions;
 class MaterialInfoTable {
 
 public:
-  MaterialInfoTable(unsigned numOfEntries);
+  MaterialInfoTable();
   ~MaterialInfoTable();
   MaterialInfo* get_material_info(const Position& pos);
 
   static Phase game_phase(const Position& pos);
 
 private:
-  unsigned size;
   MaterialInfo* entries;
   EndgameFunctions* funcs;
 };
@@ -104,20 +101,6 @@ inline Score MaterialInfo::material_value() const {
   return make_score(value, value);
 }
 
-
-/// MaterialInfo::clear() resets a MaterialInfo object to an empty state,
-/// with all slots at their default values but the key.
-
-inline void MaterialInfo::clear() {
-
-  value = 0;
-  factor[WHITE] = factor[BLACK] = uint8_t(SCALE_FACTOR_NORMAL);
-  evaluationFunction = NULL;
-  scalingFunction[WHITE] = scalingFunction[BLACK] = NULL;
-  spaceWeight = 0;
-}
-
-
 /// MaterialInfo::scale_factor takes a position and a color as input, and
 /// returns a scale factor for the given color. We have to provide the
 /// position in addition to the color, because the scale factor need not
index 4d9b242..c6b6ecf 100644 (file)
@@ -56,6 +56,7 @@ extern int get_system_time();
 extern int cpu_count();
 extern int Bioskey();
 extern void prefetch(char* addr);
+extern void prefetchPawn(Key, int);
 
 
 ////
index cec9aba..0ab1c26 100644 (file)
@@ -110,12 +110,13 @@ namespace {
 
 /// PawnInfoTable c'tor and d'tor instantiated one each thread
 
-PawnInfoTable::PawnInfoTable(unsigned numOfEntries) : size(numOfEntries) {
+PawnInfoTable::PawnInfoTable() {
+
+  entries = new PawnInfo[PawnTableSize];
 
-  entries = new PawnInfo[size];
   if (!entries)
   {
-      std::cerr << "Failed to allocate " << (numOfEntries * sizeof(PawnInfo))
+      std::cerr << "Failed to allocate " << (PawnTableSize * sizeof(PawnInfo))
                 << " bytes for pawn hash table." << std::endl;
       Application::exit_with_failure();
   }
@@ -128,16 +129,6 @@ PawnInfoTable::~PawnInfoTable() {
 }
 
 
-/// PawnInfo::clear() resets to zero the PawnInfo entry. Note that
-/// kingSquares[] is initialized to SQ_NONE instead.
-
-void PawnInfo::clear() {
-
-  memset(this, 0, sizeof(PawnInfo));
-  kingSquares[WHITE] = kingSquares[BLACK] = SQ_NONE;
-}
-
-
 /// PawnInfoTable::get_pawn_info() takes a position object as input, computes
 /// a PawnInfo object, and returns a pointer to it. The result is also stored
 /// in a hash table, so we don't have to recompute everything when the same
@@ -148,7 +139,7 @@ PawnInfo* PawnInfoTable::get_pawn_info(const Position& pos) const {
   assert(pos.is_ok());
 
   Key key = pos.get_pawn_key();
-  unsigned index = unsigned(key & (size - 1));
+  unsigned index = unsigned(key & (PawnTableSize - 1));
   PawnInfo* pi = entries + index;
 
   // If pi->key matches the position's pawn hash key, it means that we
@@ -158,7 +149,8 @@ PawnInfo* PawnInfoTable::get_pawn_info(const Position& pos) const {
       return pi;
 
   // Clear the PawnInfo object, and set the key
-  pi->clear();
+  memset(pi, 0, sizeof(PawnInfo));
+  pi->kingSquares[WHITE] = pi->kingSquares[BLACK] = SQ_NONE;
   pi->key = key;
 
   // Calculate pawn attacks
@@ -268,7 +260,7 @@ Score PawnInfoTable::evaluate_pawns(const Position& pos, Bitboard ourPawns,
       // Mark the pawn as passed. Pawn will be properly scored in evaluation
       // because we need full attack info to evaluate passed pawns.
       if (passed)
-          set_bit(&(pi->passedPawns), s);
+          set_bit(&(pi->passedPawns[Us]), s);
 
       // Score this pawn
       if (isolated)
@@ -331,19 +323,24 @@ int PawnInfoTable::evaluate_pawn_storm(Square s, Rank r, File f, Bitboard theirP
 
 
 /// PawnInfo::updateShelter calculates and caches king shelter. It is called
-/// only when king square changes, about 20% of total get_king_shelter() calls.
-int PawnInfo::updateShelter(const Position& pos, Color c, Square ksq) {
+/// only when king square changes, about 20% of total king_shelter() calls.
+Score PawnInfo::updateShelter(const Position& pos, Color c, Square ksq) {
 
-  Bitboard pawns = pos.pieces(PAWN, c) & this_and_neighboring_files_bb(ksq);
-  unsigned shelter = 0;
-  unsigned r = ksq & (7 << 3);
+  Bitboard pawns;
+  unsigned r, k, shelter = 0;
 
-  for (int i = 1, k = (c ? -8 : 8); i < 4; i++)
+  if (relative_rank(c, ksq) <= RANK_4)
   {
-      r += k;
-      shelter += BitCount8Bit[(pawns >> r) & 0xFF] * (128 >> i);
+      pawns = pos.pieces(PAWN, c) & this_and_neighboring_files_bb(ksq);
+      r = ksq & (7 << 3);
+      k = (c ? -8 : 8);
+      for (int i = 1; i < 4; i++)
+      {
+          r += k;
+          shelter += BitCount8Bit[(pawns >> r) & 0xFF] * (128 >> i);
+      }
   }
   kingSquares[c] = ksq;
-  kingShelters[c] = shelter;
-  return shelter;
+  kingShelters[c] = make_score(shelter, 0);
+  return kingShelters[c];
 }
index f9ffba0..900b092 100644 (file)
@@ -32,6 +32,8 @@
 //// Types
 ////
 
+const int PawnTableSize = 16384;
+
 /// PawnInfo is a class which contains various information about a pawn
 /// structure. Currently, it only includes a middle game and an end game
 /// pawn structure evaluation, and a bitboard of passed pawns. We may want
@@ -45,30 +47,28 @@ class PawnInfo {
   friend class PawnInfoTable;
 
 public:
-  PawnInfo() { clear(); }
-
   Score pawns_value() const;
   Value kingside_storm_value(Color c) const;
   Value queenside_storm_value(Color c) const;
   Bitboard pawn_attacks(Color c) const;
-  Bitboard passed_pawns() const;
+  Bitboard passed_pawns(Color c) const;
   int file_is_half_open(Color c, File f) const;
   int has_open_file_to_left(Color c, File f) const;
   int has_open_file_to_right(Color c, File f) const;
-  int get_king_shelter(const Position& pos, Color c, Square ksq);
+  Score king_shelter(const Position& pos, Color c, Square ksq);
 
 private:
-  void clear();
-  int updateShelter(const Position& pos, Color c, Square ksq);
+  Score updateShelter(const Position& pos, Color c, Square ksq);
 
   Key key;
-  Bitboard passedPawns;
+  Bitboard passedPawns[2];
   Bitboard pawnAttacks[2];
   Square kingSquares[2];
   Score value;
-  int16_t ksStormValue[2], qsStormValue[2];
-  uint8_t halfOpenFiles[2];
-  uint8_t kingShelters[2];
+  int ksStormValue[2];
+  int qsStormValue[2];
+  int halfOpenFiles[2];
+  Score kingShelters[2];
 };
 
 /// The PawnInfoTable class represents a pawn hash table.  It is basically
@@ -81,9 +81,10 @@ class PawnInfoTable {
   enum SideType { KingSide, QueenSide };
 
 public:
-  PawnInfoTable(unsigned numOfEntries);
+  PawnInfoTable();
   ~PawnInfoTable();
   PawnInfo* get_pawn_info(const Position& pos) const;
+  void prefetch(Key key) const;
 
 private:
   template<Color Us>
@@ -92,7 +93,6 @@ private:
   template<Color Us, SideType Side>
   int evaluate_pawn_storm(Square s, Rank r, File f, Bitboard theirPawns) const;
 
-  unsigned size;
   PawnInfo* entries;
 };
 
@@ -101,12 +101,15 @@ private:
 //// Inline functions
 ////
 
-inline Score PawnInfo::pawns_value() const {
-  return value;
+inline void PawnInfoTable::prefetch(Key key) const {
+
+    unsigned index = unsigned(key & (PawnTableSize - 1));
+    PawnInfo* pi = entries + index;
+    ::prefetch((char*) pi);
 }
 
-inline Bitboard PawnInfo::passed_pawns() const {
-  return passedPawns;
+inline Score PawnInfo::pawns_value() const {
+  return value;
 }
 
 inline Bitboard PawnInfo::pawn_attacks(Color c) const {
@@ -121,6 +124,10 @@ inline Value PawnInfo::queenside_storm_value(Color c) const {
   return Value(qsStormValue[c]);
 }
 
+inline Bitboard PawnInfo::passed_pawns(Color c) const {
+  return passedPawns[c];
+}
+
 inline int PawnInfo::file_is_half_open(Color c, File f) const {
   return (halfOpenFiles[c] & (1 << int(f)));
 }
@@ -133,8 +140,8 @@ inline int PawnInfo::has_open_file_to_right(Color c, File f) const {
   return halfOpenFiles[c] & ~((1 << int(f+1)) - 1);
 }
 
-inline int PawnInfo::get_king_shelter(const Position& pos, Color c, Square ksq) {
-  return (kingSquares[c] == ksq ? kingShelters[c] : updateShelter(pos, c, ksq));
+inline Score PawnInfo::king_shelter(const Position& pos, Color c, Square ksq) {
+  return kingSquares[c] == ksq ? kingShelters[c] : updateShelter(pos, c, ksq);
 }
 
 #endif // !defined(PAWNS_H_INCLUDED)
index fb0a32f..10f0d87 100644 (file)
@@ -845,8 +845,9 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI
       // Reset rule 50 draw counter
       st->rule50 = 0;
 
-      // Update pawn hash key
+      // Update pawn hash key and prefetch in L1/L2 cache
       st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
+      prefetchPawn(st->pawnKey, threadID);
 
       // Set en passant square, only if moved pawn can be captured
       if ((to ^ from) == 16)