title: How to understand the tricky speed up
body: <p>Sorry for may be too abstract question, but for me it is quite practical + may be some experts had similar experience and can explain it.</p>
  
  <p>I have a big code, about 10000 lines size.</p>
  
  <p>I notices that if in a certain place I put</p>
  
  <pre><code>if ( expression ) continue;
  </code></pre>
  
  <p>where expression is <strong>always false</strong> (double checked with logic of code and cout), but depends on unknown parameters (so compiler can't simply rid of this line during compilation) the speed of the program is <strong>increased by 25%</strong> (the result of calculation are the same). If I measure speed of the loop itself the speed up factor is bigger than 3.</p>
  
  <p>Why can this happen and what is possible ways to use this speed up possibility without such tricks?</p>
  
  <p>P.S. I use gcc 4.7.3, -O3 optimisation.</p>
  
  <hr>
  
  <p>More info:</p>
  
  <ol>
  <li><p>I have tried two different expressions, both works.</p></li>
  <li><p>If I change the line to:</p>
  
  <pre><code>if ( expression ) { cout &lt;&lt; " HELLO " &lt;&lt; endl; continue; };
  </code></pre>
  
  <p>the speed up is gone.</p></li>
  <li><p>If I change the line to:</p>
  
  <pre><code>expression;
  </code></pre>
  
  <p>the speed up is gone.</p></li>
  <li><p>The code, which surrounds the line looks like this:</p>
  
  <pre><code>for ( int i = a; ;  ) {
    do {
      i += d;
      if ( d*i &gt; d*ilast ) break;
  
        // small amount of calculations, and conditional calls of continue;
  
    } while ( expression0 );
    if ( d*i &gt; dir*ilast ) break;
  
    if ( expression ) continue;
  
     // very big amount calculations, and conditional calls of continue;
  
  }
  </code></pre>
  
  <p>the for loop looks strange. It is because I have modified the loops in order to catch this bottle neck. Initially expression was equal to expression0 and instead of do-loop I had only this continue.</p></li>
  <li><p>I tried use __builtin_expect in order to understand branch prediction. With</p>
  
  <pre><code>  // the expression (= false) is supposed to be true by branch prediction.
  if ( __builtin_expect( !!(expression), 1) ) continue; 
  </code></pre>
  
  <p>the speed up is 25%.</p>
  
  <pre><code>  // the expression (= false) is supposed to be false by branch prediction.
  if ( __builtin_expect( !!(expression), 0) ) continue; 
  </code></pre>
  
  <p>the speed up is gone.</p></li>
  <li><p>If I use -O2 instead of -O3 the effect is gone. The code is slightly (~3%) slower than the fast O3-version with the false condition.</p></li>
  <li><p>Same for "-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize". With one more option: "-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize -fipa-cp-clone" the effect is amplified. With "the line" the speed is same, without "the line" the code is 75% slower.</p></li>
  <li><p>The reason is in just following conditional operator. So the code looks like this:</p>
  
  <pre><code>for ( int i = a; ;  ) {
  
        // small amount of calculations, and conditional calls of continue;
  
    if ( expression ) continue;
  
      // calculations1
  
    if ( expression2 ) {
      // calculations2
    }
  
     // very big amount calculations, and conditional calls of continue;
  
  }
  </code></pre>
  
  <p>The value of expression2 is almost always false. So I changed it like this:</p>
  
  <pre><code>for ( int i = a; ;  ) {
  
        // small amount of calculations, and conditional calls of continue;
  
    // if ( expression ) continue; // don't need this anymore
  
      // calculations1
  
    if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
      // calculations2
    }
  
     // very big amount calculations, and conditional calls of continue;
  
  }
  </code></pre>
  
  <p>And have got desired 25% speed up. Even a little bit more. And behaviour no longer depends on the critical line.</p></li>
  </ol>
  
  <p><strong>If somebody knows materials, which can explain this behaviour without guesses I will be very glad to read and accept their answer</strong>.</p>