6

So I had a discussion with a colleague at work regarding the order of evaluation execution. Consider this conditional:

if (a > b && ref++) { do something }

We both agree that as per C standard the order is from left to right. However, the disagreement is that despite the order of evaluation, some instructions whose data will eventually be evaluated may be speculatively executed and then remain in this state despite the lazy evaluation.

For instance, ref is incremented before evaluating a > b, and the evaluation still happens left to right, that is the actual jump greater than instruction for both a > b and rev > 0 are executed in-order left to right, and abandoned at the first instance when !true. Now this goes against the whole concept of lazy evaluation, but what if ref is a stream of instructions, an inlined function maybe. It would make more sense to start executing some instructions speculatively. The concern is: are those instructions committed, even half way through.

Thoughts?

janjust
  • 796
  • 2
  • 7
  • 21
  • 6
    `&&` short-circuits. So it's not a matter of left to right evaluation. If `a <=b`, `ref` isn't incremented. – Jean-François Fabre Apr 17 '18 at 15:17
  • 7
    The CPU could speculatively execute `ref++` based on its branch predictor (`&&` branches, as Jean-François Fabre points out), but it will discard the increment and not commit the result to memory once the branch result is known (and the CPU knows it took the wrong path). [This question covers more on branch prediction](https://stackoverflow.com/q/11227809/1287251). – Cornstalks Apr 17 '18 at 15:22
  • 1
    What @Cornstalks said might be the actual source of this discussion you had, but it isn't related to the programming language C, it's about the design of modern CPUs. Speculatively executed code can't have any side effects until it's sure the correct branch was taken ... –  Apr 17 '18 at 15:29
  • What if ref is an atomic instruction? – janjust Apr 17 '18 at 15:30
  • @FelixPalmen, you're absolutely correct, that is how the discussion started :) – janjust Apr 17 '18 at 15:31
  • 2
    @janjust then the CPU can't execute it until it is sure it has to. There will be a memory barrier. –  Apr 17 '18 at 15:32
  • Small note: the jump condition for the `ref++` side is not `ref > 0` but `ref != 0`. A moot point if ref is unsigned, but that was not specified. – Zastai Apr 17 '18 at 16:11

3 Answers3

8

Operator && (as well as operator ||) are special in a sense as they guarantee "short-cut-evaluation" from left to right. This means that for a condition like expr1 && expr2, expr1 will always be evaluated first, and - even more - that expr2 will not get evaluated at all if expr1 already evaluated to false. This is not an optimization, this is guaranteed by the language.

Hence, in if (a > b && ref++), expression ref++ will be evaluated (including it's side effect of incrementing ref) if and only if a > b evaluates to true.

Stephan Lechner
  • 34,891
  • 4
  • 35
  • 58
  • Might want to add that `&&` and `||` introduce *sequence points* ... which you kind of already stated implicitly. –  Apr 17 '18 at 15:24
1

It's not possible with a > b && ref++ because of && operator short-circuits.

Think of that case:

f = fopen("foo.txt");
if ((f != NULL) && fread(buffer,10,1,f)) { ...

executing the second part if f==NULL would be a bug because the first part protects against it.

On the contrary, nothing prevents the compiler to do whatever it wants here:

a > b & ref++

& is the arithmetic and so both conditions are always executed. So even if the first condition is false, ref is incremented.

Jean-François Fabre
  • 137,073
  • 23
  • 153
  • 219
  • 1
    One thing worth pointing out with `a > b & ref++` is that not only are both sides evaluated, but the order of their evaluation is unspecified. It's not really relevant in simple expressions like these, but if they're function calls (with side effects), like `a() > b() & ref++`, there are no guarantees about the order of the evaluation of `a()`, `b()`, and `ref++`. – Cornstalks Apr 17 '18 at 15:26
1

C compilers are permitted to implement the "as-if" rule, meaning that they can do anything they like so long as the program's intent is respected.

Consider (a > b && ref++). The intention here is that ref will only be incremented if a > b is 1, and that must be the observed behaviour. This is because the right hand argument of && is only evaluated if the left hand argument is 1. However the generated assembly code might be such that the CPU can speculatively increment ref (branch prediction), and retract that incrementation with a pipeline dump if appropriate.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • 1
    The assembly code is not speculative. It can be programmed however using the as-if principle as "++ref; compare; undo ref++ iff result of comparison was xyz". But more likely this is the behavior of a particular CPU. – Aki Suihkonen Apr 17 '18 at 15:52
  • @AkiSuihkonen: Good point. Language is important. I've changed it. – Bathsheba Apr 17 '18 at 16:00