title: Why is branch prediction faster than no branch at all?
body: <p>Inspired by this question:
  <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">Why is it faster to process a sorted array than an unsorted array?</a></p>
  
  <p>I wrote my own branch prediction experiment:</p>
  
  <pre><code>public class BranchPrediction {
      public static void main(final String[] args) {
          long start;
          long sum = 0;
  
          /* No branch */
          start = System.nanoTime();
          sum = 0;
          for (long i = 0; i &lt; 10000000000L; ++i)
              sum += i;
          System.out.println(System.nanoTime() - start);
          System.out.println(sum);
  
          /* With branch */
          start = System.nanoTime();
          sum = 0;
          for (long i = 0; i &lt; 10000000000L; ++i)
              if (i &gt;= 0)
                  sum += i;
          System.out.println(System.nanoTime() - start);
          System.out.println(sum);
  
          /* No branch (again) */
          start = System.nanoTime();
          sum = 0;
          for (long i = 0; i &lt; 10000000000L; ++i)
              sum += i;
          System.out.println(System.nanoTime() - start);
          System.out.println(sum);
  
          /* With branch (again) */
          start = System.nanoTime();
          sum = 0;
          for (long i = 0; i &lt; 10000000000L; ++i)
              if (i &gt;= 0)
                  sum += i;
          System.out.println(System.nanoTime() - start);
          System.out.println(sum);
      }
  }
  </code></pre>
  
  <p>The result confuses me: according to program output, the loop with a branch is reliably faster than no branch loops.</p>
  
  <p>Example output:</p>
  
  <pre><code>7949691477
  -5340232226128654848
  6947699555
  -5340232226128654848
  7920972795
  -5340232226128654848
  7055459799
  -5340232226128654848
  </code></pre>
  
  <p>Why is it so?</p>
  
  <p>Edit:</p>
  
  <ul>
  <li>Disassembled class shows Java compiler did not optimize (miss) anything (<a href="https://gist.github.com/HouzuoGuo/5692424" rel="nofollow noreferrer">https://gist.github.com/HouzuoGuo/5692424</a>)</li>
  <li>The Java benchmark technique used by author of <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">Why is it faster to process a sorted array than an unsorted array?</a> is the same as mine.</li>
  <li>The machine is an Intel core i7, running Linux 3.2 64-bit and Oracle JVM 1.7 64-bit</li>
  <li>When I supersize the number of loop iterations, with-branch loop runs multi-SECONDS faster than non-branch loop.</li>
  </ul>