Storing a CRC32 in the TT without needing an additional 32 bits

[gwiesenekker]

Hi,

GWD uses a (hardware) CRC32 checksum to validate the integrity of the (lockless) TT entries. It turns out that you can store the CRC32 on top-of the standard two 64-bit unsigned-integers that GWD uses for a TT entry, so you do not need an additional 32/64 bit integer to store it. 1+1=3: I got the idea but was struggling to get it right, ChatGPT got the idea to reconstruct the CRC32 and the TT entry using the board key you are checking for. The only disadvantage is that you cannot distinguish CRC32 errors due to hardware errors (as happened during the latest Krzysztof's tournament) from errors due to multiple threads writing simultaneously to the same TT entry. I have asked ChatGPT to document the trick. score_t is either a float or an int

GW

[Joost Buijs]

Since you are using a 32-bit CRC, I wonder if this method has a lower probability of missing a data race than simply XORing the key with the data. Have you compared both methods? If so, what difference did this yield?

Another question concerns storing the most recent entry in the first slot of a bucket. Doesn't this cost an excessive amount of time because you have to shift the other entries in memory? Since a bucket is completely located in the cache, this might not be too bad, but have you looked at the net benefit?

I did ask chatGPT about this:

Code: Select all

CRC32 vs. XOR for Data Races

Yes, a 32-bit CRC has a significantly lower probability of missing data races than a simple XOR

Limitation: An XOR operation cancels itself out with double bit errors at the same position. If two bits flip simultaneously in the same column, XOR will not detect it.

CRC32 Strength: CRC uses polynomial division. This is mathematically designed to catch consecutive bit errors (burst errors) and scattered bit flips with extreme efficiency.

The Net Difference: In simulations and tests with random bit flips, XOR often yields a fault detection rate of only 50% to 90% (depending on the pattern).

For short data inputs, CRC32 approaches 99.9999999%. XOR simply misses too many correlated errors that typically occur during data races.

Shifting Cost in Buckets (Cache Efficiency)

No, this does not take an excessive amount of time because the entire bucket is already loaded into the L1/L2 CPU cache.

Cache Hit Advantage: Fetching data from the main memory (DRAM) costs hundreds of clock cycles. Modifying data that is already inside the CPU cache takes only 1 to 3 clock cycles.

SIMD and Registers: Modern CPUs shift 4 to 8 entries at once using a single vector instruction (SIMD), or handle it directly within processor registers.

The Net Benefit: Temporal locality (the concept that recently accessed data is likely to be accessed again soon) heavily outweighs the minimal write cost. For read-heavy workloads, this optimization yields a net performance gain of 15% to 30% compared to scanning an unsorted bucket.

I ran many tests to determine if data races do occur with the simple XOR method, and never found anything wrong with it.

Although I don't believe chatGPT at will because it is merely combining and repeating things it found on internet, it could be worthwhile to look at this.

Using SIMD for the transposition table seems like a good idea, something I never thought of before.

[Joost Buijs]

Hi Gijsbert,

I've implemented the proposed CRC32 verification, the speed loss seems to be negligible (actually none). I will run some SMP tests to check how it behaves in comparison with the Hyatt method.

Joost

Edit:

I've implemented it exactly as proposed in the PDF document, single threaded it works fine, no problem. With 24 threads it produces lots of data races, somehow the CRC check fails (or a 32 bit CRC is simply not good enough). It could be that I misinterpreted something, I have to take another look at it.

[FrankMesander]

Really interesting video on concurrency:
Why Multi-Threaded Code Can Sometimes Misbehave (Weak Memory Concurrency)
https://www.youtube.com/watch?v=E3hvLz7 ... WL&index=9

[Joost Buijs]

Another option is to use InterlockedCompareExchange128(), which can transfer 128-bit data atomically to and from memory. The drawback is that it takes a few percent of the total time consumed by the search, and the entries need to be aligned on a 16-byte boundary. I have this as an option in the program, but I don't use it anymore because the Hyatt lockless XOR method works well enough and is somewhat faster too. An occasional data race in the transposition table doesn't seem to hurt the program in any way; a search is very good at coping with these things.

For 128 bit atomic transfers with modern compilers like Clang or GCC who have lock-free 128 bit atomics on X86, the following code will work:

Code: Select all

#include <atomic>
#include <cstdint>

// 1. Define a 128-bit data structure aligned to a 16-byte boundary
struct alignas(16) Data128
{
    uint64_t low;
    uint64_t high;
};

// Compile-time check to guarantee that 128-bit atomics are truly lock-free on your platform
static_assert(std::atomic<Data128>::is_always_lock_free, "128-bit atomic operations are not lock-free on this platform!");

// 2. Function to atomically transfer 128-bit data TO memory (Store)
void atomic_store_128(std::atomic<Data128>& target, const Data128& value)
{
    // std::memory_order_release ensures previous writes are visible to other threads
    target.store(value, std::memory_order_release); 
}

// 3. Function to atomically transfer 128-bit data FROM memory (Load)
Data128 atomic_load_128(const std::atomic<Data128>& source)
{
    // std::memory_order_acquire ensures subsequent reads see the updated data
    return source.load(std::memory_order_acquire);
}

However with 'dumb' MSVC the 128 bit atomic transfers have to be made with InterlockedCompareExchange128().

Code: Select all

#include <iostream>
#include <cstdint>
#include <intrin.h> // Required for _InterlockedCompareExchange128

// 1. Define a 128-bit structure aligned to a 16-byte boundary
struct alignas(16) Data128
{
    int64_t low;
    int64_t high;
};

// 2. Function to atomically transfer 128-bit data FROM memory (Load)
// To perform a read using CMPXCHG16B, we execute a loop comparing the 
// destination against itself until it safely copies out the original data.
Data128 atomic_load_128(const Data128 volatile* source)
{
    Data128 expected = {0, 0};
    
    // We pass 'expected' as both the comparand and the exchange value.
    // If the data matches 'expected', it writes 'expected' back (no change).
    // If it doesn't match, 'expected' is updated with the real, current memory data.
    while (!_InterlockedCompareExchange128(
        reinterpret_cast<volatile int64_t*>(const_cast<Data128 volatile*>(source)),
        expected.high,
        expected.low,
        reinterpret_cast<int64_t*>(&expected))) 
    {
        // The intrinsic returns 0 if the swap failed.
        // But on failure, 'expected' is automatically updated with the fresh 
        // 128-bit data from memory. We loop until the operation succeeds.
    }
    
    return expected;
}

// 3. Function to atomically transfer 128-bit data TO memory (Store)
// To overwrite the destination safely, we loop until we successfully 
// replace whatever was currently there with our new value.
void atomic_store_128(Data128 volatile* target, const Data128& value) 
{
    Data128 expected = {0, 0};
    
    // Step 1: Pre-populate 'expected' with a fast, non-atomic peek
    // (This minimizes the number of times the loop has to spin).
    expected.low = target->low;
    expected.high = target->high;

    // Step 2: Loop until the compare-and-swap succeeds
    while (!_InterlockedCompareExchange128(
        reinterpret_cast<volatile int64_t*>(target),
        value.high,
        value.low,
        reinterpret_cast<int64_t*>(&expected))) 
    {
        // If another thread modified 'target' in the meantime, the swap fails,
        // and 'expected' is updated with that new value. We spin and try again.
    }
}