Use std::vector to implement HashTable
authorMarco Costalba <mcostalba@gmail.com>
Sat, 31 Mar 2012 11:15:57 +0000 (12:15 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 31 Mar 2012 18:07:11 +0000 (19:07 +0100)
Allows some code semplification and avoids directly
allocation and managing heap memory.

Also the usual renaming while there.

No functional change and no speed regression.

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

index 70f795c..61b8c09 100644 (file)
@@ -112,7 +112,7 @@ public:
   Endgames();
   ~Endgames();
 
-  template<typename T> EndgameBase<T>* get(Key key) {
+  template<typename T> EndgameBase<T>* probe(Key key) {
     return map((T*)0).count(key) ? map((T*)0)[key] : NULL;
   }
 };
index 3dcb3f6..505f2ef 100644 (file)
@@ -25,6 +25,7 @@
 #include "position.h"
 #include "search.h"
 #include "thread.h"
+#include "tt.h"
 #include "ucioption.h"
 
 using namespace std;
index d13b309..0e3ca83 100644 (file)
@@ -17,9 +17,9 @@
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+#include <algorithm>
 #include <cassert>
 #include <cstring>
-#include <algorithm>
 
 #include "material.h"
 
@@ -89,38 +89,38 @@ namespace {
 /// already present in the table, it is computed and stored there, so we don't
 /// have to recompute everything when the same material configuration occurs again.
 
-MaterialEntry* MaterialTable::probe(const Position& pos) const {
+MaterialEntry* MaterialTable::probe(const Position& pos) {
 
   Key key = pos.material_key();
-  MaterialEntry* mi = Base::probe(key);
+  MaterialEntry* e = entries[key];
 
-  // If mi->key matches the position's material hash key, it means that we
+  // If e->key matches the position's material hash key, it means that we
   // have analysed this material configuration before, and we can simply
   // return the information we found the last time instead of recomputing it.
-  if (mi->key == key)
-      return mi;
+  if (e->key == key)
+      return e;
 
-  memset(mi, 0, sizeof(MaterialEntry));
-  mi->key = key;
-  mi->factor[WHITE] = mi->factor[BLACK] = (uint8_t)SCALE_FACTOR_NORMAL;
-  mi->gamePhase = MaterialTable::game_phase(pos);
+  memset(e, 0, sizeof(MaterialEntry));
+  e->key = key;
+  e->factor[WHITE] = e->factor[BLACK] = (uint8_t)SCALE_FACTOR_NORMAL;
+  e->gamePhase = MaterialTable::game_phase(pos);
 
   // Let's look if we have a specialized evaluation function for this
   // particular material configuration. First we look for a fixed
   // configuration one, then a generic one if previous search failed.
-  if ((mi->evaluationFunction = funcs->get<Value>(key)) != NULL)
-      return mi;
+  if ((e->evaluationFunction = endgames.probe<Value>(key)) != NULL)
+      return e;
 
   if (is_KXK<WHITE>(pos))
   {
-      mi->evaluationFunction = &EvaluateKXK[WHITE];
-      return mi;
+      e->evaluationFunction = &EvaluateKXK[WHITE];
+      return e;
   }
 
   if (is_KXK<BLACK>(pos))
   {
-      mi->evaluationFunction = &EvaluateKXK[BLACK];
-      return mi;
+      e->evaluationFunction = &EvaluateKXK[BLACK];
+      return e;
   }
 
   if (!pos.pieces(PAWN) && !pos.pieces(ROOK) && !pos.pieces(QUEEN))
@@ -133,8 +133,8 @@ MaterialEntry* MaterialTable::probe(const Position& pos) const {
       if (   pos.piece_count(WHITE, BISHOP) + pos.piece_count(WHITE, KNIGHT) <= 2
           && pos.piece_count(BLACK, BISHOP) + pos.piece_count(BLACK, KNIGHT) <= 2)
       {
-          mi->evaluationFunction = &EvaluateKmmKm[pos.side_to_move()];
-          return mi;
+          e->evaluationFunction = &EvaluateKmmKm[pos.side_to_move()];
+          return e;
       }
   }
 
@@ -145,26 +145,26 @@ MaterialEntry* MaterialTable::probe(const Position& pos) const {
   // scaling functions and we need to decide which one to use.
   EndgameBase<ScaleFactor>* sf;
 
-  if ((sf = funcs->get<ScaleFactor>(key)) != NULL)
+  if ((sf = endgames.probe<ScaleFactor>(key)) != NULL)
   {
-      mi->scalingFunction[sf->color()] = sf;
-      return mi;
+      e->scalingFunction[sf->color()] = sf;
+      return e;
   }
 
   // Generic scaling functions that refer to more then one material
   // distribution. Should be probed after the specialized ones.
   // Note that these ones don't return after setting the function.
   if (is_KBPsKs<WHITE>(pos))
-      mi->scalingFunction[WHITE] = &ScaleKBPsK[WHITE];
+      e->scalingFunction[WHITE] = &ScaleKBPsK[WHITE];
 
   if (is_KBPsKs<BLACK>(pos))
-      mi->scalingFunction[BLACK] = &ScaleKBPsK[BLACK];
+      e->scalingFunction[BLACK] = &ScaleKBPsK[BLACK];
 
   if (is_KQKRPs<WHITE>(pos))
-      mi->scalingFunction[WHITE] = &ScaleKQKRPs[WHITE];
+      e->scalingFunction[WHITE] = &ScaleKQKRPs[WHITE];
 
   else if (is_KQKRPs<BLACK>(pos))
-      mi->scalingFunction[BLACK] = &ScaleKQKRPs[BLACK];
+      e->scalingFunction[BLACK] = &ScaleKQKRPs[BLACK];
 
   Value npm_w = pos.non_pawn_material(WHITE);
   Value npm_b = pos.non_pawn_material(BLACK);
@@ -174,32 +174,32 @@ MaterialEntry* MaterialTable::probe(const Position& pos) const {
       if (pos.piece_count(BLACK, PAWN) == 0)
       {
           assert(pos.piece_count(WHITE, PAWN) >= 2);
-          mi->scalingFunction[WHITE] = &ScaleKPsK[WHITE];
+          e->scalingFunction[WHITE] = &ScaleKPsK[WHITE];
       }
       else if (pos.piece_count(WHITE, PAWN) == 0)
       {
           assert(pos.piece_count(BLACK, PAWN) >= 2);
-          mi->scalingFunction[BLACK] = &ScaleKPsK[BLACK];
+          e->scalingFunction[BLACK] = &ScaleKPsK[BLACK];
       }
       else if (pos.piece_count(WHITE, PAWN) == 1 && pos.piece_count(BLACK, PAWN) == 1)
       {
           // This is a special case because we set scaling functions
           // for both colors instead of only one.
-          mi->scalingFunction[WHITE] = &ScaleKPKP[WHITE];
-          mi->scalingFunction[BLACK] = &ScaleKPKP[BLACK];
+          e->scalingFunction[WHITE] = &ScaleKPKP[WHITE];
+          e->scalingFunction[BLACK] = &ScaleKPKP[BLACK];
       }
   }
 
   // No pawns makes it difficult to win, even with a material advantage
   if (pos.piece_count(WHITE, PAWN) == 0 && npm_w - npm_b <= BishopValueMidgame)
   {
-      mi->factor[WHITE] = (uint8_t)
+      e->factor[WHITE] = (uint8_t)
       (npm_w == npm_b || npm_w < RookValueMidgame ? 0 : NoPawnsSF[std::min(pos.piece_count(WHITE, BISHOP), 2)]);
   }
 
   if (pos.piece_count(BLACK, PAWN) == 0 && npm_b - npm_w <= BishopValueMidgame)
   {
-      mi->factor[BLACK] = (uint8_t)
+      e->factor[BLACK] = (uint8_t)
       (npm_w == npm_b || npm_b < RookValueMidgame ? 0 : NoPawnsSF[std::min(pos.piece_count(BLACK, BISHOP), 2)]);
   }
 
@@ -209,7 +209,7 @@ MaterialEntry* MaterialTable::probe(const Position& pos) const {
       int minorPieceCount =  pos.piece_count(WHITE, KNIGHT) + pos.piece_count(WHITE, BISHOP)
                            + pos.piece_count(BLACK, KNIGHT) + pos.piece_count(BLACK, BISHOP);
 
-      mi->spaceWeight = minorPieceCount * minorPieceCount;
+      e->spaceWeight = minorPieceCount * minorPieceCount;
   }
 
   // Evaluate the material imbalance. We use PIECE_TYPE_NONE as a place holder
@@ -221,8 +221,8 @@ MaterialEntry* MaterialTable::probe(const Position& pos) const {
   { pos.piece_count(BLACK, BISHOP) > 1, pos.piece_count(BLACK, PAWN), pos.piece_count(BLACK, KNIGHT),
     pos.piece_count(BLACK, BISHOP)    , pos.piece_count(BLACK, ROOK), pos.piece_count(BLACK, QUEEN) } };
 
-  mi->value = (int16_t)((imbalance<WHITE>(pieceCount) - imbalance<BLACK>(pieceCount)) / 16);
-  return mi;
+  e->value = (int16_t)((imbalance<WHITE>(pieceCount) - imbalance<BLACK>(pieceCount)) / 16);
+  return e;
 }
 
 
index c5484c4..75074f9 100644 (file)
@@ -21,8 +21,8 @@
 #define MATERIAL_H_INCLUDED
 
 #include "endgame.h"
+#include "misc.h"
 #include "position.h"
-#include "tt.h"
 #include "types.h"
 
 const int MaterialTableSize = 8192;
@@ -46,7 +46,7 @@ enum Phase {
 
 class MaterialEntry {
 
-  friend class MaterialTable;
+  friend struct MaterialTable;
 
 public:
   Score material_value() const;
@@ -70,19 +70,14 @@ private:
 /// The MaterialTable class represents a material hash table. The most important
 /// method is probe(), which returns a pointer to a MaterialEntry object.
 
-class MaterialTable : public HashTable<MaterialEntry, MaterialTableSize> {
-public:
-  MaterialTable() : funcs(new Endgames()) {}
-  ~MaterialTable() { delete funcs; }
+struct MaterialTable {
 
-  MaterialEntry* probe(const Position& pos) const;
+  MaterialEntry* probe(const Position& pos);
   static Phase game_phase(const Position& pos);
+  template<Color Us> static int imbalance(const int pieceCount[][8]);
 
-private:
-  template<Color Us>
-  static int imbalance(const int pieceCount[][8]);
-
-  Endgames* funcs;
+  HashTable<MaterialEntry, MaterialTableSize> entries;
+  Endgames endgames;
 };
 
 
index 8d21c1a..d6bc267 100644 (file)
@@ -22,6 +22,7 @@
 
 #include <fstream>
 #include <string>
+#include <vector>
 
 #include "types.h"
 
@@ -48,8 +49,7 @@ struct Log : public std::ofstream {
 };
 
 
-class Time {
-public:
+struct Time {
   void restart() { system_time(&t); }
   uint64_t msec() const { return time_to_msec(t); }
   int elapsed() const { return int(current_time().msec() - time_to_msec(t)); }
@@ -60,4 +60,14 @@ private:
   sys_time_t t;
 };
 
+
+template<class Entry, int Size>
+struct HashTable {
+  HashTable() : e(Size, Entry()) { memset(&e[0], 0, sizeof(Entry) * Size); }
+  Entry* operator[](Key k) { return &e[(uint32_t)k & (Size - 1)]; }
+
+private:
+  std::vector<Entry> e;
+};
+
 #endif // !defined(MISC_H_INCLUDED)
index f2e0c4c..795e31e 100644 (file)
@@ -88,33 +88,33 @@ namespace {
 /// table, so we don't have to recompute everything when the same pawn structure
 /// occurs again.
 
-PawnEntry* PawnTable::probe(const Position& pos) const {
+PawnEntry* PawnTable::probe(const Position& pos) {
 
   Key key = pos.pawn_key();
-  PawnEntry* pi = Base::probe(key);
+  PawnEntry* e = entries[key];
 
-  // If pi->key matches the position's pawn hash key, it means that we
+  // If e->key matches the position's pawn hash key, it means that we
   // have analysed this pawn structure before, and we can simply return
   // the information we found the last time instead of recomputing it.
-  if (pi->key == key)
-      return pi;
+  if (e->key == key)
+      return e;
 
-  pi->key = key;
-  pi->passedPawns[WHITE] = pi->passedPawns[BLACK] = 0;
-  pi->kingSquares[WHITE] = pi->kingSquares[BLACK] = SQ_NONE;
-  pi->halfOpenFiles[WHITE] = pi->halfOpenFiles[BLACK] = 0xFF;
+  e->key = key;
+  e->passedPawns[WHITE] = e->passedPawns[BLACK] = 0;
+  e->kingSquares[WHITE] = e->kingSquares[BLACK] = SQ_NONE;
+  e->halfOpenFiles[WHITE] = e->halfOpenFiles[BLACK] = 0xFF;
 
   Bitboard wPawns = pos.pieces(PAWN, WHITE);
   Bitboard bPawns = pos.pieces(PAWN, BLACK);
-  pi->pawnAttacks[WHITE] = ((wPawns & ~FileHBB) << 9) | ((wPawns & ~FileABB) << 7);
-  pi->pawnAttacks[BLACK] = ((bPawns & ~FileHBB) >> 7) | ((bPawns & ~FileABB) >> 9);
+  e->pawnAttacks[WHITE] = ((wPawns & ~FileHBB) << 9) | ((wPawns & ~FileABB) << 7);
+  e->pawnAttacks[BLACK] = ((bPawns & ~FileHBB) >> 7) | ((bPawns & ~FileABB) >> 9);
 
-  pi->value =  evaluate_pawns<WHITE>(pos, wPawns, bPawns, pi)
-             - evaluate_pawns<BLACK>(pos, bPawns, wPawns, pi);
+  e->value =  evaluate_pawns<WHITE>(pos, wPawns, bPawns, e)
+            - evaluate_pawns<BLACK>(pos, bPawns, wPawns, e);
 
-  pi->value = apply_weight(pi->value, PawnStructureWeight);
+  e->value = apply_weight(e->value, PawnStructureWeight);
 
-  return pi;
+  return e;
 }
 
 
@@ -122,7 +122,7 @@ PawnEntry* PawnTable::probe(const Position& pos) const {
 
 template<Color Us>
 Score PawnTable::evaluate_pawns(const Position& pos, Bitboard ourPawns,
-                                    Bitboard theirPawns, PawnEntry* pi) {
+                                Bitboard theirPawns, PawnEntry* e) {
 
   const Color Them = (Us == WHITE ? BLACK : WHITE);
 
@@ -143,7 +143,7 @@ Score PawnTable::evaluate_pawns(const Position& pos, Bitboard ourPawns,
       r = rank_of(s);
 
       // This file cannot be half open
-      pi->halfOpenFiles[Us] &= ~(1 << f);
+      e->halfOpenFiles[Us] &= ~(1 << f);
 
       // Our rank plus previous one. Used for chain detection
       b = rank_bb(r) | rank_bb(Us == WHITE ? r - Rank(1) : r + Rank(1));
@@ -196,7 +196,7 @@ Score PawnTable::evaluate_pawns(const Position& pos, Bitboard ourPawns,
       // full attack info to evaluate passed pawns. Only the frontmost passed
       // pawn on each file is considered a true passed pawn.
       if (passed && !doubled)
-          pi->passedPawns[Us] |= s;
+          e->passedPawns[Us] |= s;
 
       // Score this pawn
       if (isolated)
index 6a8c4d7..0376ce6 100644 (file)
@@ -20,8 +20,8 @@
 #if !defined(PAWNS_H_INCLUDED)
 #define PAWNS_H_INCLUDED
 
+#include "misc.h"
 #include "position.h"
-#include "tt.h"
 #include "types.h"
 
 const int PawnTableSize = 16384;
@@ -35,7 +35,7 @@ const int PawnTableSize = 16384;
 
 class PawnEntry {
 
-  friend class PawnTable;
+  friend struct PawnTable;
 
 public:
   Score pawns_value() const;
@@ -68,14 +68,15 @@ private:
 /// The PawnTable class represents a pawn hash table. The most important
 /// method is probe, which returns a pointer to a PawnEntry object.
 
-class PawnTable : public HashTable<PawnEntry, PawnTableSize> {
-public:
-  PawnEntry* probe(const Position& pos) const;
+struct PawnTable {
+
+  PawnEntry* probe(const Position& pos);
 
-private:
   template<Color Us>
   static Score evaluate_pawns(const Position& pos, Bitboard ourPawns,
-                              Bitboard theirPawns, PawnEntry* pi);
+                              Bitboard theirPawns, PawnEntry* e);
+
+  HashTable<PawnEntry, PawnTableSize> entries;
 };
 
 
index 12ef1a3..879ac44 100644 (file)
@@ -903,8 +903,8 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI
   }
 
   // Prefetch pawn and material hash tables
-  Threads[threadID].pawnTable.prefetch(st->pawnKey);
-  Threads[threadID].materialTable.prefetch(st->materialKey);
+  prefetch((char*)Threads[threadID].pawnTable.entries[st->pawnKey]);
+  prefetch((char*)Threads[threadID].materialTable.entries[st->materialKey]);
 
   // Update incremental scores
   st->value += pst_delta(piece, from, to);
index 1e344c3..3edd5e8 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
 #if !defined(TT_H_INCLUDED)
 #define TT_H_INCLUDED
 
-#include <iostream>
-
 #include "misc.h"
 #include "types.h"
 
-
 /// The TTEntry is the class of transposition table entries
 ///
 /// A TTEntry needs 128 bits to be stored
@@ -136,35 +133,4 @@ inline void TranspositionTable::refresh(const TTEntry* tte) const {
   const_cast<TTEntry*>(tte)->set_generation(generation);
 }
 
-
-/// A simple hash table used to store pawns and material configurations. It is
-/// basically just an array of Entry objects. Without cluster concept, overwrite
-/// policy nor resizing.
-
-template<class Entry, int HashSize>
-struct HashTable {
-
-  typedef HashTable<Entry, HashSize> Base;
-
-  HashTable() {
-
-    entries = new (std::nothrow) Entry[HashSize];
-    if (!entries)
-    {
-        std::cerr << "Failed to allocate " << HashSize * sizeof(Entry)
-                  << " bytes for hash table." << std::endl;
-        ::exit(EXIT_FAILURE);
-    }
-    memset(entries, 0, HashSize * sizeof(Entry));
-  }
-
-  virtual ~HashTable() { delete [] entries; }
-
-  Entry* probe(Key key) const { return entries + ((uint32_t)key & (HashSize - 1)); }
-  void prefetch(Key key) const { ::prefetch((char*)probe(key)); }
-
-private:
-  Entry* entries;
-};
-
 #endif // !defined(TT_H_INCLUDED)