title: Slow jmp-instruction
body: <p>As follow up to my question <a href="https://stackoverflow.com/questions/38303333">The advantages of using 32bit registers/instructions in x86-64</a>, I started to measure the costs  of instructions. I'm aware that this have been done multiple times (e.g. <a href="http://www.agner.org/optimize/" rel="noreferrer">Agner Fog</a>), but I'm doing it for fun and self education.</p>
  
  <p>My testing code is pretty simple (for simplicity here as  pseudo code, in reality in assembler):</p>
  
  <pre><code>for(outer_loop=0; outer_loop&lt;NO;outer_loop++){
      operation  #first
      operation  #second
      ...
      operation #NI-th
  } 
  </code></pre>
  
  <p>But yet some things should be considered.</p>
  
  <ol>
  <li>If the inner part of the loop is large (large <code>NI&gt;10^7</code>), the whole content of the loop does not fit into the instruction cache and thus must be loaded over and over again, making the speed of RAM define the time needed for execution. For example, for large inner parts, <code>xorl %eax, %eax</code> (2 bytes) is 33% faster than <code>xorq %rax, %rax</code> (3 bytes).</li>
  <li>If <code>NI</code> is small and the whole loop fits easily into the instruction cache, than <code>xorl %eax, %eax</code> and <code>xorq %rax, %rax</code> are equally fast and can be executed 4 times per clock cycle.</li>
  </ol>
  
  <p>However this simple model does not hold water for the <code>jmp</code>-instruction. For the <code>jmp</code>-instruction my test code looks as follows:</p>
  
  <pre><code>for(outer_loop=0; outer_loop&lt;NO;outer_loop++){
      jmp .L0
      .L0: jmp .L1
      L1: jmp L2
      ....
  }
  </code></pre>
  
  <p>And the results are:</p>
  
  <ol>
  <li>For "large" loop sizes (already for <code>NI&gt;10^4</code>) I measure 4.2 ns/<code>jmp</code>-instruction ( would equate to 42 bytes loaded from RAM or ca. 12 clock cycles on my machine).</li>
  <li>For small loop sizes (<code>NI&lt;10^3</code>) I measure 1 ns/<code>jmp-</code>instruction (which is around 3 clock cycles, which sounds plausible - Agner Fog's tables shows costs of 2 clock cycles).</li>
  </ol>
  
  <p>The instruction <code>jmp LX</code> uses the 2 byte <code>eb 00</code> encoding.</p>
  
  <p><strong>Thus, my question:</strong> What could be the explanation for the high cost of <code>jmp</code>-instruction in the "large" loops?</p>
  
  <p><em>PS:</em> If you like to try it out on your machine, you can download the scripts from <a href="https://github.com/realead/asmeter" rel="noreferrer">here</a>, just run <code>sh jmp_test.sh</code> in <em>src</em>-folder.</p>
  
  <hr>
  
  <p><strong>Edit:</strong> Experimental results confirming Peter's BTB size theory.</p>
  
  <p>The following table shows cycles per instruction for different <code>ǸI</code> values (relative to <code>NI</code>=1000):</p>
  
  <pre><code>|oprations/ NI        | 1000 |  2000|  3000|  4000|  5000| 10000|
  |---------------------|------|------|------|------|------|------|
  |jmp                  |  1.0 |  1.0 |  1.0 |  1.2 |  1.9 |   3.8|
  |jmp+xor              |  1.0 |  1.2 |  1.3 |  1.6 |  2.8 |   5.3|
  |jmp+cmp+je (jump)    |  1.0 |  1.5 |  4.0 |  4.4 |  5.5 |   5.5|
  |jmp+cmp+je (no jump) |  1.0 |  1.2 |  1.3 |  1.5 |  3.8 |   7.6|
  </code></pre>
  
  <p>It can be seen:</p>
  
  <ol>
  <li>For the <code>jmp</code> instruction, a (yet unknown) resource becomes scarce and this leads to a performance degradation for <code>ǸI</code> larger than 4000.</li>
  <li>This resource is not shared with such instructions as <code>xor</code> - the performance degradation kicks in still for <code>NI</code> about 4000, if <code>jmp</code> and  <code>xor</code> are executed after each other.</li>
  <li>But this resource is shared with <code>je</code> if the jump is made - for <code>jmp</code>+<code>je</code> after each other, the resource becomes scarce for <code>NI</code> about 2000.</li>
  <li>However, if <code>je</code> does not jump at all, the resource is becoming scarce once again for <code>NI</code> being about 4000 (4th line).</li>
  </ol>
  
  <p><a href="http://xania.org/201602/haswell-and-ivy-btb" rel="noreferrer">Matt Godbolt's branch-prediction reverse engineering articles</a> establishes that the branch target buffer capacity is 4096 entries.  That is very strong evidence that BTB misses are the reason for the observed throughput difference between small and large <code>jmp</code> loops.</p>