lockless hashing

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

lockless hashing

Post by Daniel Shawul » Mon Feb 07, 2011 8:31 pm

In parallel search transposition table could be corrupted by simultaneous read/write in a tt element. I have been using simple testing of legality of move to avoid crashing problems. Now that I am doing other games too, this has become difficult mostly because MOVE is not a simple int. It could be 14 ints in checkers f.i and any of the bytes could get corrupted.

Can lock-less hashing be used for hash_entry size != 128-bit ? The information I store is different for each game. Can I do the test only on part of the data (f.i first 128 bits) and be guaranteed a safe data ? Most of the time I need only the best move to be safe. I can read the whole paper and try to get it but I am too lazy right now.

User avatar
hgm
Posts: 23792
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: lockless hashing

Post by hgm » Mon Feb 07, 2011 8:49 pm

It will work for any size. Just XOR the hash signature with (parts from) all other words. So with a 256-bit entry (four 64-bit memory words) and a 32-bits ignature, you can do

signature ^= (word1 ^ word2 ^ word3) & 0xFFFFFFFF;

(assuming the signature is in word0), both before storing and before probing. Even safer would be toXOR with all other seven 32-bit units, to catch mixups that happen to have the same low 32-bits but different high bits.

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: lockless hashing

Post by Daniel Shawul » Mon Feb 07, 2011 9:00 pm

Oh great! I was getting tired of writing game specific code. This is a clean and hassle free way if I managed to implement it.
Thanks.

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: lockless hashing

Post by bob » Mon Feb 07, 2011 10:01 pm

Daniel Shawul wrote:In parallel search transposition table could be corrupted by simultaneous read/write in a tt element. I have been using simple testing of legality of move to avoid crashing problems. Now that I am doing other games too, this has become difficult mostly because MOVE is not a simple int. It could be 14 ints in checkers f.i and any of the bytes could get corrupted.

Can lock-less hashing be used for hash_entry size != 128-bit ? The information I store is different for each game. Can I do the test only on part of the data (f.i first 128 bits) and be guaranteed a safe data ? Most of the time I need only the best move to be safe. I can read the whole paper and try to get it but I am too lazy right now.
Certainly. I use it on my pawn hash as well, where an entry is 24 bytes if I recall. You just xor them all together and store that as the signature...

Daniel Shawul
Posts: 3762
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: lockless hashing

Post by Daniel Shawul » Tue Feb 08, 2011 2:56 am

I was misguided by the 128 bit description given there but now I remember it was used also in pawn tt. The way HG described it sounds like a CRC check for data integrity in a way every data stored contributes to the key ?
How about hash collisions i.e the real ones where two different positions map to the same hash_key ? We still need to check for legality of move. I know it shouldn't happen but I am not sure since my pseudo-random numbers are generated with a different seed each time using a rather weak rand(). Just a thought.

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: lockless hashing

Post by bob » Tue Feb 08, 2011 6:18 pm

Hash collisions happen. Here, however, they are not an issue in that if two different positions have the same signature, and the same score and such, they will collide. If they have the same sig, but different scoring info, they won't because the XOR changes the stored key. The final choice is two different positions, with different everything, but they end up matching because of all the XORing...

In short, it is not worth worrying about. It is much more likely to have out-of-order writes produce corrupted entries when doing an SMP search, and those happen often enough to become problematic at times... Lockless hashing at least solves that (as much as it can be solved, anyway).

Post Reply