Conways Game of Life

Several months ago I was interviewing with various companies, primarily for senior web developer roles. In total I probably spoke with just under a dozen companies. Some had phone screens and some had in-person interviews. Some had written tests and some used white boards. My favorite of all the different interview approaches were the companies who asked me to build something. And of the companies who asked me to build something, my favorite was being asked to build Conway’s Game of Life (wikipedia link).

Conway_s_Life

Before I get into Conway’s Life (the main thrust of this blog post), let me briefly comment on why open-ended assignments are the way to go when it comes to job interviews:

  • Do you want to see how well someone can bullshit? Or do you want to see how well they can code?
  • Assigning a project measures not only technical prowess, but dedication and interest in the position
  • Instead of assessing how well someone will do on tasks tangentially related to the position, why not see how well they’ll actually do with something more real-world?
  • Best of all, it’s fun

Of the three interviews in which I was given projects, two were open-ended. Of the two, my favorite one was this: “Build an implementation of Conway’s Game of Life”.

In a nutshell, Conway’s Life is a programming exercise in which a grid of cells is implemented. Each cell can be either on or off. The number of adjacent cells which are “on” determines whether or not a given cell is toggled on during each “turn”. This simple logic can result in fairly complicated patterns emerging from an extremely simple starting point.

My implementation was written in Javascript and HTML.

Check it out by visiting this page and clicking Play.

Here are a few interesting points about my design:

  • I split the design into two modules. The life class implements an internal state of the Life board and the lifedom class handles exposing this state via the DOM.
  • The animation in lifedom works by toggling the background of the table cells on and off. Originally, the animation was so fast that I actually needed to slow it down (via setTimeout) to create a more aesthetically appealing effect. I added a slider that lets you slow down or speed up the animation by changing the value of the timeout.
  • I added unit tests. They make sense for the life class, less so for lifedom, so I got lazy as I added various bells and whistles to the latter.
  • Because I originally wanted tests for lifedom, it lead me to a regrettable design decision: there is HTML in the javascript. I wanted to avoid duplication and only define the HTML of the game board once. Generally speaking, there are 3 ways to do this:
    • Use PHP to define an HTML template to use in both the unit tests and the application. Pro: Easy. Con: Requires PHP.
    • Use Javascript for the template. Pro: Easy. Con: Ugly. Clunky.
    • Use Grunt to manage different builds for test versus production. Pro: Best pure javascript solution. Con: More complicated than the alternatives.

Performance

For me, the most interesting part of this project came shortly after I finished my first implementation. I decided to check it out on my 1st generation iPad Mini. The animation looked horrible. The “frame rate” was way too low and it looked visibly underpowered and stuttered. I tried reducing the timeout to try and speed things up, but this didn’t help: entire frames would be dropped and it still looked like shit.

It’s funny because I knew immediately how this would go down:

  • I’d first trust my gut and try a quick fix
  • This wouldn’t work so I’d get more analytical and go through looking for additional optimizations
  • I would once again fail and resort to replacing the animation with canvas as a last ditch effort to get something that looked decent. I had no idea if this would work.

My first attempt at better performance was to replace .toggleClass(‘on off’) with direct manipulation of the backgroundColor property. My rationale was that this would avoid CSS repaints and perform better. I also added some caching of which cells were “on”, which avoided a jQuery find() operation. You can see the github changeset here.

I added some basic benchmarking to measure the impact (or lack thereof) of this change. I created a running counter of “turns per second” which turned out to be a great benchmark. The less the animation slowed down the program, the higher the turns per second would be.

To measure each change, I used the R-Pentomino pattern and grabbed my benchmark at turn 150, which represents a peak for the pattern in terms of the number of enabled cells in the pattern (and consequent steep drop in animation performance on the iPad Mini). By comparing the Baseline/Control stats against a Test Run that has all the animation suppressed (such that each turn is calculated in the life class but never displayed on-screen) you can see how much the animation itself actually slows things down.

Baseline/Control Stats

  • Chrome on Macbook: 16tps
  • iOS Simulator on Macbook: 16tps
  • iPad Mini (1st generation): 5tps
  • iPhone 5S: 14tps

Animation Disabled

  • Chrome on Macbook: 19tps
  • iOS Simulator on Macbook: 19tps
  • iPad Mini (1st generation): 17tps
  • iPhone 5S: 18tps

Next, we see the impact of my first attempt at improving the animation performance by replacing toggleClass(‘on off’) with backgroundColor. It helped, but not enough.

Classes Removed

  • Chrome on Macbook: 18tps
  • iOS Simulator on Macbook: 19tps
  • iPad Mini (1st generation): 7tps
  • iPhone 5S: 16tps

I tried some additional optimizations which didn’t really do much:

  • Instead of turning the entire board off and then turning cells on, figure out which ones should remain on and don’t turn them off in the first place: commit.
  • Keep the internal array state of life sorted so we iterate less: commit.
  • Replace document.getElementById with a cache so it only gets called the first time: commit. This last change made a tiny difference, at least on the iPhone.

Cached DOM Lookups

  • Chrome on Macbook: 18tps
  • iOS Simulator on Macbook: 19tps
  • iPad Mini (1st generation): 7tps
  • iPhone 5S: 17tps

At this point, I knew my only hope of getting acceptable performance would be to drop the idea of using a

altogether and swap out the table with a when the user clicks Play and use that for the animation (changeset here). The results were pretty interesting and gratifying. Most importantly, it gets performance to an acceptable level on the iPad Mini.

Canvas Animation

  • Chrome on Macbook: 18tps
  • iOS Simulator on Macbook: 19tps
  • iPad Mini (1st generation): 11tps
  • iPhone 5S: 16tps

By reducing the timeout value, I’m able to get the turns per second higher on an iPad without dropping frames. Note how it actually performs slightly worse on an iPhone 5S. Even on my iPad Mini, canvas actually starts out worse than the

solution (peaking at 17tps versus 18tps) before eventually overtaking it by turn 150.

If I were motivated to work on performance more, I might consider coding something that turns the timeout value down dynamically to respond to a low tps value. This would allow a consistent animation speed on both overpowered and underpowered devices — you would set the desired tps, rather than setting the timeout interval.

What’s Next

I’m happy with the performance aspect of my program at this point. I might eventually add some drag and drop functionality so you can drag gliders, lines, pentominos, etc. onto the game board to more easily build complex patterns. I also toyed with the idea of adding different colors to the animation such that areas of the game board which are more busy would be colored darker than the parts which are burned out.

If you’re bored, feel free to fork my implementation, add something cool and send me a pull request.