4 ms·

Is this true? I don't know anything about writing interpreters, but wouldn't function pointers work?

by vanjoe 9y ago

haldean 9y ago
You can kind of do it with function pointers, with the caveat that a jump table of function pointers is still going to have the cost of a function call. What you can't do is something equivalent to: sta $1 jmp ($1) which just moves the PC forward by the offset stored in a register (I only know 6502 assembly, sorry everyone). There's no function call here, it's a goto where you calculate what label to go to at runtime. The closest C equivalent would be a switch/case; switch/case has the relative disadvantage that you have to make an explicit label to be targeted for each one, and it becomes difficult to express anything other than "the thing I'm jumping to is parameterized by only this one integer".
KMag 9y ago
One call/return pair, plus the increased chance of a cache miss, makes the overhead of a function dispatch for each and every opcode rather high, unless your opcodes are very complex and do a lot of work before returning to your opcode dispatch loop. The normal computed goto dispatch puts a goto opcode_table[*(++ip)]; at the end of each case statement. This essentially inlines a copy of the switch(*(++ip)) into each opcode case. This saves one branch instruction, but more importantly, it really helps the branch predictor by giving each opcode its own copy of the code for dispatching the next opcode. So, if 90% of the time your compare opcode is followed by a jump_less_than opcode, the CPU will prefetch and start speculatively executing the conditional jump before the interpreter is done with the compare opcode. In C, if you don't use non-portable computed goto, generally the best you can do for opcode dispatch is using a big switch statement. In theory, C compiler writers could write some pretty accurate heuristics (loop containing only a switch statement switching on an indirection indexed by a constant incriment) and detect interpreter bytecode dispatch inner loops. It wouldn't be too difficult to implement an optimization that results in the same instruction sequence as the computed goto dispatch. However, it would be too brittle for any interpreter writer to rely on the compiler performing the optimization, so most would continue to use computed goto.

Is this true? I don't know anything about writing interpreters, but wouldn't function pointers work?

by vanjoe 9y ago

Is this true? I don't know anything about writing interpreters, but wouldn't function pointers work?

You can kind of do it with function pointers, with the caveat that a jump table of function pointers is still going to have the cost of a function call. What you can't do is something equivalent to: sta $1 jmp ($1) which just moves the PC forward by the offset stored in a register (I only know 6502 assembly, sorry everyone). There's no function call here, it's a goto where you calculate what label to go to at runtime. The closest C equivalent would be a switch/case; switch/case has the relative disadvantage that you have to make an explicit label to be targeted for each one, and it becomes difficult to express anything other than "the thing I'm jumping to is parameterized by only this one integer".

KMag 9y ago

One call/return pair, plus the increased chance of a cache miss, makes the overhead of a function dispatch for each and every opcode rather high, unless your opcodes are very complex and do a lot of work before returning to your opcode dispatch loop. The normal computed goto dispatch puts a goto opcode_table[*(++ip)]; at the end of each case statement. This essentially inlines a copy of the switch(*(++ip)) into each opcode case. This saves one branch instruction, but more importantly, it really helps the branch predictor by giving each opcode its own copy of the code for dispatching the next opcode. So, if 90% of the time your compare opcode is followed by a jump_less_than opcode, the CPU will prefetch and start speculatively executing the conditional jump before the interpreter is done with the compare opcode. In C, if you don't use non-portable computed goto, generally the best you can do for opcode dispatch is using a big switch statement. In theory, C compiler writers could write some pretty accurate heuristics (loop containing only a switch statement switching on an indirection indexed by a constant incriment) and detect interpreter bytecode dispatch inner loops. It wouldn't be too difficult to implement an optimization that results in the same instruction sequence as the computed goto dispatch. However, it would be too brittle for any interpreter writer to rely on the compiler performing the optimization, so most would continue to use computed goto.