Chapter 17
The Game of Life

The Triumph of Algorithmic Optimization in a Cellular Automata Game

I’ve spent a lot of my life discussing assembly language optimization, which I consider to be an important and underappreciated topic. However, I’d like to take this opportunity to point out that there is much, much more to optimization than assembly language. Assembly is essential for absolute maximum performance, but it’s not the only ingredient; necessary but not sufficient, if you catch my drift—and not even necessary, if you’re looking for improved but not maximum performance. You’ve heard it a thousand times: Optimize your algorithm first. Devise new approaches. Or, as Knuth said, Premature optimization is the root of all evil.

This is, of course, old hat, stuff you know like the back of your hand. Or is it? As Jeff Duntemann pointed out to me the other day, performance programmers are made, not born. While I’m merrily gallivanting around in this book optimizing 486 pipelining and turning simple tasks into horribly complicated and terrifyingly fast state machines, many of you are still developing your basic optimization skills. I don’t want to shortchange those of you in the latter category, so in this chapter, we’ll discuss some high-level language optimizations that can be applied by mere mortals within a reasonable period of time. We’re going to examine a complete optimization process, from start to finish, and what we will find is that it’s possible to get a 50-times speed-up without using one byte of assembly! It’s all a matter of perspective—how you look at your code and data.

Conway’s Game

The program that we’re going to optimize is Conway’s famous Game of Life, long-ago favorite of the hackers at MIT’s AI Lab. If you’ve never seen it, let me assure you: Life is neat, and more than a little hypnotic. Fractals have been the hot graphics topic in recent years, but for eye-catching dazzle, Life is hard to beat.

Of course, eye-catching dazzle requires real-time performance—lots of pixels help too—and there’s the rub. When there are, say, 40,000 cells to process and display, a simple, straightforward implementation just doesn’t cut it, even on a 33 MHz 486. Happily, though, there are many, many ways to speed up Life, and they illustrate a variety of important optimization principles, as this chapter will show.

First, I’ll describe the ground rules of Life, implement a very straightforward version in C++, and then speed that version up by about eight times without using any drastically different approaches or any assembly. This may be a little tame for some of you, but be patient; for after that, we’ll haul out the big guns and move into the 30 to 40 times speed-up range. Then in the next chapter, I’ll show you how several programmers really floored it in taking me up on my second Optimization Challenge, which involved the Game of Life.

The Rules of the Game

The Game of Life is ridiculously simple. There is a cellmap, consisting of a rectangular matrix of cells, each of which may initially be either on or off. Each cell has eight neighbors: two horizontally, two vertically, and four diagonally. For each succeeding generation of cells, the game logic determines whether each cell will be on or off according to the following rules:

•  If a cell is on and has either two or three neighbors that are on in the current generation, it stays on; otherwise, the cell turns off.

•  If a cell is off and has exactly three “on” neighbors in the current generation, it turns on; otherwise, it stays off. That’s all the rules there are—but they give rise to an astonishing variety of forms, including patterns that spin, march across the screen, and explode.

It’s only a little more complicated to implement the Game of Life than it is to describe it. Listing 17.1, together with the display functions in Listing 17.2, is a C++ implementation of the Game of Life, and it’s very straightforward. A cellmap is an object that’s accessible through member functions to set, clear, and test cell states, and through a member function to calculate the next generation. Calculating the next generation involves nothing more than using the other member functions to set each cell to the appropriate state, given the number of neighboring on-cells and the cell’s current state. The only complication is that it’s necessary to place the next generation’s cells in another cellmap, and then copy the final result back to the original cellmap. This keeps us from corrupting the current generation’s cellmap before we’re done using it to calculate the next generation.

All in all, Listing 17.1 is a clean, compact, and elegant implementation of the Game of Life. Were it not that the code is as slow as molasses, we could stop right here.