Is std::min free and does not cost speed?

[Uri Blass]

The reason that I ask is that after
I found a bug in stockfish
marco corrected it and replaced
Value rbeta=beta+200 by
Value rbeta = std::min(beta + 200, VALUE_INFINITE);

see the following code:

Code: Select all

if (   !PvNode
        &&  depth >= 5 * ONE_PLY
        && !ss->skipNullMove
        &&  abs(beta) < VALUE_MATE_IN_MAX_PLY)
    {
        Value rbeta = std::min(beta + 200, VALUE_INFINITE); std::min(beta + 200, VALUE_INFINITE);

considering the fact that VALUE_MATE_IN_MAX_PLY=29880 when VALUE_INFINITE=30001
I think that a faster code that practically get the same result is the code at the bottom of this post and I wonder what is your opinion.

It seems to me that logical difference can be only in case that abs(beta)>VALUE_INFINITE-200 and these cases practically never happen in games in normal positions and I do not care about little difference in the search in positions when the program already found that one side has a forced mate in some line(and the difference is only for very long mates)

Note also that I checked that the bench is the same in both cases even when I use depth 20 and not the default depth 13 and bench calculate the number of nodes in many positions(note that I practically suspect that it may be better to use less pruning when the score is very high so it is better to use different bounds but it is a functional change that should be tested with normal SPRT).

Code: Select all

if (   !PvNode
        &&  depth >= 5 * ONE_PLY
        && !ss->skipNullMove
        &&  abs(beta) <=VALUE_INFINITE-200)
    {
        Value rbeta = beta + 200;

[lucasart]

why do you spam this forum?
why not post this in the SF forum?
besides you question is rhetorical and you know the answer...

what you should do is send a pull request to marco on github. simple, efficient, spam free.

[michiguel]

why do you spam this forum?
why not post this in the SF forum?
besides you question is rhetorical and you know the answer...

what you should do is send a pull request to marco on github. simple, efficient, spam free.

I do not see any problem with the OP question, and it is on topic for this subforum.

Miguel

[michiguel]

The reason that I ask is that after
I found a bug in stockfish
marco corrected it and replaced
Value rbeta=beta+200 by
Value rbeta = std::min(beta + 200, VALUE_INFINITE);

see the following code:

Code: Select all

if (   !PvNode
        &&  depth >= 5 * ONE_PLY
        && !ss->skipNullMove
        &&  abs(beta) < VALUE_MATE_IN_MAX_PLY)
    {
        Value rbeta = std::min(beta + 200, VALUE_INFINITE); std::min(beta + 200, VALUE_INFINITE);

considering the fact that VALUE_MATE_IN_MAX_PLY=29880 when VALUE_INFINITE=30001
I think that a faster code that practically get the same result is the code at the bottom of this post and I wonder what is your opinion.

It seems to me that logical difference can be only in case that abs(beta)>VALUE_INFINITE-200 and these cases practically never happen in games in normal positions and I do not care about little difference in the search in positions when the program already found that one side has a forced mate in some line(and the difference is only for very long mates)

Note also that I checked that the bench is the same in both cases even when I use depth 20 and not the default depth 13 and bench calculate the number of nodes in many positions(note that I practically suspect that it may be better to use less pruning when the score is very high so it is better to use different bounds but it is a functional change that should be tested with normal SPRT).

Code: Select all

if (   !PvNode
        &&  depth >= 5 * ONE_PLY
        && !ss->skipNullMove
        &&  abs(beta) <=VALUE_INFINITE-200)
    {
        Value rbeta = beta + 200;

No value should ever be greater than INFINITE _ever_. In fact, those should be assert()'ed to make sure it never happens, even by mistake. Once you have a constant with that name, you are certainly implying that type of limit and I am sure that there could be assumptions throughout the program that may rely on that. Things like that could easily crash the program, for instance, when you store bounds in the hashtable, distance to mates that are negative etc. etc.

Miguel

[hgm]

Actually I do that all the time. In my engines INF just means the maximum possible score. For instance in micro-Max I have something like

Code: Select all

Search(alpha, beta, depth)
{
  eval = Eval();
  if(alpha < eval) alpha--;
  if(beta <= eval) beta--;
  bestScore = (depth <= QSDEPTH ? eval : -INF);
  if(bestScore >= beta) goto cutoff;
  ...
  for(ALL_MOVES) {
    if(victim == KING) score = +INF;
    ...
  }
  ...
 cutoff:
  if(bestScore < eval) bestScore++;
  return bestScore;
}

Because Eval() never returns mate scores, the bestScore++ can never increment +INF, so the scores will always be confined to { -INF, +INF }.

alpha and beta can be pushed below -INF by their decrementing at the to of Search(), as they are always decremented for negative mate scores, which are all below eval. When beta is pushed down to -INF or below, you get a 'stand-pat cutoff' even in full-width search based on the initial -INF score.

This is actually a good thing: it means that even if you are checkmated in the current node, this is still a result that is so good that it refutes the previous move, and will cause a fail-low there. Apparently because he already has found a faster mate in a side branch. It is a form of mate-distance pruning.

Window limits just indicate what scores you consider sufficient. There is no reason why they should not be above the maximum possible score, or below the minimum. That just means you will never consider any score sufficient, or every score sufficient. That doesn't do any harm, and actually sometimes is exactly what you need.

[Joerg Oster]

Uri, I am far from being an expert, but do you really expect to have a measurable speed difference between these two implementations?
In a non-critical part of the code? Compilers are very good in optimizing, nowadays.

Furthermore, Marco gave a clear hint, why he chose that one.

Other fixes where possible but this one is pointed
exactly at the source of the bug, so it is the best
from a code documentation point of view.

P.S. If you want to discuss Marco's decisions, the Stockfish Forum is the appropriate place to do so. If it's more about coding questions, you might have asked in a more neutral way. Just my 2 cents.

[Evert]

I would personally prefer the latter since the code is simpler. That's assuming that they're functionally equivalent, which isn't entirely obvious.
That's all personal preference though, and not worth fighting over.

As for performance, choosing one over the other for performance reasons in this case seems overly pedantic. It's not going to make any measurable difference. If I were to test the speed difference at all, I'd use a benchmark test (but I don't think the difference will be above the noise, so it's a waste of time).

[AlvaroBegue]

The cartoon picture of CPU performance in my head is that things like cache misses are extremely expensive, miss-predicted branches are expensive, and additions and subtractions are ridiculously cheap.

std::min between two ints is probably not free, but it's going to be in the "ridiculously cheap" category, because the compiler will probably convert it to a comparison (similar to a subtraction for all purposes) followed by a conditional MOV instruction, which doesn't introduce a branch.

[Uri Blass]

Uri, I am far from being an expert, but do you really expect to have a measurable speed difference between these two implementations?
In a non-critical part of the code? Compilers are very good in optimizing, nowadays.

Furthermore, Marco gave a clear hint, why he chose that one.

Other fixes where possible but this one is pointed
exactly at the source of the bug, so it is the best
from a code documentation point of view.

P.S. If you want to discuss Marco's decisions, the Stockfish Forum is the appropriate place to do so. If it's more about coding questions, you might have asked in a more neutral way. Just my 2 cents.

I could ask also in the stockfish forum but
I prefer to ask here because this forum is more friendly towards me
and lucas could blame me that I spam the forum also if I ask in the stockfish forum.
The subject is on topic both here and in the SF froum.

You may be right that the code is not critical code in case that depth>=5*ONE_PLY does not happen often(the way to check it is simply
to add a counter to the code to see how many times the search call it practically in searches) and I will check it later.

I also think that maybe it is better to replace if a&&b by if b&&a when
it is clear that condition a happens more often than condition b
but maybe the compiler understands it
and in this case it is not needed.

[Rein Halbersma]

On a related note, detecting overflow from +INF is hard enough but detecting overflow from INT_MAX is even harder. For Apple users who have been bitten by the Undefined Behavior demons, here's a blog post about Apple's newly released Secure Coding Guide.