Benefits of using short-circuit evaluation

Question

boolean a = false, b = true;
if ( a && b ) { ... };

In most languages, b will not get evaluated because a is false so a && b cannot be true. My question is, wouldn't short circuiting be slower in terms of architecture? In a pipeline, do you just stall while waiting to get the result of a to determine if b should be evaluated or not? Would it be better to do nested ifs instead? Does that even help?

Also, does anyone know what short-circuit evaluation is typically called? This question arose after I found out that my programming friend had never heard of short-circuit evaluation and stated that it is not common, nor found in many languages, and is inefficient in pipeline. I am not certain about the last one, so asking you folks!

Okay, I think a different example to perhaps explain where my friend might be coming from. He believes that since evaluating a statement like the following in parallel:

(a) if ( ( a != null ) && ( a.equals(b) ) ) { ... }

will crash the system, an architecture that doesn't have short-circuiting (and thereby not allowing statements like the above) would be faster in processing statements like these:

(b) if ( ( a == 4 ) && ( b == 5 ) )

since if it couldn't do (a) in parallel, it can't do (b) in parallel. In this case, a language that allows short-circuiting is slower than one that does not.

I don't know if that's true or not.

Thanks

Answer 1

How can a nested if not stall? Actually if a and b are both variables and not expressions with side effects, they can be loaded in parallel by a good compiler. There's no benefit to using more ifs except increasing your line count. Really, this would be the worst kind of second guessing a compiler.

It's called short-circuit evaluation.

Answer 2

Depending upon the context, it can also be called "Guarding".

And I've seen it in just about every language I've worked in - which pushes close to a dozen.

Answer 3

Short circuit evaluation is translated into branches in assembly language in the same way if statements are (branches are basically a goto), which means it is not going to be any slower than if statements.

Branches don't typically stall the pipeline, but the processor will guess whether the branch is taken or not, and if the processor is wrong it will have to flush everything that has happened since it made the wrong guess from the pipeline.

Short circuit evaluation is also the most common name for it, and is found in most languages in some form or another.

Answer 4

I honestly wouldn't worry about it. Testing a boolean is really fast. Short-circuiting only gets interesting / useful when the second expression has side effects:

if ( ConfirmAction() && DestroyAllData() )
   Reboot();

...or depends on the first test:

if ( myDodgyVar != null && myDodgyVar.IsActive() )
   DoSomethingWith(myDodgyVar);

Answer 5

A useful short circuit I use is something like this:

if (a != null && a.equals(somevalue)) {
    ... do something.
}

This is, in my opinion very readable, and functions quite well. Generally, I try too avoid to much nesting because it leads to ugly code.

All my opinion though.

Answer 6

Most languages do short-circuit evaluation of boolean expressions. I have always heard it referred to as short-circuit evaluation.

The example in the question is a pretty simplistic example that doesn't really provide much of a performance benefit. The performance benefit comes when the expressions are complex to evaluate.

As an example of when this would be good imagine a game program that has something like:

if (someObject.isActive() && someOtherObject.isActive() && CollisionDetection.collides(someObject, someOtherObject) {
  doSomething();
}

In this case the collision detection is far more expensive than the active checks. There would be a significant performance boost if there were lots of inactive objects in the system.

Answer 7

I don't know anything about pipelining, but short-circuit evaluation is a common feature of many languages (and that's also the name I know it by). In C, && and the other operators define a sequence point just like the ; operator does, so I don't see how short-circuit evaluation is any less efficient than just using multiple statements.

Answer 8

First, your friend is wrong. Short-circuit evaluation (aka minimal evaluation) is available in most languages and is better than nested ifs for parallel languages (in which case the first of the conditions that returns will cause execution to continue)

In any case, even in a straightforward non-parallel language I don't see how nested ifs would be faster as execution would block until the first condition is evaluated.

Answer 9

i've only heard of it as short circuit. in a pipeline doesnt the next op that goes in depend on the outcome of the if statement? if that is the case this would more optimized so it wouldnt have to test two values every time.

Answer 10

Short-circuit, or minimal evaluation is just syntactic sugar for nested ifs. To assume it is inefficient, or causes stalls is a case of premature optimization. At this point, most compilers are intelligent enough to correctly interpret and optimize these statements. Using these statements can greatly reduce nesting, and therefore improve code readability, which should be your number one goal.

Answer 11

Regarding whether or not short-circuiting is efficient, pipelining is unlikely to have much of an impact on performance. In situations where it could have an impact, there's nothing to stop the compiler from testing multiple conditions in parallel so long as these tests doesn't have side-effects. Plus, modern CPUs have several mechanisms useful for improving the pipeline performance of branchy code.

Nested ifs will have the same effect as short-circuiting &&.

'Short-circuit evaluation' is the most common name for it, and your friend is wrong about it being uncommon; it's very common.

Answer 12

VB.Net has a different syntax depending on whether or not you want it to short circuit or not. Because of legacy reasons, the default behaviour is to not short circuit. The syntax is as follows

Non Short Circuit

IF A And B THEN
    ...
END IF

Short Circuit

IF A AndAlso B THEN
    ...
END IF

You can use Or / OrElse if you want to short circuit an OR statement. Which is really nice in situations like the following

If MyObj IsNot Nothing AndAlso MyObj.Value < SomeValue Then
    ....
End If

Personally while I understand that short circuiting can speed things up, it's definitely not something that's obvious from just looking at the code. I could see an inexperienced developer getting confused by the behaviour. It even seems like something that could happen or not depending on compiler flags for level of optimization. I like how VB is verbose about which behaviour you actually want to accomplish.

Answer 13

Short-circuiting boolean expressions are exactly equivalent to some set of nested ifs, so are as efficient as that would be.

If b doesn't have side-effects, it can still be executed in parallel with a (for any value of "in parallel", including pipelining).

If b has side effects which the CPU architecture can't cancel when branch prediction fails then yes, this might require delays which wouldn't be there if both sides were always evaluated. So it's something to look at if you do ever find that short-circuiting operators are creating a performance bottleneck in your code, but not worth worrying about otherwise.

But short-circuiting is used for control flow as much as to save unnecessary work. It's common among languages I've used, for example the Perl idiom:

open($filename) or die("couldn't open file");

the shell idiom:

do_something || echo "that failed"

or the C/C++/Java/etc idiom:

if ((obj != 0) && (obj->ready)) { do_something; } // not -> in Java of course.

In all these cases you need short-circuiting, so that the RHS is only evaluated if the LHS dictates that it should be.

Answer 14

Languages supporting short-circuiting:

Ada, Eiffel, ALGOL 68, C1, C++, C#, Java, R, Erlang, Standard ML, Javascript, MATLAB, Lisp, Lua, Scheme, OCaml, Haskell, Pascal,Perl, Ruby, PHP, Python, Smalltalk, Visual Basic .NET

Taken from Short-circuit evaluation

Answer 15

http://www.rawkam.com/?p=963