Page 1 of 2
transposition and multithreading question
Posted: Sun May 04, 2014 7:24 pm
by elcabesa
in my effort to add multithreading in vajolet I have found some problems implenting transposition.
I'm have up to now used a probe function stockfish stile. I search for the right element and then return the pointer to it, then in the search code I use the pointed data.
having just read some articles about multithreading it now looks to me I could use in the search a value overwritten by another thread and have some problems.
I have then looked at senpai code and it correctly read the data from the transposition and copy them in the search variables so even if another thread later overwrite the transposition table element, the previously retrieved data are not modified.
am I understood it or am I missing something in stockfish code?
thank you all for your precious help
Re: transposition and multithreading question
Posted: Sun May 04, 2014 7:48 pm
by ZirconiumX
elcabesa wrote:in my effort to add multithreading in vajolet I have found some problems implenting transposition.
I'm have up to now used a probe function stockfish stile. I search for the right element and then return the pointer to it, then in the search code I use the pointed data.
having just read some articles about multithreading it now looks to me I could use in the search a value overwritten by another thread and have some problems.
I have then looked at senpai code and it correctly read the data from the transposition and copy them in the search variables so even if another thread later overwrite the transposition table element, the previously retrieved data are not modified.
am I understood it or am I missing something in stockfish code?
thank you all for your precious help
Most engines perform TT move validation. If the move in the TT is not found in the move list then the TT entry is treated as being nonexistent.
Matthew:out
Re: transposition and multithreading question
Posted: Sun May 04, 2014 8:21 pm
by elcabesa
ZirconiumX wrote:
Most engines perform TT move validation. If the move in the TT is not found in the move list then the TT entry is treated as being nonexistent.
Matthew:out
I'm aware of this, but after retrieving the pointer, later in the code , it use the flags, depth, result of the search and static value of the position from the entry
Re: transposition and multithreading question
Posted: Sun May 04, 2014 9:00 pm
by elcabesa
is it simply a speed/precision compromise?
Re: transposition and multithreading question
Posted: Sun May 04, 2014 9:50 pm
by syzygy
elcabesa wrote:I have then looked at senpai code and it correctly read the data from the transposition and copy them in the search variables so even if another thread later overwrite the transposition table element, the previously retrieved data are not modified.
When one thread of senpai is reading out a tt entry another thread may be modifying it, so the local copy can be corrupted.
The short answer to your question is: it is not a problem
at all, as long as you validate the hash move before using it.
The long answer: use the search function of this forum. There have been many threads about this.
Re: transposition and multithreading question
Posted: Sun May 04, 2014 10:40 pm
by elcabesa
I understood that the transposition move is validated before using it and I already do that.
what i don't full understand is the following piece of code:
Code: Select all
tte = TT.probe(posKey);
ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
// At PV nodes we check for exact scores, while at non-PV nodes we check for
// a fail high/low. Biggest advantage at probing at PV nodes is to have a
// smooth experience in analy, sis mode. We don't probe at Root nodes otherwise
// we should also update RootMoveList to avoid bogus output.
if ( !RootNode
&& tte
&& tte->depth() >= depth
&& ttValue != VALUE_NONE // Only in case of TT access race
&& ( PvNode ? tte->bound() == BOUND_EXACT
: ttValue >= beta ? (tte->bound() & BOUND_LOWER)
: (tte->bound() & BOUND_UPPER)))
{
TT.refresh(tte);
ss->currentMove = ttMove; // Can be MOVE_NONE
if ( ttValue >= beta
&& ttMove
&& !pos.capture_or_promotion(ttMove)
&& ttMove != ss->killers[0])
{
ss->killers[1] = ss->killers[0];
ss->killers[0] = ttMove;
}
return ttValue;
}
nothing can assure us that ttValue, tte->depth(), tte->bound() were not changed by another thread.
Re: transposition and multithreading question
Posted: Mon May 05, 2014 1:02 am
by bob
elcabesa wrote:in my effort to add multithreading in vajolet I have found some problems implenting transposition.
I'm have up to now used a probe function stockfish stile. I search for the right element and then return the pointer to it, then in the search code I use the pointed data.
having just read some articles about multithreading it now looks to me I could use in the search a value overwritten by another thread and have some problems.
I have then looked at senpai code and it correctly read the data from the transposition and copy them in the search variables so even if another thread later overwrite the transposition table element, the previously retrieved data are not modified.
am I understood it or am I missing something in stockfish code?
thank you all for your precious help
If you just maintain a pointer to the tt entry, you are asking for trouble, because between the time you do the probe and when you access the data, the entry could be overwritten and no longer apply to the current position. You have to copy the entry to local memory when you get the match. Immediately. Or risk using bogus stuff that might cause you to crash, or might cause you to make a wrong decision.
Re: transposition and multithreading question
Posted: Mon May 05, 2014 1:16 am
by syzygy
elcabesa wrote:nothing can assure us that ttValue, tte->depth(), tte->bound() were not changed by another thread.
Correct, and that will sometimes happen.
Again, as long as the hash move is validated nothing bad will happen. A few corrupted hash entries are not going to change the move being played more than one time per many years or so.
Again, see the many other threads in this forum on exactly the same topic.
Re: transposition and multithreading question
Posted: Mon May 05, 2014 1:20 am
by syzygy
bob wrote:If you just maintain a pointer to the tt entry, you are asking for trouble, because between the time you do the probe and when you access the data, the entry could be overwritten and no longer apply to the current position. You have to copy the entry to local memory when you get the match. Immediately. Or risk using bogus stuff that might cause you to crash, or might cause you to make a wrong decision.
As you know, this is not going to prevent that, very rarely, the hash entry is corrupted by another as it is being copied into local variables.
The xor-trick (to the TS: use the search function) can detect this corruption. But you agree,
as you wrote a paper on this, that even without the xor-trick nothing bad will happen provided that the program does not crash due to playing an illegal move.
Re: transposition and multithreading question
Posted: Mon May 05, 2014 5:43 am
by bob
syzygy wrote:bob wrote:If you just maintain a pointer to the tt entry, you are asking for trouble, because between the time you do the probe and when you access the data, the entry could be overwritten and no longer apply to the current position. You have to copy the entry to local memory when you get the match. Immediately. Or risk using bogus stuff that might cause you to crash, or might cause you to make a wrong decision.
As you know, this is not going to prevent that, very rarely, the hash entry is corrupted by another as it is being copied into local variables.
The xor-trick (to the TS: use the search function) can detect this corruption. But you agree,
as you wrote a paper on this, that even without the xor-trick nothing bad will happen provided that the program does not crash due to playing an illegal move.
I agree. But copying and then matching makes the window VERY small, as opposed to "match, then use the data way later."
Of course, a very small window is still a window. As to "nothing bad happening" I agree statistically. But I STILL refuse to accept excessive hash collisions and revert to a 32 bit hash signature, even though that paper clearly showed it was safe enough.