From 2f6142cb9bd9db2a749fa3faad4d0ef793336ddb Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 4 Jun 2011 16:36:52 +0100 Subject: [PATCH 1/1] Try to keep memory access in the same cache line Signed-off-by: Marco Costalba --- src/bitboard.cpp | 91 ++++++++++++++++++++++++------------------------ src/bitboard.h | 55 +++++++++++++++-------------- 2 files changed, 74 insertions(+), 72 deletions(-) diff --git a/src/bitboard.cpp b/src/bitboard.cpp index fd4cd1ef..db2d9a05 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -22,9 +22,40 @@ #include "bitboard.h" #include "bitcount.h" +// Global bitboards definitions with static storage duration are +// automatically set to zero before enter main(). +Bitboard RAttacks[0x19000]; +Bitboard BAttacks[0x1480]; + +Magics RMagics[64]; +Magics BMagics[64]; + +Bitboard SetMaskBB[65]; +Bitboard ClearMaskBB[65]; + +Bitboard SquaresByColorBB[2]; +Bitboard FileBB[8]; +Bitboard RankBB[8]; +Bitboard NeighboringFilesBB[8]; +Bitboard ThisAndNeighboringFilesBB[8]; +Bitboard InFrontBB[2][8]; +Bitboard StepAttacksBB[16][64]; +Bitboard BetweenBB[64][64]; +Bitboard SquaresInFrontMask[2][64]; +Bitboard PassedPawnMask[2][64]; +Bitboard AttackSpanMask[2][64]; + +Bitboard BishopPseudoAttacks[64]; +Bitboard RookPseudoAttacks[64]; +Bitboard QueenPseudoAttacks[64]; + +uint8_t BitCount8Bit[256]; + +namespace { + #if defined(IS_64BIT) -static const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL; +const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL; const uint64_t BMult[64] = { 0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL, @@ -92,7 +123,7 @@ const int RShift[64] = { #else // if !defined(IS_64BIT) -static const uint32_t DeBruijnMagic = 0x783A9B23; +const uint32_t DeBruijnMagic = 0x783A9B23; const uint64_t BMult[64] = { 0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL, @@ -160,44 +191,10 @@ const int RShift[64] = { #endif // defined(IS_64BIT) -// Global bitboards definitions with static storage duration are -// automatically set to zero before enter main(). -Bitboard RMask[64]; -int RAttackIndex[64]; -Bitboard RAttacks[0x19000]; - -Bitboard BMask[64]; -int BAttackIndex[64]; -Bitboard BAttacks[0x1480]; - -Bitboard SetMaskBB[65]; -Bitboard ClearMaskBB[65]; - -Bitboard SquaresByColorBB[2]; -Bitboard FileBB[8]; -Bitboard RankBB[8]; -Bitboard NeighboringFilesBB[8]; -Bitboard ThisAndNeighboringFilesBB[8]; -Bitboard InFrontBB[2][8]; -Bitboard StepAttacksBB[16][64]; -Bitboard BetweenBB[64][64]; -Bitboard SquaresInFrontMask[2][64]; -Bitboard PassedPawnMask[2][64]; -Bitboard AttackSpanMask[2][64]; - -Bitboard BishopPseudoAttacks[64]; -Bitboard RookPseudoAttacks[64]; -Bitboard QueenPseudoAttacks[64]; - -uint8_t BitCount8Bit[256]; - - -namespace { - CACHE_LINE_ALIGNMENT int BSFTable[64]; - void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], - const int shift[], const Bitboard mult[], int deltas[][2]); + void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[], + const Bitboard mult[], int deltas[][2]); } @@ -357,8 +354,8 @@ void init_bitboards() { int rookDeltas[4][2] = { {0,1}, {0 ,-1}, {1, 0}, {-1, 0} }; int bishopDeltas[4][2] = { {1,1}, {-1, 1}, {1,-1}, {-1,-1} }; - init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas); - init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas); + init_sliding_attacks(RAttacks, RMagics, RShift, RMult, rookDeltas); + init_sliding_attacks(BAttacks, BMagics, BShift, BMult, bishopDeltas); for (Square s = SQ_A1; s <= SQ_H8; s++) { @@ -428,20 +425,22 @@ namespace { return attacks; } - void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[], - const int shift[], const Bitboard mult[], int deltas[][2]) { + void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[], + const Bitboard mult[], int deltas[][2]) { Bitboard b, v; int i, j, index; for (i = index = 0; i < 64; i++) { - attackIndex[i] = index; - mask[i] = sliding_attacks(i, 0, deltas, 1, 6, 1, 6); - j = 1 << ((CpuIs64Bit ? 64 : 32) - shift[i]); + m[i].index = index; + m[i].mult = mult[i]; + m[i].shift = shift[i]; + m[i].mask = sliding_attacks(i, 0, deltas, 1, 6, 1, 6); + j = 1 << ((CpuIs64Bit ? 64 : 32) - m[i].shift); for (int k = 0; k < j; k++) { - b = index_to_bitboard(k, mask[i]); + b = index_to_bitboard(k, m[i].mask); v = CpuIs64Bit ? b * mult[i] : unsigned(b * mult[i] ^ (b >> 32) * (mult[i] >> 32)); attacks[index + (v >> shift[i])] = sliding_attacks(i, b, deltas, 0, 7, 0, 7); } diff --git a/src/bitboard.h b/src/bitboard.h index 97048394..bdeddbd2 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -60,24 +60,25 @@ extern Bitboard SquaresInFrontMask[2][64]; extern Bitboard PassedPawnMask[2][64]; extern Bitboard AttackSpanMask[2][64]; -extern const uint64_t RMult[64]; -extern const int RShift[64]; -extern Bitboard RMask[64]; -extern int RAttackIndex[64]; -extern Bitboard RAttacks[0x19000]; - -extern const uint64_t BMult[64]; -extern const int BShift[64]; -extern Bitboard BMask[64]; -extern int BAttackIndex[64]; -extern Bitboard BAttacks[0x1480]; - extern Bitboard BishopPseudoAttacks[64]; extern Bitboard RookPseudoAttacks[64]; extern Bitboard QueenPseudoAttacks[64]; extern uint8_t BitCount8Bit[256]; +struct Magics { + Bitboard mask; + uint64_t mult; + uint32_t index; + uint32_t shift; +}; + +extern Magics RMagics[64]; +extern Magics BMagics[64]; + +extern Bitboard RAttacks[0x19000]; +extern Bitboard BAttacks[0x1480]; + /// Functions for testing whether a given bit is set in a bitboard, and for /// setting and clearing bits. @@ -173,28 +174,30 @@ inline Bitboard in_front_bb(Color c, Square s) { #if defined(IS_64BIT) -inline Bitboard rook_attacks_bb(Square s, Bitboard blockers) { - Bitboard b = blockers & RMask[s]; - return RAttacks[RAttackIndex[s] + ((b * RMult[s]) >> RShift[s])]; +inline Bitboard rook_attacks_bb(Square s, Bitboard occ) { + const Magics& m = RMagics[s]; + return RAttacks[m.index + (((occ & m.mask) * m.mult) >> m.shift)]; } -inline Bitboard bishop_attacks_bb(Square s, Bitboard blockers) { - Bitboard b = blockers & BMask[s]; - return BAttacks[BAttackIndex[s] + ((b * BMult[s]) >> BShift[s])]; +inline Bitboard bishop_attacks_bb(Square s, Bitboard occ) { + const Magics& m = BMagics[s]; + return BAttacks[m.index + (((occ & m.mask) * m.mult) >> m.shift)]; } #else // if !defined(IS_64BIT) -inline Bitboard rook_attacks_bb(Square s, Bitboard blockers) { - Bitboard b = blockers & RMask[s]; - return RAttacks[RAttackIndex[s] + - (unsigned(int(b) * int(RMult[s]) ^ int(b >> 32) * int(RMult[s] >> 32)) >> RShift[s])]; +inline Bitboard rook_attacks_bb(Square s, Bitboard occ) { + const Magics& m = RMagics[s]; + Bitboard b = occ & m.mask; + return RAttacks[m.index + + ((unsigned(b) * unsigned(m.mult) ^ unsigned(b >> 32) * unsigned(m.mult >> 32)) >> m.shift)]; } -inline Bitboard bishop_attacks_bb(Square s, Bitboard blockers) { - Bitboard b = blockers & BMask[s]; - return BAttacks[BAttackIndex[s] + - (unsigned(int(b) * int(BMult[s]) ^ int(b >> 32) * int(BMult[s] >> 32)) >> BShift[s])]; +inline Bitboard bishop_attacks_bb(Square s, Bitboard occ) { + const Magics& m = BMagics[s]; + Bitboard b = occ & m.mask; + return BAttacks[m.index + + ((unsigned(b) * unsigned(m.mult) ^ unsigned(b >> 32) * unsigned(m.mult >> 32)) >> m.shift)]; } #endif -- 2.39.2