Execution speed has always had a unique importance to game developers. More so than any other area of software, games typically must squeeze every ounce of performance out of the host system. This is distressing news for those of us writing games in Java, simply because Java is so removed from the specifics of the host system that it's extremely difficult to cut corners while coding. However, even though you can't get down and dirty with the hardware, you can still optimize Java code in various ways to improve performance in your games.
Today's lesson deals with Java code optimization and how it can be used to speed up Java games. You'll learn various optimization techniques that will help you become a more efficient Java programmer. To really understand how these optimizations help, you have to go under the hood of Java, so roll up your sleeves and prepare to get a little dirty.
As you go through today's lesson, keep in mind that it's one of the last lessons in the book for a very good reason: Any thoughts of optimizing your code should occur near the end of the development cycle. In other words, focus on getting your game up and running, and then focus your attention on looking for ways to optimize.
The following topics are covered in today's lesson:
Code optimization is the process of modifying working code to a more optimal state based on a particular goal. The fact that optimization takes place on working code is an important point; always perform optimizations on code after you get the code working. The type of optimization performed is dependent on the desired goal; code optimization can be divided into three distinct types, which are based on the needs of the developer:
Maintainability optimization is performed to help make code more manageable in the future. This type of optimization is usually geared toward the structure and organization of code, rather than modifications of the algorithms used in the code. In general, maintainability optimization involves a programmer studying the code at large and making changes to help other programmers understand and modify the code in the future.
If you haven't guessed, maintainability optimization doesn't rank very high on the list of important optimizations used by game developers. It's still important to organize your code and enforce some structure, but just don't let maintainability optimization become an overriding concern.
Another popular optimization is size optimization, which involves making changes to code that result in a smaller executable class file. The cornerstone of size optimization is code reuse, which comes in the form of inheritance for Java classes. Fortunately, good OOP design strategies naturally favor size optimization, so you will rarely need to go out of your way to perform this type of optimization. For example, it's just good design practice to put code that is reused a few times in a method. In this way, most size optimizations naturally take place during the initial code development.
Although not entirely crucial, size optimization can't be completely ignored in regard to Java game programming. This is because the size of your compiled Java classes will directly impact the amount of time it takes your game to load and initially execute. If, however, you leverage as much of the standard Java API code as possible and reuse code by deriving from other classes, you're probably doing enough for the cause of reducing class size.
And now, introducing the real subject of today's lesson: speed optimization. Speed optimization is without a doubt the most important aspect of game development after the game is up and running correctly. Speed optimization includes all the techniques and tricks used to speed up the execution of code. Considering the performance problems inherent in Java, speed optimization takes on an even more important role in Java than in other languages such as C and C++. Because the Java compiler has the last word on how code is generated, most speed optimizations will be performed with the compiler in mind.
The rest of today's lesson focuses on issues of speed optimization and how to get the best performance out of your Java code. At times, you will sacrifice the other areas of optimization for the sake of speed. In most cases, this sacrifice is entirely acceptable, even expected, because the organization of the code and size of the executable classes won't matter much if your game is too slow to play.
All optimizations begin and end with the Java compiler. If you don't understand the compiler, you're largely guessing at which optimizations will have a positive effect on your code. So let's take a look at the JDK compiler and see what role it plays in turning out speedy Java bytecodes.
A bytecode is a Java term referring to the intermediate processor-independent code generated by the Java compiler. Bytecode executables (classes) are interpreted by the Java runtime system.
| Note |
Third-party Java compilers are turning up and will continue to turn up that outclass the JDK compiler in regard to speed optimization. Nevertheless, the JDK compiler is the standard Java compiler and currently the most reliable. |
The JDK compiler (javac) includes a switch for generating optimized Java bytecode executables: -O. In release 1.0 of the JDK, this switch results in only two optimizations taking place: inline methods and exclusion of line numbers. The first of these optimizations is the only one that affects the speed of the executable bytecode; final, static, and private methods are inlined by the compiler, resulting in less method call overhead.
Method inlining is the process of replacing each call to a method with the actual method code. Inlining can often increase the size of the resulting class file, but it can help improve performance.
The second optimization performed by the JDK compiler results in the exclusion of line number information from the executable class file. This is a size optimization and does nothing in terms of helping speed up the code.
As you can see, the JDK compiler does little for you in regard to optimization. This basically means that you need to plan on doing a lot of optimization by hand. A future release of the JDK should (I hope) improve this situation, but you can't afford to stand around waiting for miracles-you've got games to write!
Now that you understand what the JDK compiler does (or doesn't do) for you in regard to optimization, it's time to focus on the Java runtime system. By examining the runtime system, you can get an idea of how fast certain types of code run and make smarter decisions about the way you write Java code. What do I mean by examining the runtime system? Well, I mean running different types of code and timing each type to see how the speeds match up. This operation gives you a very realistic look at how code differs in terms of execution speed and consequently gives you a place to start making appropriate code optimizations.
The speed of an operation is often referred to as the cost of the operation. Code optimization can almost be likened to accounting, in which you try to keep from blowing a performance budget with your code costs. As if optimization weren't tedious enough as it is, I had to make a reference to accounting! Anyway, Jonathan Hardwick performed a very neat analysis on the cost of common Java operations on various systems, the results of which I've included in Tables 20.1 through 20.3. These tables contain approximate times in microseconds for common Java operations. Incidentally, the systems used to perform the cost analysis were a Sun Sparcstation 5 running Solaris, an AMD 486 DX4-120 running Windows 95, and an AMD 486 DX4-120 running Linux 1.2.13.
In terms of speed optimization, cost refers to the speed
required to perform an operation.
Table 20.1. The costs of Java variable accesses.
| Description | Operation | |||
| Method variable assignment | i = 1; | |||
| Instance variable assignment | this.i = 1; | |||
| Array element assignment | a[0] = 1; |
Table 20.2. The costs of increment with Java data types.
| Description | Operation | |||
| Byte variable increment | byte b++; | |||
| Short variable increment | short s++; | |||
| Int variable increment | int i++; | |||
| Long variable increment | long l++; | |||
| Float variable increment | float f++; | |||
| Double variable increment | double d++; |
Table 20.3. The costs of miscellaneous Java operations.
| Description | Operation | |||
| Object creation | new Object(); | |||
| Method invocation | null_func(); | |||
| Synchronized method | sync_func(); | |||
| Math function | Math.abs(x); | |||
| Equivalent math code | (x < 0) ? -x : x; |
These tables point out lots of interesting information regarding the performance of Java code. From Table 20.1, it's readily apparent that method variables are more efficient to use than instance variables. Furthermore, you can see that array element assignment is slower than method variable assignment due to the fact that Java performs bounds checking operations whenever an array element is accessed. Keep in mind that this table isn't meant as an argument to get rid of all your class member data. Rather, think of it as providing insight into making those decisions in which the design could go either way.
Table 20.2 shows timing data relating to the use of the standard Java data types. As you might have expected, the two 32-bit data types, int and float, showed the best performance because the tests were performed on 32-bit systems. It is interesting to note that the performance difference between using an int over a byte, short, or long is much more significant than for using a float over a double.
Even though the floating-point types show comparable performance to the integer types, don't be misled about using integer math over floating-point math. This timing table reflects only an increment operation, which is much different than more complex operations performed in the context of a game. Integer math is much more efficient than floating-point math. So use the table as a measure of the relative speeds among integer types, and then try to use integer math throughout your code.
Table 20.3 focuses on a few miscellaneous operations that are worth thinking about. First, it shows the high cost of creating an object. This should serve as an incentive to eliminate the creation of temporary objects within a loop where the creation occurs over and over. Rather, you can place the temporary object above the loop and reinitialize its members as needed inside the loop.
Table 20.3 also shows the dramatic performance costs of using a normal method versus a synchronized method. Even though synchronization is very important in multithreaded programming, this should be some encouragement to minimize the usage of synchronized methods in games.
Finally, Table 20.3 shows you how using the standard Java math methods can sometimes be a burden. Even something as simple as taking the absolute value of a number imposes much greater performance costs when you call the Math.abs method, as opposed to inlining the equivalent code yourself.
The biggest mistake you can make in regard to optimizing your game code is trying to optimize all the code. Being smart about what code you attack is crucial in not spending years trying to improve the performance of your game. More important, it's a well-established fact that a relatively small portion of code is usually responsible for the bulk of the performance drain. It's your job to isolate this code and then focus your optimization efforts accordingly.
| Warning |
Don't attempt to optimize code as you write it. Many programmers have the tendency to think they can do it all the first time through, which includes developing perfectly optimized error-free code. If you truly think you are capable of filling this tall order, then be my guest. Meanwhile, the rest of us mere mortals have to contend with our fair share of mistakes, even without worrying how optimized a piece of code is. Throw in the complexities of trying to optimize code that doesn't even work yet, and you're setting yourself up for disaster. In all fairness, it's usually okay to make minor optimizations that don't sig-nificantly impact the structure of your code; just don't get carried away. |
Fortunately, isolating problem code isn't all that difficult if you use the proper tools. The most useful tool in finding bottlenecks in your code is a profiler. A profiler's job is to report on the amount of time spent in each section of code as a program is executing. The Java runtime interpreter has an undocumented built-in profiler that is easy to use and works pretty well. To use the runtime interpreter profiler, simply specify the -prof option when using the interpreter, like this:
java -prof Classname
Classname is the name of the class you want to profile. Of course, this technique doesn't work too well for applets, because they must be run within the context of the applet viewer tool or a browser. Fortunately, you can use the profiler with applets by altering the arguments to the interpreter a little, like this:
java -prof sun.applet.AppletViewer Filename
In this case, Filename is the name of the HTML file containing a link to your applet. When you finish running the applet, the interpreter will write a file named java.prof to the current directory. This file contains profile information for the applet you just ran.
To get an idea of what kind of information the Java profiler generates, check out Listing 20.1, which contains a few lines of profile information generated for the Traveling Gecko sample game. I've cleaned up the listing a little by hand just to make it easier to read.
Listing 20.1. A partial profile listing for the Traveling Gecko sample game.
count callee caller &nbs p; time
25261 java/util/Vector.size() SpriteVector.testCollision( 19
22780 java/util/Vector.elementAt(I) SpriteVector.testCollision( 38
20258 java/awt/Rectangle.intersects() Sprite.testCollision(LSprite;) 56
20258 Sprite.getCollision() Sprite.testCollision(LSprite;) 4
20258 Sprite.testCollision(LSprite;) SpriteVector.testCollision( 102
10360 Sprite.getPosition() SpriteVector.update()V 2
4075 java/lang/Object.<init>() java/awt/Rectangle.<init>(IIII) 0
3800 sun/awt/image/Image.getImageRep(II) sun/awt/win32/Win32Image.getImage 60
As you can see, the profile information is broken down into four columns. The first column specifies how many times a particular method was called, and the second column states the name of the method. The third column specifies the calling method, the one that invoked the method in question. Finally, the fourth column specifies the relative amount of time spent in the method during each call. The larger this number is, the more costly the method.
You can easily use this information as a guide to determine the code on which to focus your optimization efforts. The methods appearing at the top of the list should receive much greater attention, because they are being called far more times than methods farther down in the list. Making small performance gains in a method that is being called 20,000 times will have a much greater impact than speeding up a method that is called only a couple of hundred times. The cool thing is that you can try different optimizations and then run the profiler again to see whether the relative times have changed. This is a very practical, if somewhat time-consuming, way to make great strides in speeding up your games.
Now that you've isolated the code that is making your game crawl, it's time to look into exactly what optimizations you can perform to speed things up. The rest of today's lesson is aimed at different techniques you can apply to code that you know could stand some improvement. You won't always be able to optimize every piece of problem code; the goal is to make big dents in the areas that can be optimized.
| Note |
Incidentally, make sure that you have already tried your game with compiler optimizations turned on (the -O option). I know it's not much, but it's free! |
Many C/C++ programmers have traditionally resorted to assembly language when the issue of performance is raised. As a Java programmer, you don't have this option. This is actually a good thing, because it forces you to take a closer look at your design approach instead of relying on heavier processor dependence to solve your problems. What the assembly heads don't realize is that much more significant gains can be made by entirely rethinking an algorithm than by porting it to assembly. And trust me, the amount of time spent hand-coding tedious assembly could easily result in a leaner, more efficient algorithm.
This same ideology applies to Java programming. Before you run off writing native methods and expanding loops to get every little ounce of performance, which you'll learn about in a moment, take a step back and see whether the algorithm itself has any weaknesses. To put this all into perspective, imagine if programmers had always resorted to optimizing the traditional bubble sort algorithm and had never thought twice about the algorithm itself. The quick sort algorithm, which is orders of magnitude faster than bubble sort without any optimization, would never have come about.
I kind of hate to recommend them, but the truth is that native methods (methods written in C or C++ that can be called from Java code) are typically much faster than Java methods. The reason I'm reluctant to promote their use is that they blow the platform independence benefit of using Java, therefore limiting your game to a particular platform. If platform independence isn't high on your list, however, by all means look into rewriting problem methods in C.
Inline methods, whose bodies appear in place of each method call, are a fairly effective means of improving performance. Because the Java compiler already inlines final, static, and private methods when you have the optimization switch turned on, your best bet is to try to make as many methods as possible final, static, or private. If this isn't possible and you still want the benefits of inlined code, you can always inline methods by hand: just paste the body of the method at each place where it is called. This is one of those cases in which you are sacrificing both maintainability and size for speed. The things we do for speed!
There might be times when you are using a standard Java API class for a few of its features, but the extra baggage imposed by the class is slowing you down. In situations like this, you might be better off writing your own class that performs the exact functionality you need and no more. This streamlined approach can pay off big, even though it comes at the cost of rewriting code.
Another similar situation is when you are using a Java API class and you isolate a particular method in it that is dragging down performance. In this situation, instead of rewriting the entire class, just derive from it and override the troublesome method. This is a good middle-of-the-road solution because you leverage code reuse against performance in a reasonable manner.
An established trick up the sleeve of every experienced game programmer is the look-up table. Look-up tables are tables of constant integer values that are used in place of time-consuming calculations. For example, a very popular type of look-up table is one containing values for trigonometric functions, such as sine. The use of trigonometric functions is a necessity when you are working with rotational objects in games. If you haven't noticed, trigonometric functions are all floating-point in nature, which is a bad thing. The solution is to write an integer version of the desired function using a look-up table of values. This relatively simple change is practically a necessity considering the performance hit you take by using floating-point math.
Moving along into more detailed optimizations, you can often find unnecessary evaluations in your code that are serving only to eat up extra processor time. The following is an example of some code that unnecessarily performs an evaluation that acts effectively as a constant:
for (int i = 0; i < size(); i++)
a = (b + c) / i;
The addition of b + c, although itself a pretty efficient piece of code, is better off being calculated before the loop, like this:
int tmp = b + c;
for (int i = 0; i < size(); i++)
a = tmp / i;
This simple change could have fairly dramatic effects, depending on how many times the loop is iterated. Speaking of the loop, there's another optimization you might have missed. Notice that size() is a method call, which might bring to mind the costs involved in calling a method that you learned about earlier today. You might not realize it, but size() is being called every time through the loop as part of the conditional loop expression. The same technique used to eliminate the unnecessary addition operation can be used to fix this problem. Check out the resulting code:
int s = size;
int tmp = b + c;
for (int i = 0; i < s; i++)
a = tmp / i;
Sometimes you might be reusing a costly subexpression without even realizing it. In the heat of programming, it's easy to reuse common subexpressions instead of storing them in a temporary variable, like this:
b = Math.abs(a) * c;
d = e / (Math.abs(a) + b);
The multiple calls to Math.abs() are costly compared to calling it once and using a temporary variable, like this:
int tmp = Math.abs(a);
b = tmp * c;
d = e / (tmp + b);
One optimization that is popular among C/C++ game programmers is loop expansion, or loop unrolling, which is the process of expanding a loop to get rid of the overhead involved in maintaining the loop. You might be wondering exactly what overhead I'm talking about. Well, even a simple counting loop has the overhead of performing a comparison and an increment each time through. This might not seem like much, but with game programming you could well end up in the position of clawing for anything you can get!
Loop expansion, or loop unrolling, is the process of expanding a loop to get rid of the inherent overhead involved in maintaining the loop.
Loop expansion basically involves replacing a loop with the brute-force equivalent. To better understand it, check out the following piece of code:
for (int i = 0; i < 1000; i++)
a[i] = 25;
That probably looks like some pretty efficient code, and in fact it is. But if you want to go the extra distance and perform a loop expansion on it, here's one approach:
int i = 0;
for (int j = 0; j < 100; j++) {
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
a[i++] = 25;
}
In this code, you've reduced the loop overhead by an order of magnitude, but you've introduced some new overhead by having to increment the new index variable inside the loop. Overall, this code does outperform the original code, but don't expect any miracles. Loop expansion can be effective at times, but I don't recommend placing it too high on your list of optimization tricks.
Today you learned about a somewhat murky area of Java game development: code optimization. You began the lesson by learning about the fundamental types of optimization, including the type that game programmers are mostly concerned with: speed optimization. You then learned about the optimizations (or lack thereof) provided by the JDK compiler. From there, you got a little dose of realism by looking into the timing costs of common Java operations. Finally, you finished off the lesson with an in-depth look at some practical code optimizations you can apply to your own games.
Incidentally, after going through today's lesson, you might be wondering how well the sample code throughout the book is optimized. I'm sorry to report that it is optimized very little, mainly for the sake of keeping it easier to follow. It ends up that optimized code is often much harder to understand, so I opted to err on the side of clarity. Now that you're disillusioned with my coding practices, prepare to turn your attention toward tomorrow's lesson, which is putting together a Java game programming toolkit.
| Q | Do all games require lots of code optimization to run at acceptable speeds? |
| A | No. First, many games simply aren't speed-intensive, which immediately eliminates the need for any optimization. Second, even those games that could benefit from optimization will often run at reasonable speeds without it. The sample games you've studied in this book are very good examples of this fact. |
| Q | I keep hearing about just-in-time compilers. How will they impact the whole optimization issue? |
| A | Just-in-time compilers (Java compilers that turn bytecodes into platform-dependent code at runtime) are music to the ears of Java game programmers, because they will undoubtedly increase the speed of all Java code by an order of magnitude. Even so, Java game programmers will likely use the new speeds afforded by just-in-time compilers to add more complexity to their games. When this happens, you will still be left optimizing your code. Our greed seems to keep us from winning! |
| Q | I really enjoy hacking through cryptic bytecodes; is there anything else I can do to speed up my Java code? |
| A | But of course, the Java class file disassembler is the tool for you. The disassembler (javap) comes standard with the JDK, and it enables you to see the bytecodes generated for a class. Just use the -c option, and you'll get complete bytecode listings for each method. You can then use these listings to study the intricate results of your source code optimizations. |
The Workshop section provides questions and exercises to help you with the material you learned today. Try to answer the questions and at least go over the exercises before moving on to tomorrow's lesson. You'll find the answers to the questions in appendix A, "Quiz Answers."