From: Marco Costalba Date: Sat, 21 Aug 2010 17:57:52 +0000 (+0200) Subject: Prefetch pawn hash key X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=7b721b3663920a2b74039ad6588ba4ed638c368b Prefetch pawn hash key 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 --- diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 43ef3c4f..375c2369 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -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 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(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) { diff --git a/src/material.cpp b/src/material.cpp index ffc549ca..ab0f5a89 100644 --- a/src/material.cpp +++ b/src/material.cpp @@ -23,6 +23,7 @@ //// #include +#include #include #include @@ -134,15 +135,14 @@ template<> const SFMap& EndgameFunctions::get() 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 diff --git a/src/material.h b/src/material.h index 5e8eb5fd..48be3494 100644 --- a/src/material.h +++ b/src/material.h @@ -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 diff --git a/src/misc.h b/src/misc.h index 4d9b2429..c6b6ecfd 100644 --- a/src/misc.h +++ b/src/misc.h @@ -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); //// diff --git a/src/pawns.cpp b/src/pawns.cpp index cec9aba1..0ab1c262 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -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]; } diff --git a/src/pawns.h b/src/pawns.h index f9ffba0c..900b0925 100644 --- a/src/pawns.h +++ b/src/pawns.h @@ -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 @@ -92,7 +93,6 @@ private: template 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) diff --git a/src/position.cpp b/src/position.cpp index fb0a32f3..10f0d874 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -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)