3

I've a conditional statement expensive_foo() which is false in 99.9% cases. And I have a conditional statement bar which is true in ~50% cases.

And I want some action be done if both statements are true. So I almost certainly know that expensive_foo() is false and I want to check it only if bar is true.

Will the code below check the expensive_foo() ONLY if bar is true? Or it will check expensive_foo() every time?

if ( bar && expensive_foo() ) { ... }

Or I need to make a structure like this:

if ( bar ) { if ( expensive_foo() ) { ... } }
Improve this question
14
  • 7
    Logical boolean operators short-circuit, unless overloaded, aka yes, foo will only be checked if bar is true. Though, I have to admit, I don't see the performance benefit from saving a single boolean comparision.. Commented Sep 14, 2012 at 12:50
  • 2
    Well, that would have been smart to put into the question. Commented Sep 14, 2012 at 12:52
  • 2
    So, do you do bar && heavy_method_yielding_foo() or foo = heavy_method(); if(bar && foo) ...? Commented Sep 14, 2012 at 12:54
  • 3
    Those are important details and without those, answering the question is basically impossible (or the answers will not be what you really wanted). Commented Sep 14, 2012 at 12:57
  • 1
    Because after your edit, it didn't apply anymore. And then you edited back. Commented Sep 14, 2012 at 13:01

5 Answers 5

Reset to default
5

The logical AND operator && is short-circuited, which means that it is guaranteed the second operand is evaluated if and only if the first one is evaluated as true. The conditions if (bar && foo) and if (bar) if (foo) are identical.

Given that foo is expensive to compute, you should almost definitely check bar first. Even though bar won't be predictable by the branch predictor very well, that's a minor effect compared to the computation of foo.

Thus the structure should probably be:

if (bar) { if (bool const foo = compute()) // expensive { // ... } }

Note that all of those constructions mean that we may or may not call compute(). If you require the function call unconditionally, then you should make it the first check. In that case, the successful branch prediction on the result should be exploited.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Which is only true semantically, not performance wise. If bar and foo are not side-effecting the compiler can still reorder them causing a performance penalty.
@usr: I'm pretty sure it can't.
@DeadMG the compiler can do anything which does not change the behavior of the program according to the standard. If no behavioral change is observable the compiler can do this. (The OP edited the post though telling us that foo is actually foo_expensive(). This makes my point moot, although it was correct).
@DeadMG depends. If they have side-effects the compiler can't reorder the side-effects. Otherwise, you can't observe the difference.
@Kolyunya: No. if (bar && compute()) is identical to if (bar) { if (compute()) { /* .. */ } }. It's safe and fine. I just thought you might like to store the result of compute(), or have an else branch. But if you don't, feel free to put everything into one single condition.
|
2

Both codes will check foo only in case bar is true. In first case this is guaranteed by the language lazy boolean expression evaluation (which actually could be explicitly turned off in some compilers, but is ON by default).

Improve this answer

2 Comments

I'd be surprised if any compiler allowed you to turn short-circuit evaluation off; that would break a lot of code.
You can turn it off by saying bar & foo.
1

The other answers are good, but I'm questioning the premise.

If you are querying a predicate that is false 99.9% of the time, that is analogous to doing linear search in a list of 2000 entries, where the item you are looking for could be anywhere with roughly equal probability.

In that case, typically one would try to organize the list differently so as to do a O(logN) (or better) search instead of O(N). I don't know if you can do this, but that is where I would focus.

When a question is being asked with highly skewed probability, that can be a big speedup opportunity, if one can un-skew it. (Assuming a big % of time is spent in this activity. If not, the point is moot.)

Improve this answer

Comments

1

I'd be surprised if the optimized assembly for both wasn't exactly the same. expensive_foo() will never be called if bar is false.

Improve this answer

Comments

1

I saw a comment that the compiler can re-order operations and I'm inclined to that opinion. The efforts to improve automatic parallelization of the sequential programs has resulted in somewhat better compilers and it helps a programmer to avoid complex routines of parallelization from their programs. The compiler could re-order the operations provided the re-ordering does not violate/worsen the locality or in a broad sense doesn't violate the actual intention of the of the program.

But I doubt the fact that the compiler would try to re-order a conditional statement like :

 if ( bar && expensive_foo() )

If the less expensive Boolean function is put at the beginning, it is certain that we can save some time.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.