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 never use it because in practice the Hyatt lockless XOR-method works good enough, and is somewhat faster too.