One "cheap" performance boost you could probably get is replacing your HashMaps with FxHashMap, https://docs.rs/fxhash/latest/fxhash/, which uses a much cheaper/faster, but also not cryptographically secure, hashing algorithm. For these purposes, I doubt the hashing algorithm weakness would be an issue.
HashMap uses SipHash. To call it cryptographically secure is not a clear way of summarizing what it provides. See Wikipedia for more info. Blurb:
> It was designed to be efficient even for short inputs, with performance comparable to non-cryptographic hash functions, such as CityHash, this can be used to prevent denial-of-service attacks against hash tables ("hash flooding") [...]
I believe rust’s hashmap does have an implementation that is immune to timing-based attacks and that does have a performance cost. Maybe that’s what parent mixed it up with.
I was trying to use the specific phrasing the fxhash crate authors used, but screwed it up. Brain was half asleep when I wrote my comment, I think.
> It is not a cryptographically secure hash, so it is strongly recommended that you do not use this hash for cryptographic purproses. Furthermore, this hashing algorithm was not designed to prevent any attacks for determining collisions which could be used to potentially cause quadratic behavior in HashMaps. So it is not recommended to expose this hash in places where collissions or DDOS attacks may be a concern.
I am already using a non-cryptographic hasher. In fact, I am not doing any hashing at all, I am just assuming that the input is already random enough, and use a Hasher that just copies the input to output. But I still didn't measure the performance of that, so that may be something silly to do.
Sorry, in the blog post you were talking about the HashMap being expensive, and I didn't spot one of the usual "cheap" hashing libraries being in use. That's where I got wondering if you'd missed an easy boost.
Very nice! I've been working on a Dreamcast emulator for a long time and a lot of the issues you mentioned around deterministic behavior echoed. Schedulers are fantastic, and we landed on the same concept.
You mentioned that you do a hash map look for each (bank,addr) key. Suggestion which helped us: have this point to an Netey which contains the JIT code but also an index/pointer into the next block which executed last time you executed this block. You can do a simple check to see if this is still valid and fall back to the hashmap lookup. If you're careful about code invalidation (not an issue with ROM) then this can help skip the next lookup.
I've thought of doing one of these for my favourite 8-bit computer, though never actually got round to actually trying it.
How wide is a bank number? Even if it's the full 8 bits, that's only 24 bits, which is nothing these days. 64 MB for the full table, assuming 32 bits is enough to cover every offset into the JIT buffer. (Assuming max 4 GB of JIT'd code. If that isn't, perhaps 40 bits would be? 128 MB table, max 1 TByte of JIT'd code.) Would you need a hash table rather than an array?
The maximum supported size is 512 banks, so 25 bits. But searching now, I don't think there are any games bigger than 1 MiB in size (64 banks), so 22 bits, or just 16 MiB or 32 MiB of lookup table. Yeah, maybe it is not so bad to replace the HashMap with an array, especially when I am losing a significant amount of time doing HashMap look ups already.
But of course I would like to avoid using that amount of memory if possible. Maybe I will also take a look at perfect hash mapping someday.
Fascinating read. In the past few months I started work on a Game Boy emulator in Swift, and although it’s still very early days (got the boot ROM logo displaying but not much else) it’s been a very fun and rewarding project.
A JIT is something I’d been wondering about for a bit, and this post was eye-opening about the complexities involved (I have no real compiler background).
It looks simple & short, but on the other hand I've checked the repo and it has 1k commits, so probably not THAT simple
I have some small, 4fun experience with compilers and I do wonder - how people start with game emulators? what are the basic concepts? what is the easiest hello-world game to start w/?
The typical hello world is actually a CHIP 8 emulator, which is a type of VM that ran on an old calculator, the specifics of which elude me. It's got a tiny memory space, simple instructions and a handful of features, so it's the sort of thing you can get up and "running" with minimal effort. It lets you explore the high level concepts involved in running a "guest" system on some hosts, and tickles the challenge of synchronizing the timing and dealing with video and sound, without being overwhelming the way a physical console can be.
"Calculator" doesn't quite cover it. CHIP-8 was developed to run on the COSMAC VIP home computer, and later similar ones like the Telmac 1800, which were shipped as kits for users to build at home.
I had some Computer Organization and Architecture classes in university, and a previously-existing burning desire to understand emulation. I decided that the NES would be a good target; it was the oldest game hardware that I had personal interest in. In 2008, I found as much info as I could about how to structure an emulator, and technical documents about the NES, and started building. I got something basic working in a couple months, and came back to it every couple of years, either to add functionality or experiment with optimizations.
> what are the basic concepts?
A CPU goes through a repeating fetch->decode->execute loop, and mostly communicates with the rest of the system over a "bus", which has some number of address lines (in the NES, 16 address lines provide access to 2^16 or 65,536 addresses), some number of data lines (in the NES, 8 lines for 8-bit values), and some number of control lines (read/write, ready, and others that vary system-to-system). Different devices are connected at different address ranges. They could be RAM, ROM, I/O hardware, etc. So when a CPU is booting, the system is usually designed to expose some ROM at the first address the CPU fetches from.
> what is the easiest hello-world game to start w/?
Chip-8, probably. Space Invaders is a good one too; simple, but using a CPU related to those in a lot of other systems, and a bit less of a toy-scale system than Chip-8.
> How come you don't consider conditional branches to be terminating instructions of your basic blocks?
Initially I was doing that, but it was making tight loops too slow. And what I am referring to as a "block" was not a basic block, but a entire compilation unit.
