Handling for loop special cases

Question

In Java, C# or C++, suppose we have a very common situation where we need to iterate a large amount of times and execute a function doX, but on only one of the iterations we should execute a function doY.

int index = 123456;
for(int i = 0; i < 1000000; i++)
{
    if(i == index) doY();
    else doX();
}

In situations where I see a real performance issue, I usually break the loop in 2, but this can be very painful, especially if the loop's body is large. Does the compiled code really check for the condition on every iteration, or can it be optimized by the compiler? Furthermore, if index is not a constant at compile time, can there be such optimizations?

GCC's [loop splitting](https://gcc.gnu.org/ml/gcc-patches/2015-11/msg01564.html) doesn't like to split a loop of this form, I'm not aware of any patches that add that capability, but it could be done. — harold, Feb 05 '16 at 22:34
How do you expect to learn something meaningful and specific about performance that is relevant to 3 different programming languages, each of which runs on a different platform (CLR, JVM, native)? I think you need to pick a language in order for this to be a valid **single** question. — jpaugh, Feb 05 '16 at 23:09
Look, *nothing* is a performance issue if it only accounts for a tiny fraction of time. How many cycles are spent in `doX()`? If it's less than 10 times the `if(i==index)` test, *maybe* it's a performance issue. Certainly if the loop's body is large it won't be. — Mike Dunlavey, Feb 05 '16 at 23:46

score 10 · Accepted Answer · edited May 23 '17 at 12:06

This usually won't cause a huge performance issue. This is due to branch predicting. Refer to this famous question.

Branch predicting is basically assembly's way of guessing which way the if-statement will evaluate to. If it guesses right, it will take almost no time. If it guesses wrong, it will backtrack and cause performance issues. The branch predictor will generally use it's previous branched route as the "guess" for the next branch.

Since your if-statement evaluates to false nearly time. The branch predictor will predict correctly nearly every time.

So to answer your question "Does the compiled code really check for the condition on every iteration?". No it does not. Though it's not optimized by the compiler, but by the assembly pipeline itself.

Handling for loop special cases

1 Answers1