title: Understanding branch prediction efficiency
body: <p>I tried to measure branch prediction cost, I created a little program.</p>
  
  <p>It creates a little buffer on stack, fills with random 0/1. I can set the size of the buffer with <code>N</code>. The code repeatedly causes branches for the same <code>1&lt;&lt;N</code> random numbers.</p>
  
  <p>Now, I've expected, that if <code>1&lt;&lt;N</code> is sufficiently large (like >100), then the branch predictor will not be effective (as it has to predict >100 random numbers). However, these are the results (on a 5820k machine), as <code>N</code> grows, the program becomes slower:</p>
  
  <pre><code>N   time
  =========
  8   2.2
  9   2.2
  10  2.2
  11  2.2
  12  2.3
  13  4.6
  14  9.5
  15  11.6
  16  12.7
  20  12.9
  </code></pre>
  
  <p>For reference, if buffer is initialized with zeros (use the commented <code>init</code>), time is more-or-less constant, it varies between 1.5-1.7 for <code>N</code> 8..16.</p>
  
  <p>My question is: can branch predictor effective for predicting such a large amount of random numbers? If not, then what's going on here?</p>
  
  <p>(Some more explanation: the code executes 2^32 branches, no matter of <code>N</code>. So I expected, that the code runs the same speed, no matter of <code>N</code>, because the branch cannot be predicted at all. But it seems that if buffer size is less than 4096 (<code>N</code>&lt;=12), something makes the code fast. Can branch prediction be effective for 4096 random numbers?)</p>
  
  <p>Here's the code:</p>
  
  <pre><code>#include &lt;cstdint&gt;
  #include &lt;iostream&gt;
  
  volatile uint64_t init[2] = { 314159165, 27182818 };
  // volatile uint64_t init[2] = { 0, 0 };
  volatile uint64_t one = 1;
  
  uint64_t next(uint64_t s[2]) {
      uint64_t s1 = s[0];
      uint64_t s0 = s[1];
      uint64_t result = s0 + s1;
      s[0] = s0;
      s1 ^= s1 &lt;&lt; 23;
      s[1] = s1 ^ s0 ^ (s1 &gt;&gt; 18) ^ (s0 &gt;&gt; 5);
      return result;
  }
  
  int main() {
      uint64_t s[2];
      s[0] = init[0];
      s[1] = init[1];
  
      uint64_t sum = 0;
  
  #if 1
      const int N = 16;
  
      unsigned char buffer[1&lt;&lt;N];
      for (int i=0; i&lt;1&lt;&lt;N; i++) buffer[i] = next(s)&amp;1;
  
      for (uint64_t i=0; i&lt;uint64_t(1)&lt;&lt;(32-N); i++) {
          for (int j=0; j&lt;1&lt;&lt;N; j++) {
              if (buffer[j]) {
                  sum += one;
              }
          }
      }
  #else
      for (uint64_t i=0; i&lt;uint64_t(1)&lt;&lt;32; i++) {
          if (next(s)&amp;1) {
              sum += one;
          }
      }
  
  #endif
      std::cout&lt;&lt;sum&lt;&lt;"\n";
  }
  </code></pre>
  
  <p>(The code contains a non-buffered version as well, use <code>#if 0</code>. It runs around the same speed as the buffered version with <code>N=16</code>)</p>
  
  <p>Here's the inner loop disassembly (compiled with clang. It generates the same code for all <code>N</code> between 8..16, only the loop count differs. Clang unrolled the loop twice):</p>
  
  <pre><code>  401270:       80 3c 0c 00             cmp    BYTE PTR [rsp+rcx*1],0x0
    401274:       74 07                   je     40127d &lt;main+0xad&gt;
    401276:       48 03 35 e3 2d 00 00    add    rsi,QWORD PTR [rip+0x2de3]        # 404060 &lt;one&gt;
    40127d:       80 7c 0c 01 00          cmp    BYTE PTR [rsp+rcx*1+0x1],0x0
    401282:       74 07                   je     40128b &lt;main+0xbb&gt;
    401284:       48 03 35 d5 2d 00 00    add    rsi,QWORD PTR [rip+0x2dd5]        # 404060 &lt;one&gt;
    40128b:       48 83 c1 02             add    rcx,0x2
    40128f:       48 81 f9 00 00 01 00    cmp    rcx,0x10000
    401296:       75 d8                   jne    401270 &lt;main+0xa0&gt;
  </code></pre>