On Thu, Oct 23, 2008 at 8:13 AM, Antoine Pitrou <span dir="ltr"><<a href="mailto:solipsis@pitrou.net" target="_blank">solipsis@pitrou.net</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Is this kind of optimization that useful on modern CPUs? It helps remove a<br>
memory access to the switch/case lookup table, which should shave off the 3 CPU<br>
cycles of latency of a modern L1 data cache, but it won't remove the branch<br>
misprediction penalty of the indirect jump itself, which is more in the order of<br>
10-20 CPU cycles depending on pipeline depth.</blockquote><div><br>I searched around for information on how threaded code interacts with branch prediction, and here's what I found. The short answer is that threaded code significantly improves branch prediction.<br>
<br>Any bytecode interpreter has some kind of dispatch mechanism that jumps to the next opcode handler. With a while(1) {switch() {} } format, there's one dispatch location in the machine code. Processor branch prediction has a horrible time trying to predict where that dispatch location is going to jump to. Here's some rough psuedo-assembly:<br>
<br>main_loop:<br> compute next_handler<br> jmp next_handler ; abysmal branch prediction<br><br>handler1:<br> ; do stuff<br> jmp main_loop<br><br>handler2:<br> ; do stuff<br> jmp main_loop<br>
<br>With threaded code, every handler ends with its own dispatcher, so the processor can make fine-grained predictions. Since each opcode has its own indirect branch instruction, the processor can track them separately and make better predictions (e.g., it can figure out that opcode X is often followed by opcode Y).<br>
<br>compute next_handler<br>
jmp next_handler ; executed only once<br><br>handler1:<br> ; do stuff<br> compute next_handler<br>
jmp next_handler<br><br>handler2:<br> ; do stuff<br> compute next_handler<br>
jmp next_handler <br></div></div><blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>