Lockless main hash table (Hyatt/Crafty scheme)

Replaces the sharded-spinlock protection around every main-hash probe
and store with the classic lockless-hashing technique: HASH_ENTRY's
existing 8-byte data word (mv/uDepth/bvFlags/iValue, now addressable
as u64Data via an anonymous union) and its 8-byte u64Sig are written
as two independent plain 64-bit stores -- u64Data first, then
u64Sig = realKey ^ u64Data -- instead of under a lock. Every probe
reads both words into a local snapshot and verifies
(storedSig ^ storedData) == realKey before trusting anything; a
concurrent writer racing a reader can only ever produce a
self-inconsistent pair that fails this check (an ordinary miss), not
corruption, except in the one documented, harmless case where the two
racing entries' data words happen to be bit-identical.

LockCompareExchange (the old spinlock's cost) was already showing up
at 0.51% self-time in a `bench` profile -- real, measured overhead on
a path hit roughly once per searched node, now removed.

HashLookup's contract changes from "return a pointer into the live
table, or NULL" to "return TRUE/FALSE, with *pOut holding a validated
local copy on TRUE" -- callers must never read back through a pointer
into the live table after this function returns, since there's no
longer a lock serializing that against a concurrent writer. The one
real caller (search.c) and the DEBUG-only VERIFY_HASH_HIT diagnostic
are updated accordingly.

testhash.c: AnalyzeFullHashTable's duplicate-entry check used to
compare two entries' raw u64Sig directly, which no longer means "same
position" now that u64Sig depends on each entry's own data word --
fixed to un-corrupt both sides first. Adds TestLocklessHashAlgebra, a
pure algebra test (no concurrency) verifying the XOR round-trip and
torn-write self-detection property over 200k random trials, wired
into the TEST=1 startup self-test suite.

Verified: TestLocklessHashAlgebra passes; single-threaded runs of the
locked and lockless binaries produce identical node counts and solve
scores across all three curated suites (ecm_ringers/confident_quick/
hard_quick); several minutes of real contention (tiny 4MB hash table,
12 threads at ~1200% CPU on a Ryzen 9 3900X, plus a 4-core run
locally) produced zero crashes/assertions/corruption on either
machine.

Co-Authored-By: Claude Sonnet 5 <[email protected]>

1 files changed, 9 insertions, 7 deletions

diff --git a/src/search.c b/src/search.c
index c434f48..d8ece8d 100644
--- a/src/search.c
+++ b/src/search.c
@@ -391,8 +391,8 @@ _NullCalibBucketIndex(ULONG uNullDepth,     // probe's own post-reduction depth
 #ifdef DEBUG
 #define VERIFY_HASH_HIT                                \
     ASSERT(IS_VALID_SCORE(iScore));                    \
-    ASSERT(((ULONG)pHash->uDepth << 4) >= uDepth);     \
-    switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)   \
+    ASSERT(((ULONG)sHash.uDepth << 4) >= uDepth);      \
+    switch (sHash.bvFlags & HASH_FLAG_VALID_BOUNDS)    \
     {                                                  \
         case HASH_FLAG_LOWER:                          \
             ASSERT(iScore >= iBeta);                   \
@@ -528,7 +528,8 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
     ULONG uThisMoveJointExtraTier = 0;
     FLAG fThisMoveJointExtraEligible = FALSE;
 #endif
-    HASH_ENTRY *pHash;
+    HASH_ENTRY sHash;
+    FLAG fHashHit;
     FLAG fThreat;
     FLAG fSkipNull;
     FLAG fIsDraw;
@@ -643,7 +644,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
     // below) based on uNextDepth to inform us that a nullmove search
     // is unlikely to succeed here.
     mvHash.uMove = 0;
-    pHash = HashLookup(ctx,
+    fHashHit = HashLookup(ctx,
                        uDepth,
                        uNextDepth,
                        iAlpha,
@@ -651,11 +652,12 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx,
                        &fThreat,
                        &fSkipNull,
                        &mvHash,
-                       &iScore);
-    if (NULL != pHash)
+                       &iScore,
+                       &sHash);
+    if (TRUE == fHashHit)
     {
         VERIFY_HASH_HIT;
-        u = pHash->bvFlags & HASH_FLAG_VALID_BOUNDS;
+        u = sHash.bvFlags & HASH_FLAG_VALID_BOUNDS;
         if (0 != mvHash.uMove)
         {
             // This is an idea posted by Dieter Brusser on CCC: If we