5

I was reading my textbook for my computer architecture class and I came across this statement.

A second important distinction between the logical operators '&&' and '||' versus their bit-level counterparts '&' and '|' is that the logical operators do not evaluate their second argument if the result of the expression can be determined by evaluating the first argument. Thus, for example, the expression a && 5/a will never cause a division by zero, and the expression p && *p++ will never cause the dereferencing of a null pointer. (Computer Systems: A Programmer's Perspective by Bryant and O'Hallaron, 3rd Edition, p. 57)

My question is why do logical operators in C behave like that? Using the author's example of a && 5/a, wouldn't C need to evaluate the whole expression because && requires both predicates to be true? Without loss of generality, my same question applies to his second example.

Sourav Ghosh
  • 133,132
  • 16
  • 183
  • 261
user2020493
  • 129
  • 6
  • 1
    `why do logical operators in C behave like that`...umm because that is how they are designed to behave? – Sourav Ghosh Sep 21 '16 at 10:20
  • 1
    No, C doesn't need to evaluate the whole expression, since `false && a` is false for all values of `a`, and `true || b` is true for all values of `b`. As for "why?", the reason is simply that C is specified in this way; probably because this behaviour is often useful, and only rarely problematic. – Mankarse Sep 21 '16 at 10:20

5 Answers5

4

Short-circuiting is a performance enhancement that happens to be useful for other purposes.

You say "wouldn't C need to evaluate the whole expression because && requires both predicates to be true?" But think about it. If the left hand side of the && is false, does it matter what the right hand side evaluates to? false && true or false && false, the result is the same: false.

So when the left hand side of an && is determined to be false, or the left hand side of a || is determined to be true, the value on the right doesn't matter, and can be skipped. This makes the code faster by removing the need to evaluate a potentially expensive second test. Imagine if the right-hand side called a function that scanned a whole file for a given string? Wouldn't you want that test skipped if the first test meant you already knew the combined answer?

C decided to go beyond guaranteeing short-circuiting to guaranteeing order of evaluation because it means safety tests like the one you provide are possible. As long as the tests are idempotent, or the side-effects are intended to occur only when not short-circuited, this feature is desirable.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • 2
    Performance has nothing to do with this. The compiler is perfectly able to optimize code without the language dictating such things. – Lundin Sep 21 '16 at 12:54
  • @Lundin: If the short-circuiting and evaluation order rules weren't in effect, the compiler couldn't make any optimizations that skipped any test that it couldn't verify deterministically was side-effect free (which, without link time optimization, means basically any function call outside the current compilation unit). Granted, the spec could have made short-circuiting optional (which would mean it was only a possible optimization, not useful for control flow), but performance is a big part of this. – ShadowRanger Sep 21 '16 at 20:38
  • That doesn't make any sense. If there _were_ side effects, you wouldn't _want_ the compiler to optimize them away. Because these operators mandate order of evaluation, they can be used for flow control, just as much as `if - else`. If you write something like `if(true){} else` then you don't want the else to be executed no matter what's inside it. If you write something like `a + b` though, you want both operands to be evaluated. Comparing sequenced or non-sequenced expressions in terms of side-effects is like comparing apples and oranges. – Lundin Sep 22 '16 at 06:32
  • 1
    Take the example `if(a() | b())`. An optimizing compiler will not evaluate both operands if it finds that the first operand is not-zero. This isn't required by the standard but very likely to happen. If order of evaluation had been forced on this expression, the compiler might be forced to skip all optimizations it could have done on the temporary results, because all evaluations has to be completed. Nor can it re-order the instructions. Essentially, a sequence point might work as a memory barrier. Furthermore, the sequence point will create a conditional branch, which slows down execution. – Lundin Sep 22 '16 at 06:33
1

A typical example is a null-pointer check:

if(ptr != NULL && ptr->value) {
    ....
}

Without short-circuit-evaluation, this would cause an error when the null-pointer is dereferenced.

The program first checks the left part ptr != NULL. If this evaluates to false, it does not have to evaluate the second part, because it is already clear that the result will be false.

alain
  • 11,939
  • 2
  • 31
  • 51
  • It would be nice to know the reason for the downvote. – alain Sep 21 '16 at 10:28
  • You kind of just reiterated what the question already stated. The crucial part is the last part of your last sentence. The rest could have been omitted. – Good Night Nerd Pride Sep 21 '16 at 10:57
  • @GoodNightNerdPride Assuming you're the downvoter, *what* did this answer "kind of just reiterate"? Currently, neither the question nor *any* answer succinctly uses the example of a NULL pointer check and a dereference of that same pointer to illustrate the usefulness of short-circuit evaluation. Not only that, the "last part of [the] last sentence" makes no sense without an explanation. On top of all that, **what's wrong with a fully-explained answer in the first place**, even if it does reiterate something? That "something" may be edited in the future. – Andrew Henle Sep 21 '16 at 11:19
1

In the expression X && Y, if X is evaluated to false, then we know that X && Y will always be false, whatever is the value of Y. Therefore, there is no need to evaluate Y.

This trick is used in your example to avoid a division by 0. If a is evaluated to false (i.e. a == 0), then we do not evaluate 5/a.

It can also save a lot of time. For instance, when evaluating f() && g(), if the call to g() is expensive and if f() returns false, not evaluating g() is a nice feature.

Tom Cornebize
  • 1,362
  • 15
  • 33
1

wouldn't C need to evaluate the whole expression because && requires both predicates to be true?

Answer: No. Why work more when the answer is known "already"?

As per the definition of the logical AND operator, quoting C11, chapter §6.5.14

The && operator shall yield 1 if both of its operands compare unequal to 0; otherwise, it yields 0.

Following that analogy, for an expression of the form a && b, in case a evaluates to FALSE, irrespective of the evaluated result of b, the result will be FALSE. No need to waste machine cycle checking the b and then returning FALSE, anyway.

Same goes for logical OR operator, too, in case the first argument evaluates to TRUE, the return value condition is already found, and no need to evaluate the second argument.

Sourav Ghosh
  • 133,132
  • 16
  • 183
  • 261
0

It's just the rule and is extremely useful. Perhaps that's why it's the rule. It means we can write clearer code. An alternative - using if statements would produce much more verbose code since you can't use if statements directly within expressions.

You already give one example. Another is something like if (a && b / a) to prevent integer division by zero, the behaviour of which is undefined in C. That's what the author is guarding themselves from in writing a && 5/a.

Very occasionally if you do always need both arguments evaluated (perhaps they call functions with side effects), you can always use & and |.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • 2
    Ick. I would not encourage `&` and `|` like that. Aside from precedence issues with the bitwise operators, they're not equivalent. Testing `if (func1() && func2())` is not equivalent to `if (func1() & func2())` even beyond the "want both functions evaluated" case; if either of them returns a truthy value that's not just `1`, you could end up with `0x8 & 0x1` (both truthy values) producing `0x0`, false (because the bits don't line up), where `0x8 && 0x1` would produce true. Fixing it means remembering to put `!!` in front of everything or other hacks that `&&` wouldn't need. – ShadowRanger Sep 21 '16 at 10:31
  • @ShadowRanger I do agree with the short-comings you commented, but agree with Bathsheba that "if you do always need both arguments evaluated", this is _a_ way to do so. A stronger argument against `if (func1() & func2())` would include a proposed alternative. – chux - Reinstate Monica Sep 21 '16 at 15:41