|Previous||Table of Contents||Next|
Ive spent a lot of my life discussing assembly language optimization, which I consider to be an important and underappreciated topic. However, Id 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 its not the only ingredient; necessary but not sufficient, if you catch my driftand not even necessary, if youre looking for improved but not maximum performance. Youve 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 Im 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 dont want to shortchange those of you in the latter category, so in this chapter, well discuss some high-level language optimizations that can be applied by mere mortals within a reasonable period of time. Were going to examine a complete optimization process, from start to finish, and what we will find is that its possible to get a 50-times speed-up without using one byte of assembly! Its all a matter of perspectivehow you look at your code and data.
The program that were going to optimize is Conways famous Game of Life, long-ago favorite of the hackers at MITs AI Lab. If youve 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 performancelots of pixels help tooand theres the rub. When there are, say, 40,000 cells to process and display, a simple, straightforward implementation just doesnt 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, Ill 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, well haul out the big guns and move into the 30 to 40 times speed-up range. Then in the next chapter, Ill show you how several programmers really floored it in taking me up on my second Optimization Challenge, which involved the Game of Life.
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:
Its 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 its very straightforward. A cellmap is an object thats 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 cells current state. The only complication is that its necessary to place the next generations cells in another cellmap, and then copy the final result back to the original cellmap. This keeps us from corrupting the current generations cellmap before were 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.
|Previous||Table of Contents||Next|