If-else statements in for loops

[ChrisVer]

I've come across a rumor that states that if-else statements can make the loops go slower. Well, it's not rumors since the writer offered numbers (times) to support the statement.
http://blogs.sas.com/content/iml/2012/02/13/avoid-unnecessary-if-then-statements-in-loops.html
I was wondering though: it says "For some compiled programming languages such as FORTRAN and C/C++, an optimizing compiler can sometimes determine that an expression is constant and move it outside of the loop for you."
What does "sometimes determine that an expression is constant" and can you know it beforehand?
Thanks

 

[jack action]

The sentence just before the one you quoted:

This is sometimes called "loop hoisting."

In the link, you have an example of loop-invariant (i.e. constant) expression.

 

[ChrisVer]

In the link, you have an example of loop-invariant (i.e. constant) expression.

So does it mean that all C++ compilers can do this optimization by themselves?

 

[Mark44]

So does it mean that all C++ compilers can do this optimization by themselves?

I don't think it's reasonable to make blanket statements about "all C++ compilers" as far as what optimizations they can or cannot do.

A major reason the if ... else statements inside loops slow things down is that they disrupt the pipeline of instructions. Modern processors are fast, in part, because instructions pass through a multi-stage pipeline, with up to 14 stages. (I believe this number is accurate.) A program that executes sequentially, with one instruction executing after another, keeps the pipeline full and everything chugging along. If a branch instruction is hit (i.e., such as an if ... else), a modern processor can make an educated guess as to which branch will be taken. If its prediction is correct, all is good. If the guess is incorrect, the pipeline is invalidated, and must be filled again, slowing things down.

 

[DrClaude]

So does it mean that all C++ compilers can do this optimization by themselves?

I don't think it's reasonable to make blanket statements about "all C++ compilers" as far as what optimizations they can or cannot do.

Especially since it is usually the programmer that controls the level of optimization!

For gcc, you can see here the optimizations performed at the different levels. At the lowest level of optimization, -O or -O1, you already find
-fmove-loop-invariants

 

[phyzguy]

I have found that if statements inside of loops can slow things dramatically, for the reason Mark44 explained. Sometimes you have no choice, but in one instance I sped my code up substantially by changing the sequence from:
for (i...)
if (test) do A
else do B

to:
if (test)
for (i...)
do A
else
for (i...)
do B

 

[newjerseyrunner]

Something like this:

float theta = 0;
for(unsigned int i = 0; i < 255; ++i){
     callFunction(theta + pi);
}

It'll pull that theta + pi out because it'll always be the same while it's in a loop.

if switches don't really have much to do with performance. There is some low level optimization that allows you to do branch prediction, but almost nobody uses it. I only used it in a high speed parsing library, and even then, I left it as a compile option. If you're really into speed, you can do something like this.

if (likely(a > b)){
     //This block of code will immediately follow the jump, this is faster because it's almost certainly already in processor cache
} else {
    //This block of code may be any number of bytes away
}

 

[jim mcnamara]

The technical term is branch prediction; some compilers have features that let the programmer tell the compiler which branch of an if statement is expected to happen the most frequently.

The reason this is important is that memory is a lot slower than modern cpu's. Which is why prefetch of instructions helps improve execution speed. So having to go out and refetch new instructions can be a real bottleneck.

Ulrich Drepper has an older white paper, still very valid. If you want to improve your code efficiency consider reading:
https://www.akkadia.org/drepper/cpumemory.pdf

 

[ChrisVer]

Ulrich Drepper has an older white paper, still very valid. If you want to improve your code efficiency consider reading:
https://www.akkadia.org/drepper/cpumemory.pdf

that's a long paper but interesting, I'll have a look in it :)
though in general, in order to see how the compiler compiles the code you have to look at its features (as in DrClaude's reference for gcc) and you have control over it.

 

[jim mcnamara]

Under gcc's control? No, not always. Example: Algorithm choice has a massive impact. Locality (of data) is under your control, as you will see in the article. It can have a big impact as well. Branching too, as case statements provide an interesting challenge. Nested if then else clauses have impact too. Threading. I/O buffer cache size. The list goes on...

You control all these fully. I would suggest you read known good C/C++ code -- like the source for GNU grep or GNU C library code:
https://www.gnu.org/software/libc/sources.html