9

For instance (Lets say we are talking about C++ if that makes a differnce), In an && operator if I know that one statement will result to 0 more often/has a higher chance then the other statement should I put that on the left side, and the other statement on the right?

Same goes for || operator if I know that one statement will result to 1 more often/has a higher chance then the other statement should I put that on the left side, and the other statement on the right?

Now doing all this would cause a lot of time analysing the program, but if this does speed up execution time for the program is it worth doing it, and is this something that embedded/real-time system programmers look into to speeding up their application if necessary?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Omid CompSCI
  • 1,861
  • 3
  • 17
  • 29
  • 4
    *is it worth doing it* is going to depend on a lot of factors. The biggest is how much does it cost to do this tuning and how much do you save from the added performance. – NathanOliver Jul 22 '16 at 17:26
  • in principle yes, thats the reason the shortcircuit operators exist – 463035818_is_not_an_ai Jul 22 '16 at 17:26
  • Is this like a last effort to improve performance in embedded applications (that have hard deadlines), or is it something they actually do look at to improve performance? – Omid CompSCI Jul 22 '16 at 17:31
  • 2
    First make sure the program is correct. Then if it's too slow, profile it. Fix whatever is slowing it down. Don't waste time on that before profiling. This is my opinion; voted to close as **primarily opinion-based**. – Cheers and hth. - Alf Jul 22 '16 at 17:32
  • 1
    @OmidCompSCI: also usually the fastest solution are often simple, and elegant (on source level), so those statements often end in best order naturally. Otherwise you are probably dealing with something where hard data from profiler are a must. There's no shortcut to optimize without measuring with today's complex machines, too many good intentions can backfire easily. – Ped7g Jul 22 '16 at 17:45
  • 1
    I had a case where several expensive to calculate conditions where being checked before one very cheap one that would reject the whole thing 90% of the time. Reordering those was a huge win, but also a very special case. – Retired Ninja Jul 22 '16 at 17:50
  • For example (how important is to though out your algorithm and structures), check [this](https://youtu.be/YQs6IC-vgmo) (or search for text version). Some `if` inside loop of these would change very little, while the boost from using better fit for data structures is huge. – Ped7g Jul 22 '16 at 17:50

5 Answers5

5

It depends. If the statement is as simple as :

if(y == 4 || x == 2)

and assume that frequency of x == 2 is much higher, so that we could have short-circuited the execution by writing like:

if(x == 2 || y == 4)

But you see we wont be getting much benefit out of this, as the statements is very simple and optimizing the code at this level may not be so worthy.

Now consider an example like :

if(y == an_expensive_function() || x == 2)

Here assume an_expensive_function() is very costly operation, say it's complexity is like exponential, the definitely it makes sense to put the statement like :

if(x == 2 || y == an_expensive_function())

to perform short-circuiting.

Embedded and application developers or any developer at first instance might not consider optimizing at such a fine granulaity if this is not giving them much benefits. They may not even consider it if things are working fine for them. So as a developer we need to check, how much time will it take to analyze and optimize the code at such a level and how much benefits do we get from this.

rj99999
  • 109
  • 10
  • Thank you for the explanation, and great example to understand! And apparently everyone is saying that no one really fine tunes the code to this extreme and it is important to solve the bottleneck first, before getting into such detail. – Omid CompSCI Jul 22 '16 at 17:49
4

First, make sure you are not a victim of premature optimization.

With that said, make sure that you did everything you could to speedup the bottleneck of your program.

Doing what you said about the short circuiting may be a good idea in certain cases, but that's heavily depends all your statements.

For example, if you have something like:

if(slowFunction() && complexConditionRootsAndExponents && ConditionUsuallyZero)

then you would probably want that last term to be first, wouldn't you?

However, be careful, things are not always trivial to permute in a logical sequence. Check for example my answer in Why this program printed fork 4 times?, where one can see that short circuit can affect the flow of the execution of the program.

TL;DR

In general though, it is rare to get significant speedup by permuting the terms in the conditions. Focus on the bottleneck of your program and tackle that as hard as you can!

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • 1
    Thank you for the example and reference. Yes I did not know that premature optimization was a thing, however I now understand it as the bottleneck should be tackled first! – Omid CompSCI Jul 22 '16 at 17:47
  • 1
    You are welcome @OmidCompSCI. You asked a good question, I had asked that some years ago too and I had done the mistake to try optimizing this, rather than the bottleneck. And it didn't make a difference. Optimizing however the bottleneck of your program will for sure bring nice results! :) Good luck. – gsamaras Jul 22 '16 at 17:49
4

The answer to the question is: Yes, it does impact performance.

Whether or not the performance gain is worth the cost of finding the locations that can be improved and changing the program is something only you can answer.

In most cases the performance change is going to be small, but if some of the operations involved are costly, it can be significant.

Be aware that there can also be correctness implications. For example if in if (foo() || bar()) it is important that bar is never called if foo returns true, then it would be a bug to re-order the calls.

Start by ensuring your program is correct. Then, if it is too slow; profile it and optimize where it will have the biggest impact. That may be the order of evaluation in a short-circuit context, but in most cases it will be something else.

Jesper Juhl
  • 30,449
  • 3
  • 47
  • 70
  • 1
    Thank you, it seems like finding the bottleneck is more important than looking for these little things, as it seems Cost is greater than finding these cases in most scenarios. – Omid CompSCI Jul 22 '16 at 17:46
3

You also have to consider, how costly the evaluation of each side is.

if (veryCostlyOftenFalse() && veryCheapRareFalse()) // may be faster other way around

Unless over 50% of your source are expression evaluations and branching, I would say this is last-resort optimization, when you are happy with everything else.

The embedded/real-time application programmers focus roughly in this order:

  1. algorithm of course, finding reasonable trade-off in speed vs space.
  2. data structures in memory (hitting the caches as often as possible, when exercised by those algorithms).
  3. profiling of real application with real data, to see if there's some unexpected bottleneck and fixing those.
  4. if you are desperately missing somewhere a clock or two, and there's some complex if around, then yes, it may help...
Ped7g
  • 16,236
  • 3
  • 26
  • 63
3

Sure. if your conditional is of the form:

if ( x() && y() ) ...

and y is expensive to compute, and x is cheap and fails often, this will improve the local performance of the code.

So you want to know:

  • is the conditional in a performance-sensitive part of the program (if not, no point in optimizing it, write for clarity)
  • relative costs of the component computations of the short circuit expression
  • which cheap computations fail (for &&) or succeed (for ||) frequently.

In this case it is usually worth rearranging the short circuit expression elements.

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • Thank you for the short and simple example and explanation. Seems like most people say in simple scenarios like this it is best to rearrange them to improve performance, in complex situations the cost of analysing it would be much greater than the performance if any improvement. Looks like the key is tackling the bottleneck of the performance degrade! Thank you. – Omid CompSCI Jul 22 '16 at 18:09
  • 2
    FWIW, when I write such conditionals, I try to make the judgement about the ordering as I write it, based on what I know. Some might call this premature optimization; I don't feel the pejoriative is deserved. If the conditional is rarely executed, it won't matter if I get the order wrong. If the conditional turns out by accident to be in hot path, then to the degree I estimated right, the ordering is already correct and I don't have to find this place with a a profiler and fix it later; my code is aleady tuned. If I've done this everywhere, my code generally runs better anyway. – Ira Baxter Jul 22 '16 at 20:44