From: Ron Britvich Date: Sat, 28 Jun 2014 18:05:58 +0000 (-0400) Subject: Pack 3 TT entries in 32 bytes cluster X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=ccd823a4ffd2ed3e60cb03ab49a841742bae1994 Pack 3 TT entries in 32 bytes cluster Idea from Ron Britvich Code reworked by Marco Costalba and Joona Kiiski Bench: 8095369 Resolves #3 Resolves #10 --- diff --git a/src/tt.cpp b/src/tt.cpp index 3d2fe48a..248cbad9 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -28,20 +28,21 @@ TranspositionTable TT; // Our global transposition table /// TranspositionTable::resize() sets the size of the transposition table, /// measured in megabytes. Transposition table consists of a power of 2 number -/// of clusters and each cluster consists of ClusterSize number of TTEntry. +/// of clusters and each cluster consists of TTClusterSize number of TTEntry. void TranspositionTable::resize(uint64_t mbSize) { - assert(msb((mbSize << 20) / sizeof(TTEntry)) < 32); + assert(msb((mbSize * 1024 * 1024) / sizeof(TTCluster)) < 32); - uint32_t size = ClusterSize << msb((mbSize << 20) / sizeof(TTEntry[ClusterSize])); + uint32_t newClusterCount = 1 << msb((mbSize * 1024 * 1024) / sizeof(TTCluster)); - if (hashMask == size - ClusterSize) + if (newClusterCount == clusterCount) return; - hashMask = size - ClusterSize; + clusterCount = newClusterCount; + free(mem); - mem = calloc(size * sizeof(TTEntry) + CACHE_LINE_SIZE - 1, 1); + mem = calloc(clusterCount * sizeof(TTCluster) + CACHE_LINE_SIZE - 1, 1); if (!mem) { @@ -50,7 +51,7 @@ void TranspositionTable::resize(uint64_t mbSize) { exit(EXIT_FAILURE); } - table = (TTEntry*)((uintptr_t(mem) + CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE - 1)); + table = (TTCluster*)((uintptr_t(mem) + CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE - 1)); } @@ -60,7 +61,7 @@ void TranspositionTable::resize(uint64_t mbSize) { void TranspositionTable::clear() { - std::memset(table, 0, (hashMask + ClusterSize) * sizeof(TTEntry)); + std::memset(table, 0, clusterCount * sizeof(TTCluster)); } @@ -71,12 +72,12 @@ void TranspositionTable::clear() { const TTEntry* TranspositionTable::probe(const Key key) const { TTEntry* tte = first_entry(key); - uint32_t key32 = key >> 32; + uint16_t key16 = key >> 48; - for (unsigned i = 0; i < ClusterSize; ++i, ++tte) - if (tte->key32 == key32) + for (unsigned i = 0; i < TTClusterSize; ++i, ++tte) + if (tte->key16 == key16) { - tte->generation8 = generation; // Refresh + tte->genBound8 = generation | tte->bound(); // Refresh return tte; } @@ -95,13 +96,13 @@ const TTEntry* TranspositionTable::probe(const Key key) const { void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, Value statV) { TTEntry *tte, *replace; - uint32_t key32 = key >> 32; // Use the high 32 bits as key inside the cluster + uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster tte = replace = first_entry(key); - for (unsigned i = 0; i < ClusterSize; ++i, ++tte) + for (unsigned i = 0; i < TTClusterSize; ++i, ++tte) { - if (!tte->key32 || tte->key32 == key32) // Empty or overwrite old + if (!tte->key16 || tte->key16 == key16) // Empty or overwrite old { if (!m) m = tte->move(); // Preserve any existing ttMove @@ -111,11 +112,11 @@ void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, } // Implement replace strategy - if ( ( tte->generation8 == generation || tte->bound() == BOUND_EXACT) - - (replace->generation8 == generation) - - (tte->depth16 < replace->depth16) < 0) + if ( (( tte->genBound8 & 0xFC) == generation || tte->bound() == BOUND_EXACT) + - ((replace->genBound8 & 0xFC) == generation) + - (tte->depth8 < replace->depth8) < 0) replace = tte; } - replace->save(key32, v, b, d, m, generation, statV); + replace->save(key16, v, b, d, m, generation, statV); } diff --git a/src/tt.h b/src/tt.h index eeb18e32..e9c25ad2 100644 --- a/src/tt.h +++ b/src/tt.h @@ -23,58 +23,69 @@ #include "misc.h" #include "types.h" -/// The TTEntry is the 14 bytes transposition table entry, defined as below: +/// The TTEntry is the 10 bytes transposition table entry, defined as below: /// -/// key 32 bit +/// key 16 bit /// move 16 bit -/// bound type 8 bit -/// generation 8 bit /// value 16 bit -/// depth 16 bit /// eval value 16 bit +/// generation 6 bit +/// bound type 2 bit +/// depth 8 bit struct TTEntry { Move move() const { return (Move )move16; } - Bound bound() const { return (Bound)bound8; } Value value() const { return (Value)value16; } - Depth depth() const { return (Depth)depth16; } Value eval_value() const { return (Value)evalValue; } + Depth depth() const { return (Depth)(depth8) + DEPTH_NONE; } + Bound bound() const { return (Bound)(genBound8 & 0x3); } private: friend class TranspositionTable; - void save(uint32_t k, Value v, Bound b, Depth d, Move m, uint8_t g, Value ev) { + void save(uint16_t k, Value v, Bound b, Depth d, Move m, uint8_t g, Value ev) { - key32 = (uint32_t)k; - move16 = (uint16_t)m; - bound8 = (uint8_t)b; - generation8 = (uint8_t)g; - value16 = (int16_t)v; - depth16 = (int16_t)d; - evalValue = (int16_t)ev; + key16 = (uint16_t)k; + move16 = (uint16_t)m; + value16 = (int16_t)v; + evalValue = (int16_t)ev; + depth8 = (uint8_t)(d - DEPTH_NONE); + genBound8 = g | (uint8_t)b; } - uint32_t key32; + uint16_t key16; uint16_t move16; - uint8_t bound8, generation8; - int16_t value16, depth16, evalValue; + int16_t value16; + int16_t evalValue; + uint8_t genBound8; + uint8_t depth8; }; +/// TTCluster is a 32 bytes cluster of TT entries consisting of: +/// +/// 3 x TTEntry (3 x 10 bytes) +/// padding (2 bytes) + +const unsigned TTClusterSize = 3; + +struct TTCluster { + + TTEntry entry[TTClusterSize]; + char padding[2]; +}; /// A TranspositionTable consists of a power of 2 number of clusters and each -/// cluster consists of ClusterSize number of TTEntry. Each non-empty entry +/// cluster consists of TTClusterSize number of TTEntry. Each non-empty entry /// contains information of exactly one position. The size of a cluster should /// not be bigger than a cache line size. In case it is less, it should be padded /// to guarantee always aligned accesses. class TranspositionTable { - static const unsigned ClusterSize = 4; - public: ~TranspositionTable() { free(mem); } - void new_search() { ++generation; } + void new_search() { generation += 4; } // Lower 2 bits are used by Bound const TTEntry* probe(const Key key) const; TTEntry* first_entry(const Key key) const; @@ -83,10 +94,10 @@ public: void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV); private: - uint32_t hashMask; - TTEntry* table; + uint32_t clusterCount; + TTCluster* table; void* mem; - uint8_t generation; // Size must be not bigger than TTEntry::generation8 + uint8_t generation; // Size must be not bigger than TTEntry::genBound8 }; extern TranspositionTable TT; @@ -94,11 +105,11 @@ extern TranspositionTable TT; /// TranspositionTable::first_entry() returns a pointer to the first entry of /// a cluster given a position. The lowest order bits of the key are used to -/// get the index of the cluster. +/// get the index of the cluster inside the table. inline TTEntry* TranspositionTable::first_entry(const Key key) const { - return table + ((uint32_t)key & hashMask); + return &table[(uint32_t)key & (clusterCount - 1)].entry[0]; } #endif // #ifndef TT_H_INCLUDED diff --git a/src/types.h b/src/types.h index 2aed5486..c3911446 100644 --- a/src/types.h +++ b/src/types.h @@ -218,7 +218,7 @@ enum Depth { DEPTH_QS_NO_CHECKS = -1 * ONE_PLY, DEPTH_QS_RECAPTURES = -5 * ONE_PLY, - DEPTH_NONE = -127 * ONE_PLY + DEPTH_NONE = -6 * ONE_PLY }; enum Square {