transposition and multithreading question

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.
elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

transposition and multithreading question

Post by elcabesa » Sun May 04, 2014 5:24 pm

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

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: transposition and multithreading question

Post by ZirconiumX » Sun May 04, 2014 5:48 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: transposition and multithreading question

Post by elcabesa » Sun May 04, 2014 6:21 pm

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

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: transposition and multithreading question

Post by elcabesa » Sun May 04, 2014 7:00 pm

is it simply a speed/precision compromise?

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: transposition and multithreading question

Post by syzygy » Sun May 04, 2014 7:50 pm

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.

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: transposition and multithreading question

Post by elcabesa » Sun May 04, 2014 8:40 pm

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.

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

Re: transposition and multithreading question

Post by bob » Sun May 04, 2014 11:02 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: transposition and multithreading question

Post by syzygy » Sun May 04, 2014 11:16 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: transposition and multithreading question

Post by syzygy » Sun May 04, 2014 11:20 pm

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.

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

Re: transposition and multithreading question

Post by bob » Mon May 05, 2014 3:43 am

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.

Post Reply