4 ms·

Do you know if an optimizing compiler will ever make this transformation?

chc4 8y ago
Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax8]` and the other is `mov edx, [ecx+eax8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.
- vardump 8y ago
  HN formatting ate some * from the parent post: jmp [ecx+eax * 8] and the other is mov edx, [ecx+eax * 8]; jmp edx > The later is faster because of weird branch prediction reasons... Things like that are microarchitecture dependent. Might be true on particular CPUs. Of course it's possible separate MOV could be executed much earlier in the out of order pipeline while JMP effective address calculation might not. So JMP address (edx) would be already resolved by the time JMP is actually executing.
- dawkins 8y ago
  Do you know if the Go compiler does this too? Edit: Nevermind, it doesn't: https://github.com/golang/go/issues/5496 https://github.com/golang/go/issues/5496
- tom_mellior 8y ago
  > Every single C compiler worth mentioning will turn a switch statement into a jump table. Yes, but that is not the optimization discussed here. The optimization discussed here is looking ahead to the next bytecode instruction's opcode, using it as a key into a different jump table, and jumping to that target. No C compiler I'm aware of does that. C compilers could try to match on common patterns in interpreter implementation (a switch within a loop, keyed on certain bits of a piece of data read mostly linearly from an array) and heroically generating a dispatch table, but that would still fail in the cases of branches where you don't want to call DISPATCH because execution does not necessarily proceed to the next instruction in the array.
- ape4 8y ago
  When you are code a `switch` you're telling the compiler what you want. So you get decades of compiler optimization working for you.
- wahern 8y ago
  > Every single C compiler worth mentioning will turn a switch statement into a jump table Only if the case values are small integers with a compact range. But if your opcodes are large and/or sparse (more common in non-VM scenarios) compilers don't optimize switch statements very well. There's a ton of research on switch statement optimization, but most of it doesn't translate to real-world scenarios very well. Compilers will give up fairly quickly on trying to generate a jump table because the work necessary to map the case value to an index at runtime can easily cost more than its worth in many situations. Here's some real-world code which you can easily benchmark and compare: https://github.com/wahern/hexdump/blob/master/hexdump.c#L752 https://github.com/wahern/hexdump/blob/master/hexdump.c#L752 Just flip the VM_FASTER macro. Using `hexdump -C < 64MB.random.file > /dev/null`, on my circa 2012 Mac Mini the switch statement is 80% slower than the computed goto and on my circa 2018 Macbook Pro it's about 15% slower. (See my note elsethread about the post-Haswell branch prediction.) And this is despite the fact that the opcode range is 0-32 without holes! Also, with computed gotos you can remove the jump table altogether. You can make your opcodes actual addresses (just like native code) if you can make the label addresses visible to the code generator. (See my post elsethread for how to make them visible.) P.S. While I implemented hexdump.c using a VM mostly for fun, the end result not only out performs GNU od and BSD hexdump, but IMHO the code is much easier to read, too.
banachtarski 8y ago
Oh psh optimizing compilers go way beyond this. In fact, even hand implemented VMs also generally go further. The technique above is called tail dispatch and is really just the beginning.
- toolslive 8y ago
  indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.
  - tonyjstark 8y ago
    Where can I learn about techniques like that? Any recommendation would be very appreciated!
    - vkazanov 8y ago
      Those techniques are a relatively niche thing. People don't write bytecode interpreters daily. Couple of months ago I wrote a few articles on the topic. Unfortunately, they are in Russian. I'll probably translate 'em at some but for now... the repo and performance measurements are on Github[1]. It includes a couple of dispatch techniques, register caching, etc. [1]: https://github.com/vkazanov/bytecode-interpreters-post https://github.com/vkazanov/bytecode-interpreters-post
    - toolslive 8y ago
      article below contains an overview and more pointers. http://realityforge.org/code/virtual-machines/2011/05/19/interpreters.html http://realityforge.org/code/virtual-machines/2011/05/19/int...
    - tom_mellior 8y ago
      Look up work by Stefan Brunthaler, like this overview paper ("Virtual-Machine Abstraction and Optimization Techniques"): https://www.sba-research.org/wp-content/uploads/publications/bytecode09.pdf https://www.sba-research.org/wp-content/uploads/publications... Make sure to check out the references. I especially like "Ertl, M. A. and D. Gregg, The structure and performance of efficient interpreters, Journal of Instruction-Level Parallelism 5 (2003)"

chc4 8y ago

Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax8]` and the other is `mov edx, [ecx+eax8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.

vardump 8y ago
HN formatting ate some * from the parent post: jmp [ecx+eax * 8] and the other is mov edx, [ecx+eax * 8]; jmp edx > The later is faster because of weird branch prediction reasons... Things like that are microarchitecture dependent. Might be true on particular CPUs. Of course it's possible separate MOV could be executed much earlier in the out of order pipeline while JMP effective address calculation might not. So JMP address (edx) would be already resolved by the time JMP is actually executing.
dawkins 8y ago
Do you know if the Go compiler does this too? Edit: Nevermind, it doesn't: https://github.com/golang/go/issues/5496 https://github.com/golang/go/issues/5496
tom_mellior 8y ago
> Every single C compiler worth mentioning will turn a switch statement into a jump table. Yes, but that is not the optimization discussed here. The optimization discussed here is looking ahead to the next bytecode instruction's opcode, using it as a key into a different jump table, and jumping to that target. No C compiler I'm aware of does that. C compilers could try to match on common patterns in interpreter implementation (a switch within a loop, keyed on certain bits of a piece of data read mostly linearly from an array) and heroically generating a dispatch table, but that would still fail in the cases of branches where you don't want to call DISPATCH because execution does not necessarily proceed to the next instruction in the array.
ape4 8y ago
When you are code a `switch` you're telling the compiler what you want. So you get decades of compiler optimization working for you.
wahern 8y ago
> Every single C compiler worth mentioning will turn a switch statement into a jump table Only if the case values are small integers with a compact range. But if your opcodes are large and/or sparse (more common in non-VM scenarios) compilers don't optimize switch statements very well. There's a ton of research on switch statement optimization, but most of it doesn't translate to real-world scenarios very well. Compilers will give up fairly quickly on trying to generate a jump table because the work necessary to map the case value to an index at runtime can easily cost more than its worth in many situations. Here's some real-world code which you can easily benchmark and compare: https://github.com/wahern/hexdump/blob/master/hexdump.c#L752 https://github.com/wahern/hexdump/blob/master/hexdump.c#L752 Just flip the VM_FASTER macro. Using `hexdump -C < 64MB.random.file > /dev/null`, on my circa 2012 Mac Mini the switch statement is 80% slower than the computed goto and on my circa 2018 Macbook Pro it's about 15% slower. (See my note elsethread about the post-Haswell branch prediction.) And this is despite the fact that the opcode range is 0-32 without holes! Also, with computed gotos you can remove the jump table altogether. You can make your opcodes actual addresses (just like native code) if you can make the label addresses visible to the code generator. (See my post elsethread for how to make them visible.) P.S. While I implemented hexdump.c using a VM mostly for fun, the end result not only out performs GNU od and BSD hexdump, but IMHO the code is much easier to read, too.

banachtarski 8y ago

Oh psh optimizing compilers go way beyond this. In fact, even hand implemented VMs also generally go further. The technique above is called tail dispatch and is really just the beginning.

toolslive 8y ago
indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.
- tonyjstark 8y ago
  Where can I learn about techniques like that? Any recommendation would be very appreciated!
  - vkazanov 8y ago
    Those techniques are a relatively niche thing. People don't write bytecode interpreters daily. Couple of months ago I wrote a few articles on the topic. Unfortunately, they are in Russian. I'll probably translate 'em at some but for now... the repo and performance measurements are on Github[1]. It includes a couple of dispatch techniques, register caching, etc. [1]: https://github.com/vkazanov/bytecode-interpreters-post https://github.com/vkazanov/bytecode-interpreters-post
  - toolslive 8y ago
    article below contains an overview and more pointers. http://realityforge.org/code/virtual-machines/2011/05/19/interpreters.html http://realityforge.org/code/virtual-machines/2011/05/19/int...
  - tom_mellior 8y ago
    Look up work by Stefan Brunthaler, like this overview paper ("Virtual-Machine Abstraction and Optimization Techniques"): https://www.sba-research.org/wp-content/uploads/publications/bytecode09.pdf https://www.sba-research.org/wp-content/uploads/publications... Make sure to check out the references. I especially like "Ertl, M. A. and D. Gregg, The structure and performance of efficient interpreters, Journal of Instruction-Level Parallelism 5 (2003)"