title: Why does this C++ function produce so many branch mispredictions?
body: <p>Let <code>A</code> be an array that contains an odd number of zeros and ones. If <code>n</code> is the size of <code>A</code>, then <code>A</code> is constructed such that the first <code>ceil(n/2)</code> elements are <code>0</code> and the remaining elements <code>1</code>.</p>
  
  <p>So if <code>n = 9</code>, <code>A</code> would look like this:</p>
  
  <p><code>0,0,0,0,0,1,1,1,1</code></p>
  
  <p>The goal is to find the sum of <code>1s</code> in the array and we do this by using this function:</p>
  
  <pre><code>s = 0;
  void test1(int curIndex){
      //A is 0,0,0,...,0,1,1,1,1,1...,1
  
      if(curIndex == ceil(n/2)) return;
  
      if(A[curIndex] == 1) return;
  
      test1(curIndex+1);
      test1(size-curIndex-1);
  
      s += A[curIndex+1] + A[size-curIndex-1];
  
  }
  </code></pre>
  
  <p>This function is rather silly for the problem given, but it's a simulation of a different function that  I want to look like this and is producing the same amount of branch mispredictions.</p>
  
  <p>Here is the entire code of the experiment:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;fstream&gt;
  
  using namespace std;
  
  
  int size;
  int *A;
  int half;
  int s;
  
  void test1(int curIndex){
      //A is 0,0,0,...,0,1,1,1,1,1...,1
  
      if(curIndex == half) return;
      if(A[curIndex] == 1) return;
  
      test1(curIndex+1);
      test1(size - curIndex - 1);
  
      s += A[curIndex+1] + A[size-curIndex-1];
  
  }
  
  
  int main(int argc, char* argv[]){
  
      size = atoi(argv[1]);
      if(argc!=2){
          cout&lt;&lt;"type ./executable size{odd integer}"&lt;&lt;endl;
          return 1;
      }
      if(size%2!=1){
          cout&lt;&lt;"size must be an odd number"&lt;&lt;endl;
          return 1;
      }
      A = new int[size];
  
      half = size/2;
      int i;
      for(i=0;i&lt;=half;i++){
          A[i] = 0;
      }
      for(i=half+1;i&lt;size;i++){
          A[i] = 1;
      }
  
      for(i=0;i&lt;100;i++) {
          test1(0);
      }
      cout&lt;&lt;s&lt;&lt;endl;
  
      return 0;
  }
  </code></pre>
  
  <p>Compile by typing <code>g++ -O3 -std=c++11 file.cpp</code> and run by typing <code>./executable size{odd integer}</code>.</p>
  
  <p>I am using an Intel(R) Core(TM) i5-3470 CPU @ 3.20GHz with 8 GB of RAM, L1 cache 256 KB, L2 cache 1 MB, L3 cache 6 MB.</p>
  
  <p>Running <code>perf stat -B -e branches,branch-misses ./cachetests 111111</code> gives me the following:</p>
  
  <pre><code>   Performance counter stats for './cachetests 111111':
  
      32,639,932      branches                                                    
       1,404,836      branch-misses             #    4.30% of all branches        
  
     0.060349641 seconds time elapsed
  </code></pre>
  
  <p>if I remove the line</p>
  
  <pre><code>s += A[curIndex+1] + A[size-curIndex-1];
  </code></pre>
  
  <p>I get the following output from perf:</p>
  
  <pre><code>  Performance counter stats for './cachetests 111111':
  
      24,079,109      branches                                                    
          39,078      branch-misses             #    0.16% of all branches        
  
     0.027679521 seconds time elapsed
  </code></pre>
  
  <p>What does that line have to do with branch predictions when it's not even an if statement?</p>
  
  <p>The way I see it, in the first <code>ceil(n/2) - 1</code> calls of <code>test1()</code>, both if statements will be false. In the <code>ceil(n/2)-th</code> call, <code>if(curIndex == ceil(n/2))</code> will be true. In the remaining <code>n-ceil(n/2)</code> calls, the first statement will be false, and the second statement will be true.</p>
  
  <p>Why does Intel fail to predict such a simple behavior?</p>
  
  <p>Now let's look at a second case. Suppose that <code>A</code> now has alternating zeros and ones. We will always start from 0. So if <code>n = 9</code> <code>A</code> will look like this:</p>
  
  <p><code>0,1,0,1,0,1,0,1,0</code></p>
  
  <p>The function we are going to use is the following:</p>
  
  <pre><code>void test2(int curIndex){
      //A is 0,1,0,1,0,1,0,1,....
      if(curIndex == size-1) return;
      if(A[curIndex] == 1) return;
  
      test2(curIndex+1);
      test2(curIndex+2);
  
      s += A[curIndex+1] + A[curIndex+2];
  
  }
  </code></pre>
  
  <p>And here is the entire code of the experiment:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;fstream&gt;
  
  using namespace std;
  
  
  int size;
  int *A;
  int s;
  
  void test2(int curIndex){
      //A is 0,1,0,1,0,1,0,1,....
      if(curIndex == size-1) return;
      if(A[curIndex] == 1) return;
  
      test2(curIndex+1);
      test2(curIndex+2);
  
      s += A[curIndex+1] + A[curIndex+2];
  
  }
  
  int main(int argc, char* argv[]){
  
      size = atoi(argv[1]);
      if(argc!=2){
          cout&lt;&lt;"type ./executable size{odd integer}"&lt;&lt;endl;
          return 1;
      }
      if(size%2!=1){
          cout&lt;&lt;"size must be an odd number"&lt;&lt;endl;
          return 1;
      }
      A = new int[size];
      int i;
      for(i=0;i&lt;size;i++){
          if(i%2==0){
              A[i] = false;
          }
          else{
              A[i] = true;
          }
      }
  
      for(i=0;i&lt;100;i++) {
          test2(0);
      }
      cout&lt;&lt;s&lt;&lt;endl;
  
      return 0;
  }
  </code></pre>
  
  <p>I run perf using the same commands as before:</p>
  
  <pre><code>    Performance counter stats for './cachetests2 111111':
  
      28,560,183      branches                                                    
          54,204      branch-misses             #    0.19% of all branches        
  
     0.037134196 seconds time elapsed
  </code></pre>
  
  <p>And removing that line again improved things a little bit:</p>
  
  <pre><code>   Performance counter stats for './cachetests2 111111':
  
      28,419,557      branches                                                    
          16,636      branch-misses             #    0.06% of all branches        
  
     0.009977772 seconds time elapsed
  </code></pre>
  
  <p>Now if we analyse the function, <code>if(curIndex == size-1)</code> will be false <code>n-1</code> times, and <code>if(A[curIndex] == 1)</code> will alternate from true to false.</p>
  
  <p>As I see it, both functions should be easy to predict, however this is not the case for the first function. At the same time I am not sure what is happening with that line and why it plays a role in improving branch behavior.</p>