6 ms·

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

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.
- userbinator 13y ago
  In the case that the value you're switching on is a byte, and all 256 values are present in the case (very common for an 8-bit CPU emulator), a switch is a single instruction. You can't get faster/simpler than that.
  - haldean 13y ago
    Not to nitpick, but doesn't it need to be two instructions? You first do a relative jump by the value you're switching on, which takes you to another jump that jumps you to the actual code for that case. I can't think of a way to do it in just one instruction.
    - haberman 13y ago
      Just do an indirect branch, using a table of target pointers. If you had the opcode in eax, the single instruction would be something like: jmp [lookupTable + eax]
      - haldean 13y ago
        Ah, good point. Thanks!

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.

userbinator 13y ago
In the case that the value you're switching on is a byte, and all 256 values are present in the case (very common for an 8-bit CPU emulator), a switch is a single instruction. You can't get faster/simpler than that.
- haldean 13y ago
  Not to nitpick, but doesn't it need to be two instructions? You first do a relative jump by the value you're switching on, which takes you to another jump that jumps you to the actual code for that case. I can't think of a way to do it in just one instruction.
  - haberman 13y ago
    Just do an indirect branch, using a table of target pointers. If you had the opcode in eax, the single instruction would be something like: jmp [lookupTable + eax]
    - haldean 13y ago
      Ah, good point. Thanks!