From: Marco Costalba Date: Sat, 31 Mar 2012 11:15:57 +0000 (+0100) Subject: Use std::vector to implement HashTable X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=32c504076f5a1d5c84f88c2d30a11c25ea2e5a6e Use std::vector to implement HashTable 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 --- diff --git a/src/endgame.h b/src/endgame.h index 70f795cd..61b8c096 100644 --- a/src/endgame.h +++ b/src/endgame.h @@ -112,7 +112,7 @@ public: Endgames(); ~Endgames(); - template EndgameBase* get(Key key) { + template EndgameBase* probe(Key key) { return map((T*)0).count(key) ? map((T*)0)[key] : NULL; } }; diff --git a/src/main.cpp b/src/main.cpp index 3dcb3f6d..505f2ef3 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -25,6 +25,7 @@ #include "position.h" #include "search.h" #include "thread.h" +#include "tt.h" #include "ucioption.h" using namespace std; diff --git a/src/material.cpp b/src/material.cpp index d13b3091..0e3ca832 100644 --- a/src/material.cpp +++ b/src/material.cpp @@ -17,9 +17,9 @@ along with this program. If not, see . */ +#include #include #include -#include #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(key)) != NULL) - return mi; + if ((e->evaluationFunction = endgames.probe(key)) != NULL) + return e; if (is_KXK(pos)) { - mi->evaluationFunction = &EvaluateKXK[WHITE]; - return mi; + e->evaluationFunction = &EvaluateKXK[WHITE]; + return e; } if (is_KXK(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* sf; - if ((sf = funcs->get(key)) != NULL) + if ((sf = endgames.probe(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(pos)) - mi->scalingFunction[WHITE] = &ScaleKBPsK[WHITE]; + e->scalingFunction[WHITE] = &ScaleKBPsK[WHITE]; if (is_KBPsKs(pos)) - mi->scalingFunction[BLACK] = &ScaleKBPsK[BLACK]; + e->scalingFunction[BLACK] = &ScaleKBPsK[BLACK]; if (is_KQKRPs(pos)) - mi->scalingFunction[WHITE] = &ScaleKQKRPs[WHITE]; + e->scalingFunction[WHITE] = &ScaleKQKRPs[WHITE]; else if (is_KQKRPs(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(pieceCount) - imbalance(pieceCount)) / 16); - return mi; + e->value = (int16_t)((imbalance(pieceCount) - imbalance(pieceCount)) / 16); + return e; } diff --git a/src/material.h b/src/material.h index c5484c49..75074f91 100644 --- a/src/material.h +++ b/src/material.h @@ -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 { -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 static int imbalance(const int pieceCount[][8]); -private: - template - static int imbalance(const int pieceCount[][8]); - - Endgames* funcs; + HashTable entries; + Endgames endgames; }; diff --git a/src/misc.h b/src/misc.h index 8d21c1ad..d6bc2672 100644 --- a/src/misc.h +++ b/src/misc.h @@ -22,6 +22,7 @@ #include #include +#include #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 +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 e; +}; + #endif // !defined(MISC_H_INCLUDED) diff --git a/src/pawns.cpp b/src/pawns.cpp index f2e0c4c3..795e31e2 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -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(pos, wPawns, bPawns, pi) - - evaluate_pawns(pos, bPawns, wPawns, pi); + e->value = evaluate_pawns(pos, wPawns, bPawns, e) + - evaluate_pawns(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 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) diff --git a/src/pawns.h b/src/pawns.h index 6a8c4d7a..0376ce61 100644 --- a/src/pawns.h +++ b/src/pawns.h @@ -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 { -public: - PawnEntry* probe(const Position& pos) const; +struct PawnTable { + + PawnEntry* probe(const Position& pos); -private: template static Score evaluate_pawns(const Position& pos, Bitboard ourPawns, - Bitboard theirPawns, PawnEntry* pi); + Bitboard theirPawns, PawnEntry* e); + + HashTable entries; }; diff --git a/src/position.cpp b/src/position.cpp index 12ef1a30..879ac442 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -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); diff --git a/src/tt.h b/src/tt.h index 1e344c3f..3edd5e8a 100644 --- a/src/tt.h +++ b/src/tt.h @@ -20,12 +20,9 @@ #if !defined(TT_H_INCLUDED) #define TT_H_INCLUDED -#include - #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(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 -struct HashTable { - - typedef HashTable 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)