Fergulator - NES emulator, written in Go | Hacker News Reader

Fergulator - NES emulator, written in Go

plus.google.com

85 pointsbconway31 comments

I found Go to be really productive for expressing machine emulators; the language is deliberately amenable to working with ints at bit level, the packaging system is effective and mostly stays out of the way, it has a flexible "switch", there's just enough abstraction so that it's easy to swap different components (memories, etc) in and out, and, of course, once you start running the things, goroutines make it easy to step machines as coroutines.

With regards to the switch statement, I've read on stackoverflow[1] that function tables actually outperform switch statements when there's several cases. So I tend to avoid switches for performance critical routines.

It will be interesting to see how 1.1 performs in relation to this.

[1] http://stackoverflow.com/questions/9928221/table-of-function...

This is pretty strange if it's true; shouldn't a switch (especially one that simple) compile into a jump table? Otherwise what's the point? Does Go just linearly search through case conditions in a switch?

EDIT: Missed the link: https://groups.google.com/forum/#!msg/golang-nuts/IURR4Z2SY7...

Seems like a reasonable argument, but then again I don't see why they even bothered adding a switch given those constraints.

There is a general form to switch statements in Go that really is syntactic sugar over if/else chains.

I get that serious emulators invest effort in making dispatch fast, and that a naive for/switch loop is not the fastest way to dispatch instructions, but it's nice for getting the emulator working. :)

> I get that serious emulators invest effort in making dispatch fast, and that a naive for/switch loop is not the fastest way to dispatch instructions

If you're the kind of masochist that enjoys optimizing dispatch loops (hi, you're not alone), check this out: http://www.emulators.com/docs/nx25_nostradamus.htm One of the best resources out there for this sort of stuff.

Thanks, I hadn't seen that before. My go-to point for all this stuff has always been the papers by Ertl and others http://www.complang.tuwien.ac.at/forth/threaded-code.html

I think the Go compiler handles switches a little more like a series of "if else" (In fact I think a few languages do that) but Go supports first class functions, you can map things somewhat differently using that.

Ken Thompson does go into more detail in a link off the SO question I posted earlier.

[edit: i see you've already spotted that link. Sorry about that]

Dispatching a table of functions should have roughly similar performance to dispatching a large switch table, yes, but implementing opcodes as a table of functions allows you restructure your bytecode interpreter in a way that significantly improves performance. Here's a much better explanation than I could give of the dispatch-per-opcode technique, how it works, and why it's faster (tl;dr it's all about branch prediction): http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...

That article explains how to implement the technique for C programs using a "computed goto"/"labels as values" gcc extension. While Go lacks that feature, dispatching a table of functions as the last statement in each opcode implementation should yield a similar result. As long as Go supports "tail-call optimization" in the trivial case of "functions that take no parameters and return nothing calling similar functions" it should work just fine. Googling suggests that Go does not support TCO, but at least this program didn't explode the stack:

EDIT: Yes, it does.

  package main
  import ("fmt")
  var acc byte
  func main() {
  	fmt.Println(acc)
  	acc++
  	main()
  }

On my system that Go program does not seem to be tail call optimized. Look at the memory consumption over time. You aren't seeing an OOM because Go performs stack growth as necessary.

Oops, you're right, I was looking at the wrong process in htop: the "go run test.go" process used to build and launch it, not the actual test process, which indeed burned up memory very quickly (but not fast enough to crash when I ran it for a minute earlier). I should have sorted by CPU usage instead of searching by process name.

Can anyone think of any other way to implement this kind of dispatch system in Go? If it isn't possible, I don't think Go deserves the status of being "a good language to write emulators in," as this is a pretty important technique for improving performance of CPU emulation.

If you want the fastest possible speed, what you need is a technique called dynamic recompilation. Essentially, you compile the 6502 opcodes (or whatever) to native x86_64 code, and execute that. It's considered the gold standard of emulation. Nowadays, it's usually done by using LLVM to generate bytecode, and jumping to that.

By the way, I did enjoy reading your link about computed gotos. It sounds like what it comes down to is that the C switch statement does bounds checking, and the computed goto can avoid that. At the end of the day, though, no matter how many hacks you pile on, using an interpreter will have an overhead above dynorec.

N.B. Tail call optimization has its costs as well as benefits. Rust recently announced that it won't be supporting it. I don't know if the Go guys have made any statement about this, but I would imagine they might not consider it, for the same reasons. More here: https://mail.mozilla.org/pipermail/rust-dev/2013-April/00355...

> I'm not familiar with the implementation of Go, but at least this program didn't explode the stack:

It does, it's just that Go is so slow printing to the console that it would take years to run out of stack space. If you redirect to null it will use up all your memory and swap space in a few minutes:

./main > /dev/null

In most other languages this same code would run for a short time and then abort after exhausting the stack. This is the best behavior since algorithms that use unbounded memory are where you certainly must handle out of memory errors and set limits; using too much stack space is an error that should be caught quickly not postponed. Go on the other hand uses a growable stack, so the code you gave will use up all available memory and swap before finally crashing.

Go uses a growable stack so that programs can use many goroutines on 32-bit machines. This is bad for performance due to extra checks on calling function to see if the stack needs to be grown or shrunk, the overhead to actually do that, and less efficient use of cpu data cache. It makes it complicated to call functions from any other language. It seems like any modern language should work best on 64-bit and make trade-offs for 32-bit, not the other way.

Go uses a growable stack so that each goroutine's stack consumes less memory,not less address space.

You are mistaken. You don't need extra checks to determine when to grow the stack. You just need to leave some unmapped space after the stack and correctly handle a SIGBUS error. There is no extra overhead above what the operating system is already doing.

Growable stacks aren't about getting optimal performance on 32 bit architectures. That is explicitly a non-goal of Go. They're about minimizing memory consumption for goroutines which don't use very much stack space, which is expected to be most goroutines. You can't have hundreds of thousands of goroutines if you have a high fixed amount of memory per goroutine.

As for your argument that growable stacks make it harder to determine program correctness, it seems like nonsense to me. I could make the same arguments about heap space, but nobody thinks a low fixed limit on heap sizes is a great idea. If you want to test your program under low memory conditions, try mlocking a lot of memory and then running your program. Alternately you could try something involving cgroups or virtual machines.

I'm surprised that even ran. I've had issues in the past where go build refused to compile because it detected the potential for a recursive function call (this was in a table of functions where one func referenced another, so there wasn't any practical risk of getting locked in a loop even though the compiler detected a theoretical risk).

I'd probably rank that compile time 'error' as one of the most annoying I've seen to date because the code was actually fine, it was just the compiler pre-empting a non-existent risk. So I had to rewrite a chunk of code just for the sake of over-eager error catching (this is also why I wish go build would just warn about one or two trivial issues instead of flat out fail)

I have in the past written my CPU cores in a pseudo-language that allowed a custom preprocessor to spit out either a function call table or a switch table. (see bsnes v013 - v040 or so.)

It's not a significant difference. The margin of error is so slim that I couldn't confidently even say one ever outperformed the other.

The main difference is that, for about 512 instructions of 16-bit era complexity, the switch table binary will be about ~800KB smaller (obviously this is highly dependent on countless things. YMMV.)

Nowadays, I wrote a cooperative threading library. I am not sure how powerful a goroutine is, but my version allocates separate stacks so that each thread has its own nested call stack, and can exit even in subfunctions. It is indeed a major boon to writing clearer emulator code, to get rid of all that delicate state machine red tape. But it does come with a performance penalty in most cases.

Goroutines have independent 4k stacks.

The juxtaposition between this and https://github.com/pcwalton/sprocketnes is neat.

E.g. https://github.com/pcwalton/sprocketnes/blob/master/audio.rs compared to https://github.com/scottferg/Fergulator/blob/master/audio.go or https://github.com/pcwalton/sprocketnes/blob/master/disasm.r... compared to https://github.com/scottferg/Fergulator/blob/master/disassem...

It is interesting to read and compare both, but I would avoid a simple LOC comparison as the Go versions have a lot of extra lines (newlines, unneeded selects, redundant case statements) that could easily be eliminated.

What is the difference between sigle-case select vs just reading from the channel?

Nothing, just a remnant from aggressive debugging. I had a default clause in there at some point probably.

Ew, my audio code. :( I hacked the SDL audio bindings together with no regard to proper Rust idioms; hence the unsafe everywhere. The Go code reads far better.

The disassembler is nicer though—it demonstrates macros and traits well. The macros and AddressingMode trait help avoid duplicating the instruction decode logic between the CPU interpreter and disassembler, with no overhead at runtime.

The audio bindings are due to the excellent Go-SDL package. Nevermind my own fork, that was just to remove some unneeded stuff to fix compilation on OSX.

He should consider making the emulator able to read .fcm input logs from a TAS.

These runs usually serve as good tests of an emulators compliance. Particularly the runs that were verified on the actual console.

though... there are some cartridges that have random (read: not psudo-random) behavior, and can't actually be tested. (or tased at all)

Where does one go to learn how to create an emulator? I'm interested in picking up C/Go (probably the latter nowadays) while trying to make an emulator. Is there a process people adhere by or do they seriously just figure it out?

It's mostly the steep curve of learning the platform you're trying to emulate. Start here: http://emu-docs.org/ and read everything you can get your hands on.

Begin with the CPU and start emulating that. Then just start adding hardware bit by bit. It makes a lot more sense as you get into it.

For NES emulation, the community at nesdev.com is amazing for assistance if you get stumped.

I'm just beginning with emulators and I wrote my first one to emulate CHIP8 a few months ago. I'm now working on a gameboy emulator. Anyways, having no experience with assembly, processor instructions, bitwise operations, etc, I started with this tutorial:

http://www.multigesture.net/articles/how-to-write-an-emulato...

Also, good reference: http://en.wikipedia.org/wiki/CHIP-8

I think that tutorial quite good and I emerged with a solid understanding of what exactly emulators/interpreters do, and what it means to emulate a certain device. CHIP8 is very simple, so moving to gameboy is actually a very big leap. The gameboy's instruction set (you'll know why that is a crucial piece of information after completing the CHIP8 tutorial) is much larger, so it requires a lot more work and understanding.

Let me know if you have any questions

I have a 90%-working chip-8 emulator in JS. I never got around to fixing an instruction that waits for user input, though. http://luna.thehorseplace.us/pr/chip8.html

I wrote a post about creating a Chip-8 emulator in JavaScript, if JS is your thing.

http://blog.alexanderdickson.com/javascript-chip-eight-emula...

Best part is that if you've installed Go and set up the GOPATH already, downloading and compiling fergulator is just a

go get github.com/scottferg/Fergulator

away.

However, sdl, SDL_image and glew must be installed with header files.

Reply on news.ycombinator.com