Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# If-else statements in for loops

  1. Apr 10, 2017 #1

    ChrisVer

    User Avatar
    Gold Member

    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
     
  2. jcsd
  3. Apr 10, 2017 #2

    jack action

    User Avatar
    Science Advisor
    Gold Member

    The sentence just before the one you quoted:
    In the link, you have an example of loop-invariant (i.e. constant) expression.
     
  4. Apr 10, 2017 #3

    ChrisVer

    User Avatar
    Gold Member

    So does it mean that all C++ compilers can do this optimization by themselves?
     
  5. Apr 10, 2017 #4

    Mark44

    Staff: Mentor

    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.
     
  6. Apr 11, 2017 #5

    DrClaude

    User Avatar

    Staff: Mentor

    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
     
  7. Apr 11, 2017 #6

    phyzguy

    User Avatar
    Science Advisor

    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
     
  8. Apr 11, 2017 #7
    Something like this:

    Code (Text):
    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.

    Code (Text):
    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
    }
     
  9. Apr 11, 2017 #8

    jim mcnamara

    User Avatar

    Staff: Mentor

    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
     
  10. Apr 15, 2017 #9

    ChrisVer

    User Avatar
    Gold Member

    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.
     
  11. Apr 15, 2017 #10

    jim mcnamara

    User Avatar

    Staff: Mentor

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted