Basic Optimisation

Its been a rough day at work and out of the blue, I decide I'm going to write an implementation of Conway's Game of Life. I've written one with practically every other Pascal compiler I've used, but never with Delphi.

For those of you that have never encountered the Game of Life, there's a good article on Wonders Of Math.

Why is any of this relevant? Because over the course of the next couple of hours, I put together what is essentially a very untidy little program, with no glitz (the GUI is basic) and no glam (it uses TPaintBox as its output), but, that does provide some useful points about the basics of optimization.

So what is the Game of Life?

Just in case you don't know what the Game of Life is and haven't read the excellent article at Wonders of Math, it goes something like this... the Game of Life is a simulation of a simple cell based system. It is supposed to use an infinitely sized grid. Cells within the system follow these basic rules:-

• If I have less than 2 neighbours, I die of loneliness
• If I have exactly 3 neighbours and I'm not alive, I am born
• If I have 2 or 3 neighbours and I'm alive, then I survive
• If I have more than 3 neighbours, its too cramped... I die of overcrowding

So, you activate some cells and then apply these rules to every cell in the grid. Repeat, add infinitum. This sounds like an easy little program, and it is, a really easy little program, but one that does have some good scope for introducing some basic optimization.

There is a ZIP file containing the source code and various EXE's that illustrate the points discussed in the article. It is available for download from here.

The Original Program
From the rules, you can see there are certain values that are important. When I originally started writing it, I couldn't remember these values and I didn't want to Google them... I wanted to code, so I added some edit boxes to allow me to tweak them.

I decided I would do a small grid (80 x 80, although this quickly became 282 x 282 - the size used for all the timings) and that I would render this on a 705 x 705 paint box control with a cell size of 8 pixels. First thing to do is write a renderer and hook up events to activate/deactivate cells when the user clicks on the grid.

The renderer is incredibly basic. Using only TCanvas's fillRect method it fills the paint box clipping area with white and then proceeds to render each cell by filling it with the appropriate colour (governed by how long the cell has been alive). Moving onto the editor, the code works out where the mouse was on the click and then calculates a grid reference by div'ing them by the cell size. It then toggles the cell and redraws the display.

Once you have placed your cells, you click 'Start' and off it goes. The cells spring into life and begin their journey. When this happens, all hell break lose. The system uses TTimer to call the code that generates the next generation of cells from the existing grid. It does this repeatedly as long as the system is set to run.

If you look at the source code, you will notice a whole bunch of conditional defines at the top. What I've actually done, is deoptimise the source to take it back to the original version. This can be tried out by running the Life_Original.exe or compiling the code with none of the conditional defines set (stuff a _ in front of them), except 'optimisedvariablerules'.

First Impressions

Editing the grid is a nightmare.. lots of screen flicker and actually running the simulation... painfully slow. So lets tackle the least important of these first... editing the grid.

The Editor

You will have undoubtedly noticed the horrendous screen flicker when you edit the grid. This is caused by the full screen refresh that occurs whenever you toggle a cell. The original mouseUp event handler that forms the editor can be seen below.

We have a couple of options open to us at this point. The first is to batch our updates, so that not every click of the mouse forces a repaint. To enable this optimization remove the _ from the conditional define editoroptimisation1 or run the exe Life_EditOpt1.exe

This is relatively easy to achieve with the simple addition of a timer (tmrRefresh) to the form. This timer is disabled when the application starts and is only enabled by the mouseUp event handler of the TPaintBox (pb), after it has finished toggling the cell. This event handler also disables the timer when it starts... this means that so long as we click again before the interval of the timer has expired, a repaint won't occur, this means we can click click click click then pause and see our handy-work when the timer fires.

tmrRefresh Event Handler

mouseUp Event Handler of TPaintBox (pb)

This does remove some of the screen flicker, but it introduces a new problem. Its no longer easy to see the changes your making, without waiting for an update. You could reduce the delay, but this will only increase screen flicker, clearly, this isn't a very good method for optimizing the editor.

The second and most obvious method is to simply update the cell thats changed. You can see the difference by enabling editoroptimisation2 or running Life_EditOpt2.exe.

The revised mouseUp handler looks like this...

Now, we get instant visual feedback about our options and there is practically no screen flicker, so the job is complete as far as the editor is concerned. I suspect many of you choked as soon as I suggested the batch update approach, but this article isn't about getting straight to the optimal method... its about the thought processes that should be going on in your head when you consider how to optimise your code. I opted to try the batch update approach because I've seen some graphics tools use this method with great effect, but for my purposes, it was not the best way as it still resulted in screen flicker and didn't provide instant visual feedback. At that point, it wasn't my highest priority... I wanted to see the simulation run and the editor is a relatively minor part of that, so I decided to leave it as it was.

My options at that point were also restricted by the routines I had coded. Initially, the only routine that updated the canvas displaying the map was 'paintmap'. It wasn't until I added the 'drawcell' routine during my optimization of the code that prodcues the next generation of cells that I went back and finished off optimizing the editor. I could have coded it, but it was late, I was lazy and I could live without it... for a while anyway.

This does illustrate a very valuable point about optimization. The process of optimizing your software should have started even before you write the first line of code. Good design can often highlight potential problems before they occur, the more experience you get, the more potential pitfalls you may be able to avoid during the design phase.

Had I spent any time thinking about it before hand, its highly likely that I would have had a 'drawCell' routine in my original code and as such, probably wouldn't have had to worry about optimizing the editor since it would make use of 'drawCell' in the original design.