Speculative prefetch
Posted: Sun Sep 28, 2014 12:11 am
A while ago I implemented speculative prefetch in texel. The idea is to issue a prefetch instruction for the next needed transposition table probe before the move legality test in the parent search node. The prefetch is speculative for two reasons. First, if the move legality test fails, the prefetch is useless. Second, the computation of the zobrist hash key after the next move deliberately ignores special moves like castling, en passant and promotions, which means that the prefetch will load the wrong cache line for those moves.
In texel I measured a +6 elo increase at hyper bullet time control when using this optimization.
I decided to see if this optimization would work also in stockfish. Using the patch below, I measured a 2.8% speed increase for "stockfish bench". Before the change the average bench time was 3710ms +/- 5ms. After the change the average bench time was 3607ms +/- 7ms.
I have not played any games to verify this patch, but since it only affects speed it should also give an elo increase.
My computer is an Intel Core i7 870 @ 2.93GHz and my compiler is gcc 4.7.2. It would be interesting to know if there is a speed increase also for other computer/compiler combinations.
In texel I measured a +6 elo increase at hyper bullet time control when using this optimization.
I decided to see if this optimization would work also in stockfish. Using the patch below, I measured a 2.8% speed increase for "stockfish bench". Before the change the average bench time was 3710ms +/- 5ms. After the change the average bench time was 3607ms +/- 7ms.
I have not played any games to verify this patch, but since it only affects speed it should also give an elo increase.
My computer is an Intel Core i7 870 @ 2.93GHz and my compiler is gcc 4.7.2. It would be interesting to know if there is a speed increase also for other computer/compiler combinations.
Code: Select all
diff --git a/src/position.cpp b/src/position.cpp
index db4c857..ec59e8d 100644
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -1267,3 +1267,16 @@ bool Position::pos_is_ok(int* step) const {
return true;
}
+
+Key Position::hash_after_move(Move m) const {
+ int from = from_sq(m);
+ int to = to_sq(m);
+ Piece p = board[from];
+ Piece capP = board[to];
+ Key ret = st->key ^ Zobrist::side;
+ if (capP != NO_PIECE)
+ ret ^= Zobrist::psq[color_of(capP)][type_of(capP)][to];
+ ret ^= Zobrist::psq[color_of(p)][type_of(p)][to];
+ ret ^= Zobrist::psq[color_of(p)][type_of(p)][from];
+ return ret;
+}
diff --git a/src/position.h b/src/position.h
index 8f5fb75..7565abb 100644
--- a/src/position.h
+++ b/src/position.h
@@ -139,6 +139,7 @@ public:
void undo_move(Move m);
void do_null_move(StateInfo& st);
void undo_null_move();
+ Key hash_after_move(Move m) const;
// Static exchange evaluation
Value see(Move m) const;
diff --git a/src/search.cpp b/src/search.cpp
index 6215b08..7cabff6 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -796,6 +796,8 @@ moves_loop: // When in check and at SpNode search starts from here
}
}
+ prefetch((char*)TT.first_entry(pos.hash_after_move(move)));
+
// Check for legality just before making the move
if (!RootNode && !SpNode && !pos.legal(move, ci.pinned))
{
@@ -1145,6 +1147,8 @@ moves_loop: // When in check and at SpNode search starts from here
&& pos.see_sign(move) < VALUE_ZERO)
continue;
+ prefetch((char*)TT.first_entry(pos.hash_after_move(move)));
+
// Check for legality just before making the move
if (!pos.legal(move, ci.pinned))
continue;