Skip to content

Remembering Six Years of ZMPP Development

Z-Machine Preservation Project

I am happy to announce that ZMPP can now be found and downloaded from the Android Market. Shipping a software project always fills a developer with relief and pride and for me there is no difference. I wanted to take the opportunity to reminisce about the process that led up to this point, as ZMPP has recently turned 6 years old . It’s amazing that nowadays, you can just search the web to help you track the proceedings of a project.

The Beginnings

In 2005, I decided to learn Test Driven Development, so I picked up Kent Beck’s “TDD By Example” and studied it. Along with that, I also decided to practice the techniques on a non-trivial project. Right around that time, I also remembered that I had never played any of the classic Infocom adventures – my first experiences with the IF until then had been “The Hobbit” for the C64 and “Fish” and “Guild of Thieves” for the Amiga.

So that was it, I got myself a copy of the “Masterpieces of Infocom” for something like 180 US Dollar from Ebay, my 12.1″ iBook G4 and the Z-Machine Specification and said to myself: “now TDD yourself a Z-Machine interpreter to play these”. I usually worked on our kitchen table or on the bus, because I did not have a desk. I still don’t use one, so “deskless ZMPP development” has been something of a tradition, just with the work places being extended to coffee shops and Barnes&Noble. I called the project “Z-Machine Preservation Project” to indicate that I was going to revive an extinct technology. Little did I know that the Z-Machine was still alive and well.

Even though I did not TDD everything, it was a large portion of the code and I learned a lot about both the strengths and limitations of TDD and the Z-Machine. The Z-Machine is good for this kind of project, because it has a good specification, which you can match up with tests (except perhaps the UI part). Within 3 weeks, I was able to get my reference game “Leather Goddesses of Phobos” to play the first turn, take the input and crash on an invalid instruction code. That’s somewhat the general approach I have taken to start implementing emulators and virtual machines: trying to keep the VM running longer between crashes. I benefitted a lot from only being able to afford programming in assembler on the Amiga and C64 as a teenager, reading long runs of Z-code mnemonics felt oddly familiar.

After 3 more weeks, I had the first stable version that could run V3 games, for a total of 6 weeks, always working in the evening. After having implemented 4-5 Z-Machine interpreters in different programming languages, I only need a fraction of that time to get V1-V3 running now.

Reality Check: Meet the IF community

After making the first release of ZMPP, I was trying to share my efforts, because I thought it could very useful if authors could publish their works on the web. But when your software hits users, things might turn out different than what you expected.

First of all, the Z-Machine version V3 is almost not used in modern Interactive Fiction, due to its limitations in terms of available memory and text representation. These weaknesses are also some of the motivations behind the Inform authors moving more and more to the Glulx platform, which ZMPP supports now, but is not available on Android – yet.

Another thing is that Inform 6 stories are in general more computational demanding than Infocom. I did not know this when I started and my tests were initially performed on Infocom games. The initial ZMPP had lots of classes and created lots of immutable objects, also because TDD encourages many classes and many methods. This often leads to better code, but in an interpreter that runs thousands of instructions per turn, this can hurt you, especially when combined with creating lots of small objects that need to be garbage collected.

Enter the Web – Smeagol

ZMPP was originally designed to run as a Java application first and as an applet second. Sun Microsystems brought out Java Applets in the mid-90’s and they were cool and exciting at the time, unfortunately they did not put enough effort into it, so Flash pretty much took the market, and nowadays, even Flash seems to be on its way out.

The one thing that I always disliked about applets was that they felt like a bolt-on in the browser and I also knew that you could achieve a lot with web browser technology alone. Look at the efforts behind Parchment to see how far this has come today, it’s working pretty well.

So, in 2006, I decided to port ZMPP to Ruby, with a Ruby on Rails interface. It worked quite well as a proof-of-concept, but would require special hosting, which I could not afford. From this experience, however, I derived ZMPP’s execution model, that the interpreter runs until it requires user interaction and is resumed from the user interface again.

Schmalz – An Erlang Port

Schmalz (german word for “Lard”), was an exercise in programming Erlang, which I did in late 2007. I taught myself the actor model as well as the Erlang OTP failure recovery model with it. Erlang provides some wonderful tools to make scalable and recoverable systems and I love the way you can express operations on binary data with pattern matching, but it is not really a great platform for Z-Machine/Glulx interpreters that mostly run on a single thread/process. When Erlang can not take advantage of its scalability, it is actually quite slow.

Still, I wrote the beginnings of the ZMPP Glulx implementation in Erlang, that’s why I mentioned it here.

ZMPP2 – A new home at the Scala

In 2010, I was toying with the idea of distilling all that experience I made over the years in a new implementation. I knew that I wanted to stay on the Java Virtual Machine, but wanted to use a different language than Java. This is probably one of the few advantages being the sole developer on an Open Source project: you can change technologies at will. The best alternatives at that time were (and still are in my opinion) Clojure and Scala.

I love Lisp and do most of my coding tasks in Emacs for that reason, but given my experiences with Erlang and Ruby, which are both dynamic languages, I decided to go with Scala. Scala is a language chamaeleon in many ways in that it is very flexible like a dynamic language, yet you have great control over the representation of data. You can easily use mutable objects if you need to and you can use primitive types. In other words, you can use Scala, as a “better, cleaner Java” if you need to, and use a more functional style in non-performance-critical code.

Yeah, reality is, in a Z-Machine or Glulx interpreter, a lot of code is performance-critical and CPU-bound as we see later in the performance section.

A nice side effect of using Scala is that the language does not try to force me into putting a three-line class into its own separate source file and so I can group related classes in a single file. ZMPP2 has now about the same size as the original ZMPP – but includes the more complicated Glulx and Glk implementations in addition to the Z-Machine. To be fair, the shorter code is due to choosing more efficient data representations first and due to using Scala second.

I was initially concerned about the overhead Scala introduces, especially about closures and the fact that access to member variables is usually wrapped into accessor methods. Closures, generated by for-expressions, did in fact make the code a lot slower on Android due to a lot of garbage collection invocations they caused, but Android’s Dalvik VM is actually pretty good – if you can avoid creating too many objects in your execution loop, performance is similar to its Java equivalent. I did, at one point experiment with rewriting parts in Java, but the performance gain was close to zero, so I switched back to pure Scala.

Another thing that led to increased garbage collection was that I created a large number of case class instances, with the additional problem that they are created without the “new” keyword, so you can not find the instantiation as easily. I use case classes all the time, but for the ZMPP core, I had to replace them with a mutable representation.

People recently have been talking all over the place about “never use this” and “never use that” in Scala, e.g. closures, Scala collections or what not, up to the ridiculous point where you could interpret that as “when programming Scala, never use any Scala features ever” (which was not what the original post said, btw). Well, I did not use Java collections in performance-critical code either, just plain integer arrays, because these are even faster, there you go. The emphasis is on “performance-critical”, nothing will ever stop you using the nicer Scala alternatives in the other places where they come in handy. Additionally, things change over time, I guess that there are still people out there thinking that Java is slow because that was true 15 years ago. But then, people might as well still think computers only have 8 K of memory and are as large as your fridge.

ZMPP/Android – ZMPP goes mobile

Fast-forward a year and a half to October 2011. I looked into interpreters for Interactive Fiction on Android and it seemed that the available ones are taking the route of using C implementations through the Android NDK. It sounds reasonable, because at the moment, IF interpreters are “embarassingly non-parallel” and it is harder to make a VM-in-a-VM perform comparably well as a C implementation.

I am taking a slightly different stance, though: I released “Logic Shrinker”  more than a year earlier. “Logic Shrinker” was developed on Android 1.6, which does not contain a JIT. There is some code in this application that is computational intensive, but the tuning improved over the initial performance by about 1000%, perfectly sufficient on my slow HTC Magic/myTouch.

Now the minimum Android version ZMPP supports is 2.2 Froyo, which includes a JIT. I don’t see any hope you could get reasonable performance running Inform 7 games without a JIT, so it does not make any sense to support lower Android versions.

The Android team did a great job on the Dalvik VM, given that it is not based on Hotspot and they had to practically write it from scratch. Startup times are fantastic, even when compared to iOS applications, something you would not expect from the typical Java desktop application. I took the gamble and just used my ZMPP2 Z-Machine core (I am certainly not going to go back and write a Z-Machine in C anyways).

My build setup

I had to fiddle with my build setup quite a bit initially, but having the android plugin for SBT made things relatively easy. I use just the plain vanilla setup, without putting pre-packaged Scala libraries on my device. The reason is that when I did that, build times were awesomely short, but I had to pay back in startup time on the emulator so the wait times were similar, around a minute or so per build, YMMV. As previously said, I use Emacs for all development, because I work with a lot of different programming languages all the time, from 68000 assembly to R and Emacs can handle all of these pretty well.

When I started programming in Scala, I used Maven, because it has become my tool of choice for Java projects, but recently, SBT has become the best Scala build tool available. The full configuration with a .scala project file has turned out to be better than the .sbt alternative for building ZMPP.

Performance

A little earlier, I promised some numbers, here some Infocom games, along with “Curses”, an Inform game:

Story Author Year Z-Machine Version avg. instructions/turn
Zork I Infocom 1980 3 ~500
A Mind Forever Voyaging Infocom 1985 4 ~2000
Border Zone Infocom 1987 5 ~1000
Curses! Graham Nelson 1994 5 ~4500

Curses is just a single example, but I would say, among pre-Inform 7 works, its instruction/turn count is probably the lower average.

Inform 7 games can increase the complexity even more – far more. Some examples:

1. In “Bronze” (Emily Short, 2006), you can see numbers of typically a couple hundred thousand instructions per turn. If I recall correctly, this is due to an Inform extension that dynamically computes directions and a compass rose.

2. “Reliques of Tolti-Aph” (Graham Nelson, 2006), what I call the “World Record holder for most instructions in the first turn”. It takes 3,132,785 instructions for the game to display the first input prompt. “Tolti-Aph” is a special case, it is actually more like an RPG than a typical work of Interactive Fiction.

Both Graham Nelson and Emily Short often push the limits of and demonstrate the power of the Inform authoring system, so as an interpreter author, their stories are a very good way to test the efficiency of your interpreter. As people who worked on tuning performance-critical code probably noticed by now, there is actually some potential room for optimization here: Initialization of non-random content could be precomputed at compile time, the same goes for path finding: unless you have a randomly generated map, you can probably get away with baked-in offline computed data. There is some ongoing optimization work on the Inform compiler side, but I have no knowledge about the status.

Back to ZMPP: the current ZMPP2 core takes something like 700 ms on Java 6 on my 4 year old Macbook Pro/2.4 Core 2 Duo to execute these 3 million+ instructions. I remember running “Tolti-Aph” for the first time in 2006, I thought my interpreter was running in an infinite loop, it took a long, long time. Eventually I learned how to get satisfactory performance without the need to use obscure hacks, even though “Tolti-Aph”‘s first turn still takes some time on mobile devices.

Well, enough of the rambling and reminiscing, working on ZMPP has been exciting so far and will hopefully continue to be. I have my roadmap laid out, but nothing set in stone, staying flexible has served me well over the years.

In closing, I wanted to say thanks to all those members of the IF community that I had the pleasure to meet over the years, either in person, through mail or on one of the forums. This has been the real blessing of working on ZMPP: To learn from people who really care about Interactive Fiction and who try to advance it. Most of them have been actively involved for decades. I will try to continue learning from you. Since the new year is approaching as well, I might as well wish you a Happy New Year.

 

Available in Android Market

10 Comments