4 ms·

I suppose you could create a dictionary of opcode -> function pointers. In C# that'd be like var ops = new Dictionary<Opcode, Action<opcodeArgs>> () {

I suppose you could create a dictionary of opcode -> function pointers. In C# that'd be like var ops = new Dictionary<Opcode, Action<opcodeArgs>> () { {0, nop }, {1, add }, ... } or even better, maybe I'd get a list of the opcodes with their names, name all the functions after those names exactly, then use reflection to automatically create this dictionary. Then in the main loop, ops[opcode].Invoke(args); I don't know if something like that would be any use in C, though.

grapeshot 13y ago
It's possible to do something like that in C. In C++, you can even do some template magic to create all the appropriate functions for each opcode based on something like the original instruction decode ROM. Brilliant and short code, but very difficult to write in the first place. Here's a very apropos example of this technique as applied to the 6502. http://www.youtube.com/watch?v=y71lli8MS8s http://www.youtube.com/watch?v=y71lli8MS8s
haldean 13y ago
The problem with that method is that it's inefficient; with the switch statement, there's no hashing or significant computation involved in finding the location to jump to. With an object-based method, you have (at least) a memory access to get the method object, a lookup in a vtable to find the location of the Invoke method and a function call (which means pushing a new stack frame) before you start processing the instruction. With the switch statement, none of that happens; instead, it compiles to (essentially) two jump instructions; one into a lookup table, then one from the lookup table to the opcode handler. Getting out of the handler and back into the loop is also a single constant jump (no stack frame popping).
- jimmaswell 13y ago
  These are mostly O(1) things and shouldn't matter. The dictionary lookup can become O(1) if you turn it into an array of function pointers indexed by ints, the opcodes.
  - breckinloggins 13y ago
    But remember that O(n) is really c*n. The problem is that, when emulating a CPU, the "c" can dominate in these cases.
  - haldean 13y ago
    Yup, that's definitely true, but opcode parsing and dispatch needs to be a really tight loop. Keep in mind that function calls still involve pushing/popping stack frames, which while super, super cheap, are still not free. There are no loops other than the main loop in here, and every instruction takes constant time, which means that constant factors in opcode parsing and dispatch are going to really dominate.
  - haberman 13y ago
    In these kinds of situations, O(1) means nothing; any (reasonable) approach will be O(1), but constant factors will dominate. For example, there are measurable differences in branch prediction based on whether each opcode's implementation ends with its own dispatch code or branches back to a common dispatch routine. The sequence of instructions is basically the same in both cases, but there is an icache/branch prediction tradeoff to be made. Subtle stuff (see http://repo.or.cz/w/luajit-2.0.git/blob/0ded8e82a88fadb40b4dd7e6632311781f1b2f91:/src/vm_x86.dasc#l283 http://repo.or.cz/w/luajit-2.0.git/blob/0ded8e82a88fadb40b4d...)
  - weland 13y ago
    > These are mostly O(1) things and shouldn't matter. I often hear this from programmers coming from a higher-level background. O(1) only means constant time. It doesn't mean quickly. This function: int foo(int x) { sleep(3600); return x; } is O(1), just as this: int bar(int x) { return x; } Foo takes an hour to commplete, but it's just as O(1) as bar :-).
  - csmuk 13y ago
    No dictionaries are O(1). Even if they were they are pitifully slow compared to a switch. Consider chaining and the fact that you have to compute hashes. switch is O(1) and fast as the operation is usually 2-3 deterministic time instructions: 1. Look up jump address from lookup table made by compiler. 2. Jump to it. More people need to have written assembly to actually get this into their heads.
- Keyframe 13y ago
  What are the common alternatives to avoid function calls when you want to wrap them? For example you want to wrap an adding function in order to have several cases for it (different architectures for example) but you also want to avoid wrapping it in a function call either via function pointer or switch to invoke different functions.
  - haldean 13y ago
    Macros can satisfy that in simple cases (like the NEXT_BYTE macro in x6502), and inline functions (like set_flags, get_flag, mem_abs, etc.) can handle more complex cases. Both of these result in the code in the contents of the "function" being directly inserted into the calling block. (For inline functions, that's only true if you turn on optimizations, but I think even O1 on any C99 compiler turns on inlining). In general, if I need something to avoid function calls, I'll use macros as a shorthand for a complex expression (like NEXT_BYTE) and inline functions for anything that involves one or more full statements (like set_flags). Obviously I don't follow that too dogmatically, because mem_abs is an inline function.
haberman 13y ago
Yes you could do that. But why go to such contortions when "switch" is an idiomatic and efficient way of expressing this pattern directly?

grapeshot 13y ago

It's possible to do something like that in C. In C++, you can even do some template magic to create all the appropriate functions for each opcode based on something like the original instruction decode ROM. Brilliant and short code, but very difficult to write in the first place. Here's a very apropos example of this technique as applied to the 6502. http://www.youtube.com/watch?v=y71lli8MS8s http://www.youtube.com/watch?v=y71lli8MS8s

haldean 13y ago

The problem with that method is that it's inefficient; with the switch statement, there's no hashing or significant computation involved in finding the location to jump to. With an object-based method, you have (at least) a memory access to get the method object, a lookup in a vtable to find the location of the Invoke method and a function call (which means pushing a new stack frame) before you start processing the instruction. With the switch statement, none of that happens; instead, it compiles to (essentially) two jump instructions; one into a lookup table, then one from the lookup table to the opcode handler. Getting out of the handler and back into the loop is also a single constant jump (no stack frame popping).

jimmaswell 13y ago
These are mostly O(1) things and shouldn't matter. The dictionary lookup can become O(1) if you turn it into an array of function pointers indexed by ints, the opcodes.
- breckinloggins 13y ago
  But remember that O(n) is really c*n. The problem is that, when emulating a CPU, the "c" can dominate in these cases.
- haldean 13y ago
  Yup, that's definitely true, but opcode parsing and dispatch needs to be a really tight loop. Keep in mind that function calls still involve pushing/popping stack frames, which while super, super cheap, are still not free. There are no loops other than the main loop in here, and every instruction takes constant time, which means that constant factors in opcode parsing and dispatch are going to really dominate.
- haberman 13y ago
  In these kinds of situations, O(1) means nothing; any (reasonable) approach will be O(1), but constant factors will dominate. For example, there are measurable differences in branch prediction based on whether each opcode's implementation ends with its own dispatch code or branches back to a common dispatch routine. The sequence of instructions is basically the same in both cases, but there is an icache/branch prediction tradeoff to be made. Subtle stuff (see http://repo.or.cz/w/luajit-2.0.git/blob/0ded8e82a88fadb40b4dd7e6632311781f1b2f91:/src/vm_x86.dasc#l283 http://repo.or.cz/w/luajit-2.0.git/blob/0ded8e82a88fadb40b4d...)
- weland 13y ago
  > These are mostly O(1) things and shouldn't matter. I often hear this from programmers coming from a higher-level background. O(1) only means constant time. It doesn't mean quickly. This function: int foo(int x) { sleep(3600); return x; } is O(1), just as this: int bar(int x) { return x; } Foo takes an hour to commplete, but it's just as O(1) as bar :-).
- csmuk 13y ago
  No dictionaries are O(1). Even if they were they are pitifully slow compared to a switch. Consider chaining and the fact that you have to compute hashes. switch is O(1) and fast as the operation is usually 2-3 deterministic time instructions: 1. Look up jump address from lookup table made by compiler. 2. Jump to it. More people need to have written assembly to actually get this into their heads.
Keyframe 13y ago
What are the common alternatives to avoid function calls when you want to wrap them? For example you want to wrap an adding function in order to have several cases for it (different architectures for example) but you also want to avoid wrapping it in a function call either via function pointer or switch to invoke different functions.
- haldean 13y ago
  Macros can satisfy that in simple cases (like the NEXT_BYTE macro in x6502), and inline functions (like set_flags, get_flag, mem_abs, etc.) can handle more complex cases. Both of these result in the code in the contents of the "function" being directly inserted into the calling block. (For inline functions, that's only true if you turn on optimizations, but I think even O1 on any C99 compiler turns on inlining). In general, if I need something to avoid function calls, I'll use macros as a shorthand for a complex expression (like NEXT_BYTE) and inline functions for anything that involves one or more full statements (like set_flags). Obviously I don't follow that too dogmatically, because mem_abs is an inline function.

haberman 13y ago

Yes you could do that. But why go to such contortions when "switch" is an idiomatic and efficient way of expressing this pattern directly?