Where to Optimize – the 90/10 rule
In performance-hungry games, 90 percent of a program’s execution time is spent running 10 percent of the code. It is in this 10 percent of the code that we should concentrate all of our optimization efforts. We locate that 10 percent using a profiler. To turn on the Profiler Utility in the J2ME Wireless Toolkit, select the Preferences item from the Edit menu. This will bring up the Preferences window. Select the Monitoring tab, check the box marked “Enable Profiling”, and click the OK button. Nothing will happen. That’s okay – we need to run our program in the emulator and then exit before the Profiler window appears. Do that now.
Figure 1 illustrates how to turn on the Profiler Utility.
My emulator (running under Windows XP on a 2.4GHz Intel P4) reports that 100 iterations of the loop took 6,407ms, or just under six and a half seconds. The app reported 62 or 63ms per frame. On the hardware ( a Motorola i85s ) it ran much slower. Time per frame was around 500ms and the whole thing ran in 52460ms. We’ll try to improve these figures in the course of this article.
When you exit the application the profiler window will appear and you will see something that resembles a folder browser, with the familiar tree widget displayed in a panel on the left. Method relationships are shown in this hierarchical list. Each folder is a method and opening a methods folder displays the methods called by it. Selecting a method in the tree shows the profiling information for that method and all the methods called by it in the panel on the right. Notice that a percentage is displayed next to each element. This is the percentage of total execution time spent in that particular method. We must navigate through this tree to find where all the time is going, and optimize the methods with the highest percentages, where possible.
Figure 2 – the Profiler Utility call graph.
Click here for larger image
A couple of notes about the profiler. First, your percentages will almost certainly vary from mine, but they will be similarly proportioned – always follow the biggest numbers. My numbers varied every time I ran the app. To keep things as uniform as possible, you might want to close any background applications, like email clients, and keep activity to a minimum while you’re running tests. Also, don’t obfuscate your code before using the profiler or all your methods will be mysteriously named “b” or “a” or “ff”. Finally, the profiler doesn’t shed any light on the performance of whatever device you are emulating. The hardware itself is a completely different animal.
Opening the folder with the highest percentages we see that 66.8% of the execution time went to a method named “com.sun.kvem.midp.lcdui.EmulEventHandler$EventLoop.run”, which doesn’t really help us. Digging down further unfolds a level or two of methods with similarly obscure names. Keep going and you’ll trace the fat percentages to serviceRepaints() and finally to our OCanvas.paint() method. Another 30% of the time went into our OCanvas.run() method. It should come as no surprise that both of these methods live inside of our main game loop. We won’t be spending any time trying to optimize code in our MIDlet class, just as you shouldn’t bother optimizing code in your game that’s outside the main game loop. Only optimize where it counts.
The way that these percentages are divided in our example app is not entirely uncharacteristic of how they would be in a real game. You will most likely find that the vast proportion of execution time in a real videogame is spent in the paint() method. Graphics routines take a very long time when compared to non-graphical routines. Unfortunately, our graphics routines are already written for us somewhere below the surface of the J2ME API, and there’s not much we can do to improve their performance. What we can do is make smart decisions about which ones we use and how we use them.
High-Level vs. Low-Level optimization
Later in this article we will look at low-level code optimization techniques. You will see they are quite easy to plug into existing code and tend to degrade readability as much as they improve performance. Before you employ those techniques, it is always best to work on the design of your code and its algorithms. This is high-level optimization.
Michael Abrash, one of the developers of id software’s “Quake”, once wrote, “the best optimizer is between your ears”. There’s more than one way to do it (TMTOWTDI) and if you take the extra time to think about doing things the right way first, then you will reap the greatest reward. Using the right (i.e. fastest) algorithm will increase performance much more than using low-level techniques to improve a mediocre algorithm. You might shave a few more percentage points off using the low-level stuff, but always start at the top and use your brain (you’ll find it between your ears).
So let’s look at what we’re doing in our paint() method. We’re calling Graphics.drawString() 16 times every iteration to paint our message “n ms per frame” onscreen. We don’t know anything about the inner workings of drawString, but we can see that it’s using up a lot of time, so let’s try another approach. Let’s draw the String directly onto an Image object once and then draw the Image 16 times.
public void paint(Graphics g) {
g.setColor( COLOR_BG );
g.fillRect( 0, 0, getWidth(), getHeight() );
Font font = Font.getFont( Font.FACE_PROPORTIONAL,
Font.STYLE_BOLD | Font.STYLE_ITALIC,
Font.SIZE_SMALL );
String msMessage = frameTime + “ms per frame”;
Image stringImage =
Image.createImage( font.stringWidth( msMessage ),
font.getBaselinePosition() );
Graphics imageGraphics = stringImage.getGraphics();
imageGraphics.setColor( COLOR_BG );
imageGraphics.fillRect( 0, 0, stringImage.getWidth(),
stringImage.getHeight() );
imageGraphics.setColor( COLOR_FG );
imageGraphics.setFont( font );
imageGraphics.drawString( msMessage, 0, 0,
Graphics.TOP | Graphics.LEFT );
for ( int i = 0 ; i < DRAW_COUNT ; i ++ ) {
g.drawImage( stringImage, getRandom( getWidth() ),
getRandom( getHeight() ),
Graphics.VCENTER | Graphics.HCENTER );
}
}
When we run this version of our software, we see that the percentage of time spent in our paint method is a little less. Looking deeper we can see that the drawString method is only being called 101 times, and it is now the drawImage method that sees most of the action, being called 1616 times. Even though we are doing more work, the app runs a little quicker because the graphics calls we are using are faster.
You will probably notice that drawing the string to an image affects the display because J2ME does not support image transparency, so a lot of the background is overwritten. This is a good example of how optimization might cause you to re-evaluate application requirements. If you really needed the text to overlap, you might be forced to deal with the slower execution time.
This code might be slightly better, but it still has a lot of room for improvement. Let’s look at our first low-level optimization technique.