Lazy SMP and shared hash table

[amanjpro]

I am trying to implement LazySMP into Zahak, and it is going very well... I have some elo gain and things seem to be working, that is how I guarantee atomicity when updating the hashtable:

- find hash entry at index i
- use compare-and-swap to flip a bit in the entry from 0 to 1
- read or update the entry
- atomically flip the bit from 1 to 0, to unlock it for other readers

Since, I essentially had to grow the size of the entry by int32 (that is the smallest size that I can use it in compare-and-swap in golang), I decided to only store 32-bit of the hash in the entry. This proves to be good except Zahak plays an illegal move every 1600 games or so (I do not validate the legality of hash moves).

That encouraged me to search other engines, and see how they implement atomicity in their engines, and they DO NOT! I saw some top engiens like Weiss for example even plays hash moves without checking their legality first! Stockfish even admits that neither probing, nor storing are atomic! Not sure how this works, can somone enlighten me

[smatovic]

Not sure if this is what you mean, TT lockless:

https://www.chessprogramming.org/Shared ... #Lock-less

I use the xor trick for lockless TT, my tt move is picked from a prev generated move list, dunno how other engines check tt move, maybe to just check if the move is valid (piece/sq from/to) but not legal is already enough.

--
Srdja

[Terje]

Weiss doesn't check move legality before playing it? When did it stop?

[amanjpro]

Weiss doesn't check move legality before playing it? When did it stop?

Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?

[Terje]

Weiss doesn't check move legality before playing it? When did it stop?

Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?

I do.

[amanjpro]

Weiss doesn't check move legality before playing it? When did it stop?

Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?

I do.

Can you point me to where you do the check, I completely fail to find it:

https://github.com/TerjeKir/weiss/searc ... egal&type=

What is more amazing, you read the entry here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179

Then use it here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181

The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?

I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand

[amanjpro]

Not sure if this is what you mean, TT lockless:

https://www.chessprogramming.org/Shared ... #Lock-less

I use the xor trick for lockless TT, my tt move is picked from a prev generated move list, dunno how other engines check tt move, maybe to just check if the move is valid (piece/sq from/to) but not legal is already enough.

--
Srdja

I haven't tried this, but found the crafty source and Bob's article about it. Will read it.

My data is more than 64 bytes, but I can probably fix that

[Jakob Progsch]

What I did recently is change my buckets to three elements stored in 4 uint64. The first uint64 is just a directory containing 21 bits of metadata per entry like age, depth, type and however many bits of signature fit after that. The remaining three entries then contain the rest of the signature as well as score and move. The idea being that you only need to inspect that metadata to find an entry to replace instead of the entries themselves.

So to fully update an entry technically i'd have to atomically write both the metadata uint64 as well as the entry uint64. Which I don't do. The justification being that if there is a race condition in the worst case you see mismatched metadata and entry. However since both contain part of the signature the chance of mistaking a partial entry as a real one is very small. So if you multiply out the chances of there being a data race in the first place, that race not resulting in a signature mismatch AND that entry being critical for the search result the risk is low enough. Probably lower than the chance of a key collision which is a risk we already accept in the TT.

[AndrewGrant]

Weiss doesn't check move legality before playing it? When did it stop?

Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?

I do.

Can you point me to where you do the check, I completely fail to find it:

https://github.com/TerjeKir/weiss/searc ... egal&type=

What is more amazing, you read the entry here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179

Then use it here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181

The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?

I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand

https://github.com/TerjeKir/weiss/blob/ ... ker.c#L151

[amanjpro]

Weiss doesn't check move legality before playing it? When did it stop?

Not move legality, but pseudo legality.... For killers you make sure the move is pseudo legal, for hash moves you don't ... Or probably I read it wrong?

I do.

Can you point me to where you do the check, I completely fail to find it:

https://github.com/TerjeKir/weiss/searc ... egal&type=

What is more amazing, you read the entry here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L179

Then use it here:

https://github.com/TerjeKir/weiss/blob/ ... rch.c#L181

The issue is that, your probe function returns the reference of the entry, not a copy of it. That means in the meantime another thread could have easily written a different value there, unless I'm missing something obvious. Can you elaborate a bit?

I'm sure whatever you do works, as your engine is way stronger than mine, it is just that I do not understand

https://github.com/TerjeKir/weiss/blob/ ... ker.c#L151

Oh! I totally missed that. Thank you

I'll give Bob's approach a try, if it wasn't good then I'll give this a try, and see

Bob's approach is I believe the safest non-atomic/non-locking solution, as you will almost never have corrupt data. The way Weiss is doing, is slightly riskier, as you can have score+move mismatch, and possibly play bad moves, but that is not as sever as playing illegal move