Two-tier hash database that deduplicates visited states across the whole search. More...

#include <hashDb.hpp>

Classes
struct	hashStore_t
	One generation of a rolling store: a hash set of previously found states plus its identity, age and snapshotted statistics. More...

struct	NUMAStore_t
	A single (L1 or L2) hash store: a rolling window of hashStore_t generations together with its rolling state and per-thread statistics counters. More...

struct	paddedCounter_t
	A query/collision counter padded to a full cache line to avoid false sharing. More...

Public Member Functions
	HashDb (const nlohmann::json &config)
	Constructs the hash database from its configuration block.

size_t	getMaxBudgetBytes () const
	Configured PEAK hash-DB footprint in bytes = Max Store Size x Max Store Count (the rolling generations can be live simultaneously).

	~HashDb ()
	Destroys the database, deleting all per-domain L1 stores and the global L2 store.

void	initialize ()
	Allocates the hash stores and splits the configured budget across the L1 and L2 tiers.

void	printInfo () const
	Logs the database's current state, including per-generation breakdowns of the rolling stores and aggregated check / collision statistics.

bool	checkHashExists (const jaffarCommon::hash::hash_t hash)
	Checks whether the given hash is already present in the database, inserting it if new.

void	insertHash (const jaffarCommon::hash::hash_t hash)
	Inserts a hash into the current (newest) store(s) without checking for collisions.

void	advanceStep ()
	Signals that a new search step has started, rolling and ageing every store.

Private Member Functions
NUMAStore_t *	makeStore ()
	Creates a fresh store with a single (empty) hash set generation and per-thread counters.

bool	probeStore (NUMAStore_t *const store, const jaffarCommon::hash::hash_t hash)
	Reverse-scans a store's hash sets (newest first), inserting into the current set and checking-only the archived sets.

void	rollStore (NUMAStore_t *const g, const size_t maxBytes)
	Rolls a single store and advances its age.

size_t	getStoreSizeBytes (const hashStore_t &store) const
	Computes the actual resident memory of a hash store generation from the underlying set's measured allocated capacity (number of slots) plus the fixed overhead.

Private Attributes
size_t	_maxStoreCount
	Maximum number of store generations to keep at any time.

double	_maxStoreSizeMb
	Maximum (global L2) store size, in megabytes.

size_t	_maxStoreSizeBytes
	Maximum global L2 store size, in bytes (derived from _maxStoreSizeMb).

size_t	_l1MaxStoreSizeBytes = 0
	Per-domain L1 store budget, in bytes (derived: global budget / number of NUMA domains).

std::vector< NUMAStore_t * >	_l1
	Per-domain NUMA-local L1 caches. Empty on a single-domain run.

NUMAStore_t *	_l2 = nullptr
	The single global authoritative store (holds the complete dedup set).

Static Private Attributes
static constexpr size_t	_bytesPerSlot = sizeof(jaffarCommon::hash::hash_t) + sizeof(uint8_t)
	Per-slot memory cost of the underlying phmap flat hash set.

static constexpr size_t	_hashStoreFixedOverhead = sizeof(jaffarCommon::concurrent::HashSet_t<jaffarCommon::hash::hash_t>)
	Fixed overhead of a hash store, independent of the number of entries.

Detailed Description

Two-tier hash database that deduplicates visited states across the whole search.

On a multi-NUMA host it uses a two-tier layout: a NUMA-local L1 store per domain in front of a single global authoritative L2 store. A worker first probes its own domain's L1 (local, fast); only on an L1 miss does it consult L2 (which may be remote / contended). Every globally-new hash is registered in L2 exactly once, so dedup stays COMPLETE – identical to a single global table – while the frequent within-domain repeats are served locally. On a single-NUMA host (one domain) the L1 tier is skipped and a single local store is used, since everything is local anyway.

This is automatic; there is no script-level configuration for it.

Definition at line 32 of file hashDb.hpp.

Constructor & Destructor Documentation

◆ HashDb()

jaffarPlus::HashDb::HashDb ( const nlohmann::json & config )

inline

Constructs the hash database from its configuration block.

Parameters

config JSON configuration providing "Max Store Count" and "Max Store Size (Mb)". The environment variable JAFFAR_ENGINE_OVERRIDE_MAX_HASHDB_SIZE_MB, when set, overrides the configured maximum store size (in Mb) for testing.

Definition at line 41 of file hashDb.hpp.

◆ ~HashDb()

jaffarPlus::HashDb::~HashDb ( )

inline

Destroys the database, deleting all per-domain L1 stores and the global L2 store.

Definition at line 55 of file hashDb.hpp.

Member Function Documentation

◆ advanceStep()

void jaffarPlus::HashDb::advanceStep ( )

inline

Signals that a new search step has started, rolling and ageing every store.

Each per-domain L1 store is rolled at the per-domain L1 budget and the global L2 store is rolled at the L2 budget; rolling creates a fresh current store (and discards the oldest) only when a store's measured memory exceeds its budget. Every store's age is advanced.

Definition at line 249 of file hashDb.hpp.

◆ checkHashExists()

bool jaffarPlus::HashDb::checkHashExists ( const jaffarCommon::hash::hash_t hash )

inline

Checks whether the given hash is already present in the database, inserting it if new.

On a single-domain run it probes the lone global store. On a two-tier run it first probes (and caches into) the calling thread's domain-local L1 store; on an L1 hit it returns true without touching L2. On an L1 miss it probes (and inserts into) the global L2, which makes the hash globally visible. Per-thread query and collision counters are updated on each probe.

Parameters

hash	The state hash to look up.

Returns: true if the hash was already present (a duplicate state), false if it was newly inserted.

Definition at line 195 of file hashDb.hpp.

◆ getMaxBudgetBytes()

size_t jaffarPlus::HashDb::getMaxBudgetBytes ( ) const

inline

Configured PEAK hash-DB footprint in bytes = Max Store Size x Max Store Count (the rolling generations can be live simultaneously).

Used by the engine's combined RAM guard.

Definition at line 52 of file hashDb.hpp.

◆ getStoreSizeBytes()

size_t jaffarPlus::HashDb::getStoreSizeBytes ( const hashStore_t & store ) const

inlineprivate

Computes the actual resident memory of a hash store generation from the underlying set's measured allocated capacity (number of slots) plus the fixed overhead.

Measuring from capacity tracks phmap's real footprint – which varies with load factor and per-submap power-of-two rounding – so the configured store budget is respected instead of being over- or under-shot.

Parameters

store The hash store generation to measure.

Returns: The estimated resident memory of the store, in bytes.

Definition at line 446 of file hashDb.hpp.

◆ initialize()

void jaffarPlus::HashDb::initialize ( )

inline

Allocates the hash stores and splits the configured budget across the L1 and L2 tiers.

The configured "Max Store Size" is the absolute per-generation budget for the whole hash DB. On a multi-domain run the global L2 receives 3/4 of the budget and the per-domain L1 caches share the remaining 1/4 (split evenly across domains); on a single-domain run the lone global store receives the entire budget and no L1 tier is created.

Definition at line 69 of file hashDb.hpp.

◆ insertHash()

void jaffarPlus::HashDb::insertHash ( const jaffarCommon::hash::hash_t hash )

inline

Inserts a hash into the current (newest) store(s) without checking for collisions.

On a two-tier run the hash is inserted into the calling thread's domain-local L1 current store; in all cases it is inserted into the global L2 current store.

Parameters

hash	The state hash to insert.

Definition at line 236 of file hashDb.hpp.

◆ makeStore()

NUMAStore_t * jaffarPlus::HashDb::makeStore ( )

inlineprivate

Creates a fresh store with a single (empty) hash set generation and per-thread counters.

Returns: A pointer to the newly allocated store (owned by the caller).

Definition at line 361 of file hashDb.hpp.

◆ printInfo()

void jaffarPlus::HashDb::printInfo ( ) const

inline

Logs the database's current state, including per-generation breakdowns of the rolling stores and aggregated check / collision statistics.

On a single-domain run it reports L2 as a single store with its rolling-window breakdown. On a two-tier run it aggregates the L1 caches across domains, reports the global L2, and prints the L2 rolling-window breakdown. Each store line exposes its Id and Age so window rolling is observable.

Definition at line 109 of file hashDb.hpp.

◆ probeStore()

bool jaffarPlus::HashDb::probeStore	(	NUMAStore_t *const	store,
		const jaffarCommon::hash::hash_t	hash
	)

inlineprivate

Reverse-scans a store's hash sets (newest first), inserting into the current set and checking-only the archived sets.

Inserting-while-checking on the newest set means a single probe both registers the hash and detects a same-step duplicate.

Parameters

store	The store to probe and insert into.
hash	The hash to look up / insert.

Returns: true if the hash was already present in any of the store's generations (a collision).

Definition at line 380 of file hashDb.hpp.

◆ rollStore()

void jaffarPlus::HashDb::rollStore	(	NUMAStore_t *const	g,
		const size_t	maxBytes
	)

inlineprivate

Rolls a single store and advances its age.

If the current (newest) set's measured memory reaches maxBytes, the per-thread counters are snapshotted into the current generation and reset, the oldest generation is discarded if the window is already at _maxStoreCount, and a fresh current generation is pushed. The store's age is then advanced in all cases.

Parameters

g	The store to roll.
maxBytes	The per-generation memory budget that triggers a roll.

Definition at line 408 of file hashDb.hpp.

Member Data Documentation

◆ _bytesPerSlot

constexpr size_t jaffarPlus::HashDb::_bytesPerSlot = sizeof(jaffarCommon::hash::hash_t) + sizeof(uint8_t)

staticconstexprprivate

Per-slot memory cost of the underlying phmap flat hash set.

Each element is stored inline (one slot = sizeof(value)) plus one control byte per slot.

Definition at line 453 of file hashDb.hpp.

◆ _hashStoreFixedOverhead

constexpr size_t jaffarPlus::HashDb::_hashStoreFixedOverhead = sizeof(jaffarCommon::concurrent::HashSet_t<jaffarCommon::hash::hash_t>)

staticconstexprprivate

Fixed overhead of a hash store, independent of the number of entries.

The parallel set holds 256 (2^N) submaps, each with its own table bookkeeping and mutex, allocated even when empty.

Definition at line 461 of file hashDb.hpp.

◆ _l1

std::vector<NUMAStore_t*> jaffarPlus::HashDb::_l1

private

Per-domain NUMA-local L1 caches. Empty on a single-domain run.

Definition at line 471 of file hashDb.hpp.

◆ _l1MaxStoreSizeBytes

size_t jaffarPlus::HashDb::_l1MaxStoreSizeBytes = 0

private

Per-domain L1 store budget, in bytes (derived: global budget / number of NUMA domains).

Definition at line 469 of file hashDb.hpp.

◆ _l2

NUMAStore_t* jaffarPlus::HashDb::_l2 = nullptr

private

The single global authoritative store (holds the complete dedup set).

Definition at line 473 of file hashDb.hpp.

◆ _maxStoreCount

size_t jaffarPlus::HashDb::_maxStoreCount

private

Maximum number of store generations to keep at any time.

Definition at line 463 of file hashDb.hpp.

◆ _maxStoreSizeBytes

size_t jaffarPlus::HashDb::_maxStoreSizeBytes

private

Maximum global L2 store size, in bytes (derived from _maxStoreSizeMb).

Definition at line 467 of file hashDb.hpp.

◆ _maxStoreSizeMb

double jaffarPlus::HashDb::_maxStoreSizeMb

private

Maximum (global L2) store size, in megabytes.

Definition at line 465 of file hashDb.hpp.

The documentation for this class was generated from the following file:

hashDb.hpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ HashDb()

◆ ~HashDb()

Member Function Documentation

◆ advanceStep()

◆ checkHashExists()

◆ getMaxBudgetBytes()

◆ getStoreSizeBytes()

◆ initialize()

◆ insertHash()

◆ makeStore()

◆ printInfo()

◆ probeStore()

◆ rollStore()

Member Data Documentation

◆ _bytesPerSlot

◆ _hashStoreFixedOverhead

◆ _l1

◆ _l1MaxStoreSizeBytes

◆ _l2

◆ _maxStoreCount

◆ _maxStoreSizeBytes

◆ _maxStoreSizeMb