Blog post: Writing a Game Boy emulator in OCaml

Hi all!

I have written a blog post to share my experience of writing a Game Boy emulator in OCaml.

I will cover things like:

  • Overview of the Game Boy architecture.
  • Using functors to implement testable modules.
  • Using GADTs to encode the Game Boy instruction set.
  • Using test ROMs and ppx_expect to implement the emulator in exploratory programming style.
  • Finding bottlenecks and improving performance.
  • General thoughts on OCaml.

Please take a look if you are interested and/or share with anyone who might be interested.

Also, let me know if you have any questions or comments.

Thanks!

61 Likes

I think the fragment introducing GADTs has a typo: ADD8 of arg * arg even though arg has a type parameter now.

I found the comparison between modules and Java-like OOP especially interesting.

Note that most of your signatures are object-like: you have one type t, it’s only produced in the “constructor”, all “methods” take one t. With these restrictions modules don’t have advantages over objects (or records of closures), and may even carry more syntactic overhead (https://xavierleroy.org/talks/icfp99.ps.gz p.25). Your functors don’t use sharing constraints, so I think you could have as well passed an object (or first-class module or record of functions) as an argument to create, as you said would happen in OOP.

But OOP comes with the cost of dynamic dispatch

I’ve always found it very unclear if OCaml inlines functor applications at compile time (won’t any impurity in functors make such an optimization invalid?). Your program may very well apply functors at runtime and use dynamic dispatch for calling functions from the resulting modules.

2 Likes

Is this a real-time program?
I guess you need to refrain the emulator from going to fast, or the games
won’t be playable.
Also, in case garbage collection is triggered at an unsavory time point,
the game might lag.
Does it happen sometimes?

1 Like

I think the fragment introducing GADTs has a typo

Good find! Fixed.

Note that most of your signatures are object-like
Your functors don’t use sharing constraints, so I think you could have as well passed an object (or first-class module or record of functions) as an argument to create , as you said would happen in OOP.

Yeah, I actually did consider using objects to avoid the syntactical overhead mentioned in the article. My main concern of using objects was not technical but rather social: I thought that using OOP would limit the # of people who can read the code as the OCaml community mostly doesn’t use the OOP aspect of OCaml.

I personally think that there are certain situations where objects make the code a lot simpler. Still, the concerns toward objects are understandable as they have complex runtime semantics that can introduce hard-to-understand code if used incorrectly. Also, constantly picking between classes and modules will add additional mental overhead when writing code, so it is often simpler to use modules without thought.

I’ve always found it very unclear if OCaml inlines functor applications at compile time (won’t any impurity in functors make such an optimization invalid?). Your program may very well apply functors at runtime and use dynamic dispatch for calling functions from the resulting modules.

Interesting… I have actually never thought about the runtime cost of using functors at runtime. I assumed (without much thought) that modules + runtime functor application would have a lower cost than using objects, considering that modules have a much simpler runtime semantics (compared to objects wich have inheritance, overloading, etc.). I will need some more investigation (or input from anyone knowledgeable) on this.

2 Likes

Is this a real-time program?
I guess you need to refrain the emulator from going to fast, or the games
won’t be playable.

Not 100% sure what you mean by “real-time program”, but to answer the latter half of the question: yes, as you pointed out, I did need to throttle the emulator so the emulator runs at a fixed speed, namely 60 FPS/sec.

The way I introduced throttling was different between the SDL2 native frontend and the js_of_ocaml web frontend:

  • For the SDL2 native frontend: I triggered an appropriate amount of Unix.sleep depending on how long it took to render the frame (code)
  • For the js_of_ocaml web frontend: I used the requestAnimationFrame and scheduled the main loop to be called on every repaint, which is 60 times/sec (code)

Also, in case garbage collection is triggered at an unsavory time point,
the game might lag.
Does it happen sometimes?

Actually, the emulator generates very little garbage so GC has never been an issue. It also doesn’t do much IO, so it is a purely CPU-intensive program.

3 Likes

I didn’t necessarily mean “objects” as “OCaml objects”, that’s why I added “records of functions”. Records of functions will be understood by any OCaml programmer, even those who never touched the “O” part. Records of functions are a good replacement for OCaml objects in many cases. Using them instead of modules allows us to stay in the “core” language and not write unwieldy module-level code.

Modules (and first-class modules) are elaborated to records of values early in the compilation stage, so their performance should be similar. OCaml objects are for sure more expensive than records of functions: any method call is done by first finding the method in a map using the hash of its name. On the other hand, this is exactly what allows us to be polymorphic over objects of different shapes in our code, as long as they all have the methods we need.

The distinction I wanted to highlight is between direct and indirect function calls. Direct calls (the procedure is at a statically known location in the program code) are cheaper than indirect calls (the procedure is located at an address contained in a runtime value, plus some offset). Even more, direct calls can be inlined. (I don’t know how to call OCaml object method calls, but they will be even more expensive.)

A call to a function in a static OCaml module (and in an inlined functor application) will be a direct call, a call to an OCaml function contained in a runtime record or a virtual method call in C++ will be (in general) an indirect call.

2 Likes

That’s only true if your screen is at 60hz, nowadays 120hz and 144hz is a very common thing.

That’s only true if your screen is at 60hz, nowadays 120hz and 144hz is a very common thing.

Emulation speed depends on frame rate, so with non-60 Hz throttle there will be a “faster” or “slower” game speed (the original Game Boy framerate is 59.727500569606 Hz).

Btw, anyone who tries to play on a mobile phone (Android) and got low fps, try Firefox instead of Chrome. I trying to play “Rocket Man Demo” on my mobile phone, so I got ~23 fps (and slow emulation) in Google Chrome and ~44 fps (and playable emulation) in Firefox Nightly.

1 Like

This is an awesome project and a great write up! Thanks for sharing and congrats on the successful project :tada: :camel:

2 Likes

I see. The “records of functions” approach seems like a reasonable approach, but I will need to try it out to see if it looks OK in terms of readability.

Ah, I remember reading somewhere that modules are compiled to records, and functors are compiled to functions that take a record and return a record. I now understand what you meant by “I’ve always found it very unclear if OCaml inlines functor applications at compile time”.

I see, makes sense. “indirect” seems to be a better term than “dynamic dispatch”.

True. I should probably think of some way to achieve consistent 60hz, especially since non-60hz might become more common in the future. Another item on my TODO list :slight_smile:

I was reading it the other day. Dope article, thank you!

1 Like

Very interesting. Thanks for the writing and sharing.

1 Like