From: Marco Costalba Date: Sun, 9 Aug 2009 14:53:51 +0000 (+0100) Subject: Try to prefetch as soon as position key is ready X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=4251eac8601af47d1ee2d6f613f00a4bf00fedbb Try to prefetch as soon as position key is ready Move prefetching code inside do_move() so to allow a very early prefetching and to put as many instructions as possible between prefetching and following retrieve(). With this patch retrieve() times are cutted of another 25% No functional change. Signed-off-by: Marco Costalba --- diff --git a/src/position.cpp b/src/position.cpp index d1e3f448..874c7545 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -34,6 +34,7 @@ #include "position.h" #include "psqtab.h" #include "san.h" +#include "tt.h" #include "ucioption.h" using std::string; @@ -71,6 +72,14 @@ Position::Position(const string& fen) { } +/// Position::setTranspositionTable() is used by search functions to pass +/// the pointer to the used TT so that do_move() will prefetch TT access. + +void Position::setTranspositionTable(TranspositionTable* tt) { + TT = tt; +} + + /// Position::from_fen() initializes the position object with the given FEN /// string. This function is not very robust - make sure that input FENs are /// correct (this is assumed to be the responsibility of the GUI). @@ -743,25 +752,9 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) { if (st->capture) do_capture_move(st->capture, them, to); - // Move the piece - Bitboard move_bb = make_move_bb(from, to); - do_move_bb(&(byColorBB[us]), move_bb); - do_move_bb(&(byTypeBB[pt]), move_bb); - do_move_bb(&(byTypeBB[0]), move_bb); // HACK: byTypeBB[0] == occupied squares - - board[to] = board[from]; - board[from] = EMPTY; - // Update hash key st->key ^= zobrist[us][pt][from] ^ zobrist[us][pt][to]; - - // Update incremental scores - st->mgValue += pst_delta(piece, from, to); - st->egValue += pst_delta(piece, from, to); - - // If the moving piece was a king, update the king square - if (pt == KING) - kingSquare[us] = to; + st->key ^= zobSideToMove; // Reset en passant square if (st->epSquare != SQ_NONE) @@ -770,6 +763,30 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) { st->epSquare = SQ_NONE; } + // Update castle rights, try to shortcut a common case + if ((castleRightsMask[from] & castleRightsMask[to]) != ALL_CASTLES) + { + st->key ^= zobCastle[st->castleRights]; + st->castleRights &= castleRightsMask[from]; + st->castleRights &= castleRightsMask[to]; + st->key ^= zobCastle[st->castleRights]; + } + + bool checkEpSquare = (pt == PAWN && abs(int(to) - int(from)) == 16); + + // Prefetch TT access as soon as we know key is updated + if (!checkEpSquare && TT) + TT->prefetch(st->key); + + // Move the piece + Bitboard move_bb = make_move_bb(from, to); + do_move_bb(&(byColorBB[us]), move_bb); + do_move_bb(&(byTypeBB[pt]), move_bb); + do_move_bb(&(byTypeBB[0]), move_bb); // HACK: byTypeBB[0] == occupied squares + + board[to] = board[from]; + board[from] = EMPTY; + // If the moving piece was a pawn do some special extra work if (pt == PAWN) { @@ -780,7 +797,7 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) { st->pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to]; // Set en passant square, only if moved pawn can be captured - if (abs(int(to) - int(from)) == 16) + if (checkEpSquare) { if ( (us == WHITE && (pawn_attacks(WHITE, from + DELTA_N) & pawns(BLACK))) || (us == BLACK && (pawn_attacks(BLACK, from + DELTA_S) & pawns(WHITE)))) @@ -791,19 +808,22 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) { } } + // Prefetch only here in the few cases we needed zobEp[] to update the key + if (checkEpSquare && TT) + TT->prefetch(st->key); + + // Update incremental scores + st->mgValue += pst_delta(piece, from, to); + st->egValue += pst_delta(piece, from, to); + + // If the moving piece was a king, update the king square + if (pt == KING) + kingSquare[us] = to; + // Update piece lists pieceList[us][pt][index[from]] = to; index[to] = index[from]; - // Update castle rights, try to shortcut a common case - if ((castleRightsMask[from] & castleRightsMask[to]) != ALL_CASTLES) - { - st->key ^= zobCastle[st->castleRights]; - st->castleRights &= castleRightsMask[from]; - st->castleRights &= castleRightsMask[to]; - st->key ^= zobCastle[st->castleRights]; - } - // Update checkers bitboard, piece must be already moved st->checkersBB = EmptyBoardBB; Square ksq = king_square(them); @@ -820,7 +840,6 @@ void Position::do_move(Move m, StateInfo& newSt, Bitboard dcCandidates) { } // Finish - st->key ^= zobSideToMove; sideToMove = opposite_color(sideToMove); gamePly++; @@ -960,6 +979,8 @@ void Position::do_castle_move(Move m) { // Update checkers BB st->checkersBB = attacks_to(king_square(them), us); + + st->key ^= zobSideToMove; } @@ -1050,6 +1071,8 @@ void Position::do_promotion_move(Move m) { // Update checkers BB st->checkersBB = attacks_to(king_square(them), us); + + st->key ^= zobSideToMove; } @@ -1127,6 +1150,8 @@ void Position::do_ep_move(Move m) { // Update checkers BB st->checkersBB = attacks_to(king_square(them), us); + + st->key ^= zobSideToMove; } @@ -1407,14 +1432,15 @@ void Position::do_null_move(StateInfo& backupSt) { history[gamePly] = st->key; // Update the necessary information - sideToMove = opposite_color(sideToMove); if (st->epSquare != SQ_NONE) st->key ^= zobEp[st->epSquare]; + st->key ^= zobSideToMove; + TT->prefetch(st->key); + sideToMove = opposite_color(sideToMove); st->epSquare = SQ_NONE; st->rule50++; gamePly++; - st->key ^= zobSideToMove; st->mgValue += (sideToMove == WHITE)? TempoValueMidgame : -TempoValueMidgame; st->egValue += (sideToMove == WHITE)? TempoValueEndgame : -TempoValueEndgame; @@ -1654,6 +1680,7 @@ void Position::clear() { initialKFile = FILE_E; initialKRFile = FILE_H; initialQRFile = FILE_A; + TT = NULL; } diff --git a/src/position.h b/src/position.h index e48be111..ba4caf13 100644 --- a/src/position.h +++ b/src/position.h @@ -98,6 +98,7 @@ struct StateInfo { StateInfo* previous; }; +class TranspositionTable; /// The position data structure. A position consists of the following data: /// @@ -258,6 +259,7 @@ public: void undo_move(Move m); void do_null_move(StateInfo& st); void undo_null_move(); + void setTranspositionTable(TranspositionTable* tt); // Static exchange evaluation int see(Square from, Square to) const; @@ -356,6 +358,7 @@ private: File initialKFile, initialKRFile, initialQRFile; StateInfo startState; StateInfo* st; + TranspositionTable* TT; // Static variables static int castleRightsMask[64]; diff --git a/src/search.cpp b/src/search.cpp index 61475a2f..32d1a8bd 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -663,6 +663,7 @@ namespace { // Initialize TT.new_search(); + p.setTranspositionTable(&TT); H.clear(); for (int i = 0; i < 3; i++) { @@ -1126,7 +1127,6 @@ namespace { // Make and search the move StateInfo st; pos.do_move(move, st, dcCandidates); - TT.prefetch(pos.get_key()); if (moveCount == 1) // The first move in list is the PV value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID); @@ -1297,8 +1297,6 @@ namespace { StateInfo st; pos.do_null_move(st); - TT.prefetch(pos.get_key()); - int R = (depth >= 5 * OnePly ? 4 : 3); // Null move dynamic reduction Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID); @@ -1413,7 +1411,6 @@ namespace { // Make and search the move StateInfo st; pos.do_move(move, st, dcCandidates); - TT.prefetch(pos.get_key()); // Try to reduce non-pv search depth by one ply if move seems not problematic, // if the move fails high will be re-searched at full depth. @@ -1623,7 +1620,6 @@ namespace { // Make and search the move. StateInfo st; pos.do_move(move, st, dcCandidates); - TT.prefetch(pos.get_key()); Value value = -qsearch(pos, ss, -beta, -alpha, depth-OnePly, ply+1, threadID); pos.undo_move(move); diff --git a/src/tt.cpp b/src/tt.cpp index f2313eab..8ef2a635 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -93,6 +93,16 @@ void TranspositionTable::clear() { } +/// TranspositionTable::first_entry returns a pointer to the first +/// 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 { + + return entries + ((uint32_t(posKey) & (size - 1)) * ClusterSize); +} + + /// TranspositionTable::store writes a new entry containing a position, /// a value, a value type, a search depth, and a best move to the /// transposition table. Transposition table is organized in clusters of @@ -145,7 +155,7 @@ void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d, 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 < ClusterSize; i++, tte++) if (tte->key() == posKey32) @@ -154,6 +164,7 @@ TTEntry* TranspositionTable::retrieve(const Key posKey) const { return NULL; } + /// TranspositionTable::prefetch looks up the current position in the /// transposition table and load it in L1/L2 cache. This is a non /// blocking function and do not stalls the CPU waiting for data @@ -166,14 +177,6 @@ void TranspositionTable::prefetch(const Key posKey) const { _mm_prefetch((char*)first_entry(posKey), _MM_HINT_T0); } -/// TranspositionTable::first_entry returns a pointer to the first -/// 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 { - - return entries + ((uint32_t(posKey) & (size - 1)) * ClusterSize); -} /// TranspositionTable::new_search() is called at the beginning of every new /// search. It increments the "generation" variable, which is used to