NES Emulator: Existentials Crisis

TL;DR: don’t use existentials where generics will do. Avoid existentials if at all possible in performance-critical code paths.

The North American NES is locked to 60 FPS. During each CPU tick, the PPU ticks three times, which means that if your emulator is too slow, not only will the frame rate suffer, but the entire game runs slower. This is in contrast to modern games, where elapsed time is the central control mechanism, not the FPS or number of clock ticks.

All this to say: emulator’s gotta run fast, or else everything falls apart.

It probably shouldn’t have surprised me that the slowest thing in my emulator is memory access. But it’s just a 64kb address space, most of which is memory – how complicated could it be? There’s a bit more complexity: memory accesses are intermediated by a bus that determines which device services each access, and the cartridge is always given the opportunity to service a request even when it would normally go somewhere else. Pretty straightforward. The problem is: even when lots of data is being fetched, it happens one byte at a time, which means bus.read() gets called hundreds of thousands of times per second. It had better be fast!

My first approach was the Swiftiest: define a reusable Bus class that manages a list of entries, each of which contains a device conforming to Addressable, the starting address, and addressable length. A device might be a block of RAM or some memory mapped thing like PPU registers or game controllers. When a read or write happens on the bus, it searches for the right entry and calls its device’s read() or write() method.

Since there’s an array containing entries, and each entry’s device can be a different type conforming to Addressable, we have to use existentials. To oversimplify a bit, an existential (spelled var thing: any SomeProtocol in Swift) is a little type-erased box that can hold anything conforming to a given protocol. The benefit is that it’s super convenient and allows us to express things like heterogeneous arrays (or in our case, an array of things containing heterogeneous types). The downside is performance: since the concrete type of a value can’t be known at compile time, method calls on existentials must be dynamically dispatched. Which happens hundreds of thousands of times per second. Slow!

The solution is easy, but not as nice. I now have separate MainBus and PPUBus types which almost exclusively hold references to concrete types conforming to Addressable, and I’ve hardcoded the logic to read or write to each device based on their locations within the address space.

I got a huge performance win out of this!

Which reminded me: I was using existentials all over the place where generics would suffice. When there are no other downsides, you should always use generics instead of existentials. In many cases they do the exact same thing, but the concrete types are known at compile time and dynamic dispatch is avoided. Whew! It was an easy, mechanical fix.

Lastly, there’s still the question of the cartridge being able to step in to handle any memory read or write. That means each bus needs to hold a reference to the cartridge. Since there are hundreds of types of cartridges (although most games use one of a select few), that means I still need to use an existential (var cartridge: any Cartridge) in the buses! I could make the buses generic over the cartridge type (class MainBus<C: Cartridge> {}) but then each type that holds a reference to the buses would have to use an existential, or themselves be generic over the cartridge type. I did actually go down this rabbit hole briefly, before deciding it was making my code too ugly and annoying.

There are certainly ways to solve this last issue of the cartridge being an existential, but as of right now performance is acceptable, hitting 60 FPS on my test devices. I still have the APU to write, though, so I may have to address it later. We shall see!