title: How can you optimize jump instruction slowed by cpu branch miss?
body: <h1>Background</h1>
  
  <p>It is known that random branching costs significant overhead.
  <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">And there was a post in SO answering such question.</a></p>
  
  <p>Similar performance impact can be seen with jump instructions in many CPU architectures. <a href="https://stackoverflow.com/questions/7241922/how-has-cpu-architecture-evolution-affected-virtual-function-call-performance">And there was a post in SO for such theme as well</a></p>
  
  <p>So if you used programming patterns like function pointer or just normal inheritable C++ class based function call, we have to pay the cost of branch miss.</p>
  
  <p>Even for the most advanced hardware branch prediction algorithms can only do globally shared address history based branch prediction, and perhaps it may speculatively fetch the branch target address code and so on.</p>
  
  <p>But by definition, it won't work for the first execution.  </p>
  
  <p>Many embedded appliance, smartphones, etc should demand maximum performance at  </p>
  
  <ul>
  <li>boot time</li>
  <li>first execution of an application like browser</li>
  </ul>
  
  <p>Which calls millions of function calls and may not want to change there software architecture significantly like converting all indirect jumps into direct jumps...</p>
  
  <p>If the conditions are as follows,</p>
  
  <h1>Conditions:</h1>
  
  <ul>
  <li>must run at top speed
  
  <ul>
  <li>at the first run<br>
  or</li>
  <li>the jump looks completely random to the cpu</li>
  </ul></li>
  </ul>
  
  <p>Is the following best to achieve the result?  </p>
  
  <p>And I want to know any example that does dynamic/static code rewrite of indirect to direct jumps.  </p>
  
  <h1>How to get maximum performance:</h1>
  
  <ul>
  <li>always use either branch likely or unlikely</li>
  <li>use prelink</li>
  <li>use mlock or readahead, cacheflush(ICACHE) the function call</li>
  <li>rewrite indirect jumps to direct jumps dynamically or statically<br>
  (<a href="http://dl.acm.org/citation.cfm?id=331419" rel="nofollow noreferrer">found a paper written in 1996 by Bradley M Kuhn</a> for static rewrite for some case)</li>
  </ul>
  
  <p>The paper I found was translating virtual function calls to static function call at source code level, but binary link time optimization seemed better for the software developer point of view.  </p>