title: Trying famous branch-prediction example sometimes results in strange times
body: <p>I tried to duplicate the example in <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">this famous question</a>. My code looks like this:</p>
  
  <pre><code>#![feature(test)]
  extern crate rand;
  extern crate test;
  
  use test::Bencher;
  use rand::{thread_rng, Rng};
  
  type ItemType = u8;
  type SumType = u64;
  const TEST_SIZE: usize = 32_768;
  
  #[bench]
  fn bench_train(b: &amp;mut Bencher) {
      let numbers = get_random_vec();
      b.iter(|| calc_sum(&amp;numbers));
  }
  
  #[bench]
  fn bench_train_sort(b: &amp;mut Bencher) {
      let mut numbers = get_random_vec();
      numbers.sort();     // &lt;-- the magic difference
      b.iter(|| calc_sum(&amp;numbers));
  }
  
  fn get_random_vec() -&gt; Vec&lt;ItemType&gt; {
      thread_rng().gen_iter().take(TEST_SIZE).collect()
  }
  
  fn calc_sum(numbers: &amp;Vec&lt;ItemType&gt;) -&gt; SumType {
      let mut sum = 0;
      for &amp;num in numbers {
          if num &lt; ItemType::max_value() / 2 {
              sum += num.into();
          }
      }
  
      sum
  }
  </code></pre>
  
  <p>If I benchmark the exact code from above I get reasonable results (like in the linked question):</p>
  
  <pre><code>test bench_train      ... bench:     148,611 ns/iter (+/- 8,445)
  test bench_train_sort ... bench:      21,064 ns/iter (+/- 1,980)
  </code></pre>
  
  <p>However, if I change <code>SumType</code> to <code>u8</code> both versions run equally fast and much faster overall:</p>
  
  <pre><code>test bench_train      ... bench:       1,272 ns/iter (+/- 64)
  test bench_train_sort ... bench:       1,280 ns/iter (+/- 170)
  </code></pre>
  
  <p>First of: of course, the <code>sum</code> will overflow all the time, but in release mode the overflow checks of Rust are disabled, so we just calculate a wrong result without panicking. Could this be the reason for the surprisingly short time?</p>
  
  <p>Even stranger: when I change the implementation of <code>calc_sum</code> to something more idiomatic, the results change again. My second implementation:</p>
  
  <pre><code>fn calc_sum(numbers: &amp;Vec&lt;ItemType&gt;) -&gt; SumType {
      numbers.iter()
          .filter(|&amp;&amp;num| num &lt; ItemType::max_value() / 2)
          .fold(0, |acc, &amp;num| acc + (num as SumType))
  }
  </code></pre>
  
  <p>With this implementation the <code>SumType</code> doesn't matter anymore. With <code>u8</code> as well as with <code>u64</code> I get these results:</p>
  
  <pre><code>test bench_train      ... bench:     144,411 ns/iter (+/- 12,533)
  test bench_train_sort ... bench:      16,966 ns/iter (+/- 1,100)
  </code></pre>
  
  <p>So we again get the numbers we are expecting. So the question is:</p>
  
  <p><strong>What is the reason for the strange running times?</strong></p>
  
  <hr>
  
  <p><strong>PS</strong>: I tested with <code>cargo bench</code> which compiles in release mode.</p>
  
  <p><strong>PPS</strong>: I just noticed that in the first implementation of <code>calc_sum</code> I use <code>into()</code> for casting, whereas I use <code>as</code> in the second example. When also using <code>as</code> in the first example, I get more strange numbers. With <code>SumType = u64</code>:</p>
  
  <pre><code>test bench_train      ... bench:      39,850 ns/iter (+/- 2,355)
  test bench_train_sort ... bench:      39,344 ns/iter (+/- 2,581)
  </code></pre>
  
  <p>With <code>SumType = u8</code>:</p>
  
  <pre><code>test bench_train      ... bench:       1,184 ns/iter (+/- 339)
  test bench_train_sort ... bench:       1,239 ns/iter (+/- 85)
  </code></pre>