4 ms·

I had a look at the 6502 implementation. For each instruction it grabs the first (and maybe only) byte of the instruction. Surprisingly, it uses a binary tree o

I had a look at the 6502 implementation. For each instruction it grabs the first (and maybe only) byte of the instruction. Surprisingly, it uses a binary tree of if / else decoding to narrow it down to one case and then execute that instruction. Python doesn't have a case statement (which would be the natural way to do something like this in most languages) but I would have expected a dict function lookup would have been faster than the binary tree of if/else decisions.

staplung 3y ago
Python doesn't have a case statement but (as of 3.10) it does have match. The apparent problem with using either of those is that you'd potentially have to evaluate many, many if statements (or match clauses) in the worst case whereas with the hand-made binary tree you'll only have to do 8 checks. Having said that, I too wonder why they didn't use a dictionary. ;-)
joneholland 3y ago
The 6502 has variable length encoding, each opcode is associated with a half dozen addressing modes that determine what to do with the following bytes. In my implementation I usually store a dictionary entry with two function pointers. One for the opcode itself, and one for the addressing mode. Call the address mode to configure state correctly, then call the opcode to actually perform the work. This is a lot cleaner than nested ifs.
deaddodo 3y ago
> but I would have expected a dict function lookup would have been faster than the binary tree of if/else decisions. This would just be an O(n) worst-case operation, the same as a non-optimized switch statement. In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table, but not in Python. Same goes for an exhaustive and non-fallthrough switch statement. Using a binary search tree (what this essentially is a flattened version of) halves the worst case. For 8-bit CPUs, the more common paradigm is to use a giant switch statement and just order the OPs by frequency. You get the same Worst-Case, but a much better Average-Case.
- junon 3y ago
  What about python arrays? Been a while since I poked around python internals but surely lookups in a list isn't worst case O(n), no?
- flohofwoe 3y ago
  In C and C++ a continuous switch-case will be turned into a simple jump table though, which turns the "opcode decoding" into a single indirect branch instruction (or something similar on esoteric ISAs like WASM). The jump table transform happens at least on gcc, msvc and llvm based compilers. Also, at least llvm is also clever enough to build a mix of binary search and jump tables for "sparse" switch case statements.
  - deaddodo 3y ago
    Which is what I said, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement. I have no doubt that non-exhaustive (sparse) switch statements can also be optimized in compilers today; the more important portion is the non-fallthrough aspect.
- tasty_freeze 3y ago
  Python uses some kind of hash, so worst case O(n) would be very unlikely. And rereading what I wrote, I don't know why I said dict -- an array would be just fine. For most languages, a dense case statement is implemented via a jump table, a fast, constant time operation.
  - deaddodo 3y ago
    I said that, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement.

staplung 3y ago

Python doesn't have a case statement but (as of 3.10) it does have match. The apparent problem with using either of those is that you'd potentially have to evaluate many, many if statements (or match clauses) in the worst case whereas with the hand-made binary tree you'll only have to do 8 checks. Having said that, I too wonder why they didn't use a dictionary. ;-)

joneholland 3y ago

The 6502 has variable length encoding, each opcode is associated with a half dozen addressing modes that determine what to do with the following bytes. In my implementation I usually store a dictionary entry with two function pointers. One for the opcode itself, and one for the addressing mode. Call the address mode to configure state correctly, then call the opcode to actually perform the work. This is a lot cleaner than nested ifs.

deaddodo 3y ago

> but I would have expected a dict function lookup would have been faster than the binary tree of if/else decisions. This would just be an O(n) worst-case operation, the same as a non-optimized switch statement. In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table, but not in Python. Same goes for an exhaustive and non-fallthrough switch statement. Using a binary search tree (what this essentially is a flattened version of) halves the worst case. For 8-bit CPUs, the more common paradigm is to use a giant switch statement and just order the OPs by frequency. You get the same Worst-Case, but a much better Average-Case.

junon 3y ago
What about python arrays? Been a while since I poked around python internals but surely lookups in a list isn't worst case O(n), no?
flohofwoe 3y ago
In C and C++ a continuous switch-case will be turned into a simple jump table though, which turns the "opcode decoding" into a single indirect branch instruction (or something similar on esoteric ISAs like WASM). The jump table transform happens at least on gcc, msvc and llvm based compilers. Also, at least llvm is also clever enough to build a mix of binary search and jump tables for "sparse" switch case statements.
- deaddodo 3y ago
  Which is what I said, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement. I have no doubt that non-exhaustive (sparse) switch statements can also be optimized in compilers today; the more important portion is the non-fallthrough aspect.
tasty_freeze 3y ago
Python uses some kind of hash, so worst case O(n) would be very unlikely. And rereading what I wrote, I don't know why I said dict -- an array would be just fine. For most languages, a dense case statement is implemented via a jump table, a fast, constant time operation.
- deaddodo 3y ago
  I said that, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement.