[Home | Contact | What's New? | Products | Services | Tips | Mike |
Living with Schizoaffective Disorder

Write the Fastest
Conway's Life Game:

This started out as a simple exercise and became a silly endeavour.
All I wanted was to learn PowerPC assembly code.

To motivate myself to actually do it, I challenged all the folks on comp.sys.mac.programmer to write a faster Life game than I could. This was to be my hack for MacHack but I slept all day Friday, and spent two weeks before the conference figuring out that the result of 300 times 300 won't fit in 16 bits, and that you won't get null events unless you handle your update events. This required the personal attention of MacDTS to find, even though my job is debugging the MacOS.

Beer Bottle Caps

I'm persisting in this endeavour (though I have yet to write any PowerPC assembly code), and have decided to write a sort of Life application framework. My application will provide a user interface, file format and printing, as well as a couple of built-in methods for propagating the game. It will accept "plug-ins" that you can write to implement your algorithm. (Coming Real Soon Now: the plug-in specification.) The very beginning of the plug-in architecture has been written. Read the code - it's the best documentation, eh?

Two prizes will be given, one for the coolest 68k entry, and one for the coolest PowerPC entry. The prize will be a large bottle of fine locally brewed beer.

The deadline will be in early September - moved out from August, because I decided I needed the time to be able to do anything interesting. I'll set a date later. (All prizes to be awarded - you're not competing against me, except that I will crow about it if no one can beat me.)

Maybe, if I'm generous, I'll give one for the entry that uses the least memory. The judging will be done pretty much arbitrarily, but basically I'll create a variety of initial patterns and see how each method does with each starting pattern. So far I'm only prepared to deal with code that runs on the Mac. I could accept code for Linux or DOS if there were demand, but I'm not likely to write the shell for it.

You don't have to write it in assembly - you could use COBOL if you like - but I'd be pretty impressed if you can write faster C code than I can write assembly.

The timing will include drawing to the screen. There may be an option to not draw, so that raw performance can be measured, but all the methods I have seen so far can be slowed down enough by making the field larger that the generations pass slower than the screen refreshes. It is acceptable to require particular bit depths, but please note that there are PowerPC models that do not have monochrome as an option; all of your methods should at least be able to run on an 8 bit monitor.

Note that the criterion for winning is "coolest"; this is a nebulous criterion to which speed greatly contributes. Interesting tricks in your code are cool too.

Part of why I chose this particular problem to work on is that there is not a whole lot of opportunity to speed it up by using higher-order algorithms. I think that the best that you can hope for is that the algorithm time will be proportional to the number of living cells, so that the worst case time will be proportional to the total number of cells in the grid. It is in such a case that skanky coding becomes really worthwhile. Note that while I don't believe you can have an algorithm which is not proportional to the number of cells in running time, the algorithm can affect the constant of proportionality, so that one is likely to win more from algorithm choice to start with than from just doing it in assembly.

If you are writing it for 68k, consider the cache sizes on both the 68020 and the 68040. It is actually possible to write code to the '020 cache and get tremendous speed improvements.

The Rules of Conway's Game of Life

Conway's game of Life was described in Scientific American's Mathematical Games column back in the early 70's (can you tell me which issue?). The game is played on an infinite grid of cells, which may be alive or dead. The cells live or die from generation to generation according to whether they are already alive, and how many living neighbors they have.

The neighbors will be each square that a King could move to on a chessboard.

Here is an example. The dots are dead cells, the O's are live cells. We start with three live cells in a column:


Now we count the neighbors that each of these cells have:


You see that the middle cell is alive and has two neighbors, so that it stays as it is. The top and bottom cells have only one neighbor so they die. The cells to the right and left of the middle have three neighbors, so they live. There are other cells with two neighbors but they were dead to start with so they stay dead:


You can see that this will flip back and forth, so it is called a blinker or traffic light. There are many such animals in the life world, such as gliders, glider guns, blots and so on. It is fascinating to watch for the animals to appear, and to record their shapes so that one can play with them later. I will include a menagerie pallette to make it easy to add in the familiar animals, and save the new animals you find. My friend Stefan Youngs tells me that back when Life was played on mainframes at IBM in the 70's, the engineers would develop affections for the creatures in their world.

An interesting property of these rules is that they are not reversible - you cannot run the game backwards - consider that a single cell, all alone, will immediately die, but a blank field run backwards will never resurrect that cell. This can be disappointing if you see a really neat pattern appear and then disappear.

It might seem to some of you that there is not much choice to the algorithm, but to get you started, consider that you could take advantage of any or all of the following:

There are lots of tradeoffs. For example, on the '020, you only have 128 bytes of instruction cache, so if you have some elaborate algorithm in your inner loop, you will blow your cache. I have written at least one program in which I sped the program up by a factor of two by getting the two innermost loops to fit in the '020 processor cache. On the other hand, some instructions may be compact and do a lot for you, but are very slow to execute, and may stall the pipeline on the PowerPC because of dependencies on shared resources like condition code bits. Thus you can see that this is a deceptively simple problem, and in fact I chose it because it is a problem which is both simple enough to have some hope of exploring it in detail but complicated enough to be really interesting.

A good reference on many of these methods is Optimizing PowerPC Code by Gary Kacmarcik, Addison Wesley 1995, ISBN 0-201-40839-2.

Consider that the code I presently provide, which operates in a simple and obvious way, can run at full screen refresh rate only up to about 100 by 100, even on a PowerPC. Compare that to Marathon or Doom, which can operate a video game and do real time 3D color animation on a Quadra 605. Do you think they're using C++?

The Code

Enough already. Get Mike's Life source code via anonymous FTP and get to work.

Sorry! I don't have my source where I can get at it, but I expect one of the original contestants will have it.

(The code that is presently there is pretty rudimentary. You will need to fetch updates later. Send me email if you get the code and I will notify you of updates.)

I presently hold copyright in my code but I plan to change that to the GNU copyleft. You can copyright your source any way you please, but to enter the contest, you must allow me to post your source for anonymous FTP along with the Life framework.

The Contestants

Send me your URL and I will put a link to your homepage here. Mail addresses are acceptable URL's if you have no homepage.

[Home | Contact | What's New? | Products | Services | Tips | Mike]