Apple II emulators are so much fun. I've written or significantly worked on at least four that I can think of (one of them in Python is at https://github.com/jtauber/applepy). They're great because the 6502 is a nice simple CPU to emulate, and the whole machine is small enough to keep in your head all at once.
As a kid I remember spreading out the Apple II motherboard circuit diagram (part of the machine reference manual) on the floor and studying it. Good times.
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.
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.
> 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.
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.
> 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.
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.
> 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.
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. ;-)
As a kid I remember spreading out the Apple II motherboard circuit diagram (part of the machine reference manual) on the floor and studying it. Good times.