Synchronizing Threads in Java-Based Games

Author: by Paul Tyma

The speed at which Java has exploded onto the web (and into computing in general) is nothing less than astounding. And why not? It's sexy, well designed, and provides a relatively simple way to infuse web pages with live content. For advanced applications, the language is nearly as flexible as C, but its design methodology smushes in buckets of grace and elegance.

Game developers tend to be on the forefront, so you would think they would embrace Java with an unrelenting fervor. The platform independence factor is quite alluring. Of course, the game industry has traditionally targeted only a few choice platforms. At first glance, there doesn't seem to be much of a game market for Sun workstations or AIX boxes, but maybe that's because no one ever made the expensive commitment to try it. Programming games in Java may induce latent game players (who are cursed with some nonstandard "productivity" machine on their desk) to toast a few aliens with workstation power.

If all this sounds beyond wonderful, heck, why program in anything else? Well, unless you've never heard of Java or you're devout board game programmer, you know the answer--Java's performance is not exactly awesome. In fact, its rather on the slow side. O.K., actually, it stinks.

The current canonical form for creating Java programs works in two steps. Java source code is written much like any other popular high-level language. It's then run through a Java compiler that produces Java bytecode. Bytecode is nothing more than a machine language for the Java virtual machine. Compared to machine code of real machines, it is a tad higher-level but still retains the look and feel of any given assembly language code.

From here, the bytecode is usually run through an interpretive Java virtual machine. Hence, our first attempt at speed is blocked. Although bytecodes are simple enough that interpreters are easy and efficient to write, the simple fact that they are interpreted is an ominous idea. The idea of interpretation brings forth thoughts of turtles, snails, and booting Windows NT on a 2MB 386. On top of that, the Java run time is intent upon performing run-time safety checks for every program. This includes type checking, array bounds checking, and in the case of applets, disk and network access restrictions. All this checking ends up just slowing things down further.

Of course, all these aspects pertain to running Java code. However, there's a large caveat to running Java programs. No Java program ever runs completely in Java. Remember the big excitement of platform independence Java purports? It's kind of an amazing idea that if you write drawLine in your Java program, the Java run time will know how to draw a line regardless of what machine, operating system or windowing system it's running on.

Imagine that, regardless of the architecture, the video's memory organization, the video chipset, the operating system, and windowing system, Java is omniscient and always knows how to draw your line. Unfortunately, its not quite all that hallowed. The real story is that Java doesn't have a clue about lines, graphics, or your system in general. What Java does know is that the system has resources to act upon itself. In other words, every windowing system has an API that knows how to draw a line in its own environment. So all Java really needs to know is where that API is.

The good news is that every time Java needs to do something fancy (that is, system dependent), it simply asks the operating system to do the operation. Of course, the pieces of the operating system that perform the operation are written in compiled C or C++ code. Write a Java for loop that draws a thousand lines on the screen. Only the looping code is running in Java, while the actual line drawing is running in compiled C or C++.

This is good news of a kind for Java in general, but still not really a boon for game programmers. Usually, operating system graphics routines are written very generically. They usually need to handle many video modes and can take many parameters. All this reusability adds overhead to the drawing of your line. What's worse is that across architectures, the unpredictability of line drawing (that is, graphics in general) performance is exacerbated.

Our speed problem is somewhat twofold. All the Java code will run interpreted, providing its expected leisurely output and all the graphics routines are at worst slow and at best unpredictable. Some good news is on the horizon. Several companies have already released just-in-time compilers for the Java environment.

Just-in-time compilers sit on the client machine and wait for the bytecode to be loaded (from network or disk). The compiler will then compile the bytecode into native machine language for the client architecture. Subsequently, your Java programs run natively (not interpreted). Initial releases of the just-in-time compilers are rather boring and don't provide the fantastic speed increases that were anticipated. Academics have been working on these compilers for several years and have developed many powerful optimizations. The developers of these initial Java releases were probably more interested in getting the compilers to market instead of working out the complexities of making them super fast. The good news is that subsequent releases will probably start providing serious performance boosts.

Solving the graphics performance problem won't be so transparent. More likely, you'll be involved in using (or developing) proprietary graphics libraries to use with your Java program. How well this will fit together remains to be seen. Writing your own super-speed graphics routines in C and then interfacing them to Java is not a solution. You'll need to write your routines for many different platforms, and you need your users to obtain your libraries.

A solid solution might be to distribute your company's Brand X Graphics Lib on CD-ROM (hence a solid method for charging for your work) and allow your games to be downloaded off the Internet. In other words, you develop a standard graphics library for all your games and distribute it the hard way; all your Java games then float in over the Net but can use these local libraries.

Applet Optimizations

Regardless if you're running interpretive or just-in-time compilers, you must take into account some definitive design issues when designing applets. Actually, this also applies to applications, because often the same model is used. It is amazing how silly 90% of all applets in the world are currently written. Consider Listing 1, a subset of the canonical form for an applet.

The run method is executed by a thread you create. One thing this does is call the repaint method, which "asks" the browser to call your paint method (actually repaint asks the browser to call your update method, which then calls paint, but for simplicity, we'll leave out the update step). For the Java gurus screaming over the previous sentence, repaint really asks the Java environment within the browser (not exactly the browser) for paint, but it's more intuitive to think of the browser as being in charge. Repaint does not eventually call paint. Repaint is an asynchronous method call; it simply sends a message to the browser asking to get paint called. The run method then sleeps for 100 msecs, hoping that within that time,paint will get called.

Why can't you call paint yourself? Well, you can if you happen to know what that graphics context parameter is. The Graphics G parameter is given to you by the browser and is your little piece of the screen. You can save this object reference the first time the browser enters paint, but (at least with Netscape) the reference is soon to change. After several iterations, the browser decides that the graphics context you have just isn't that good anymore and will create a new one for you. Normally, you wouldn't care, but since you have a stored reference to the old one, it kind of foils your plans. For now, it's probably best to stick to the repaint/paint model handed to you.

The repaint/paint system has two threads. One you created in your run method (which calls repaint and does some sleeping) and one that comes from the browser and enters your paint method and draws what you want drawn. Since the thread is coming from the browser (we'll call this thread the updater thread), you should not assign it any significant processing (that is, paint should do the minimum it needs to get your applet drawn). All significant work should be pushed into your run method. The browser has better things to do with its threads than worry about drawing your applet. The same thread is in charge of all applets running on the page. You can prove this to yourself by adding a Thread.sleep to one of your applet's paint methods. All applets will slow down as you increase the sleep time.

Back to our canonical applet, we said there are two threads running in the Listing 1 code--the updater and your run thread--Thread.sleep is used to slow down the run thread so the updater has a chance to wake up and call your paint method. In other words, Thread.sleep is being used as synchronization between the two threads, which should make any self-respecting operating systems professor reel in inscrutable pain. This is an ineffective (another appropriate word would be "ridiculous") method of thread synchronization, and what's worse is it may simply fail.

Usually, applet programmers who want maximum speed out of their applets lower the sleep value as much as they can. Why not just remove it or sleep for 0 msecs? This doesn't work because we have two threads running. Once a repaint is issued, the updater needs to enter the CPU. Unfortunately, without any form of synchronization, it's likely additional repaints will get sent before the updater can call paint.

These repaints are wasted (that is, in this sense, repaints do not queue). Also, since the CPU is so busy sending wasted repaints, there is even less chance the updater will get a chance to call the paint method. Typically, there is a compromise value you can have the run method sleep for. It provides just enough time for the updater to come in and call paint. This method attempts to approximate a one-for-one calling sequence of repaint-paint-repaint-paint, and so on.

To throw a final wrench into all this, once you spend countless compiles tweaking your sleep value until you find just the perfect value, as soon as your applet runs on another machine, your value will be wrong. Because graphics systems and CPU speeds vary, finding the correct value for one machine could be incorrect on another. In other words, if you're using Thread.sleep for thread synchronization, you have a problem.

Before presenting a solution, Thread.sleep is a great way to slow down applets and threads in general. Most applets don't need every bit of CPU power or need to be slowed down a bit, and Thread.sleep provides a convenient vehicle for this purpose. However, Thread.sleep is a pitiful attempt at thread synchronization.

An Attempt at Synchronization

Hopefully, you believe that Thread.sleep as a thread synchronization technique is nothing short of silly. What's the answer? Ideally, we'd like to insure a one-to-one calling sequence of repaint and paint. We never want two repaints or paints to get called in a row. How about the code shown in Listing 2?

Pretty slick, huh? Now, the run method calls repaint, then sits happily in a loop until the browser comes in and calls paint. This works, except that we are wasting a whole lot of CPU power just waiting. So, this code isn't really the best solution. What we need is a way to shut down the run thread (without it using any CPU power) right up until the paint method completes.

Real Synchronization

In their omniscience, the designers of Java have provided solid thread synchronization primitives to handle just such a situation. Two of the more beloved are the wait and notify keywords. In short, the wait keyword allows a thread to wait for some event (while waiting, a thread uses no CPU power). The notify keyword allows a thread to notify other threads that their condition is now ready. Reworking our code from Listing 2, we get the code shown in Listing 3.

We've removed Thread.sleep and added just a few keywords. The synchronized method modifiers indicate that a thread must obtain a lock on the current object (in this case, your applet object) before it may enter the given method. Since we've synchronized the run and paint method, only one thread may be running in either of these methods at any given instant. As we've said, there are two threads in this model, and we are attempting to insure that they never run at the same time.

An apparent problem is that our run thread enters its while loop and never exits. If it never exits the run method, it will always own the lock, and no other thread may enter run or paint. If no other thread can enter paint, the browser can never paint our screen. Fear not, this is where wait comes in. When execution reaches the wait command, the thread blocks, effectively stopping execution. It also releases the lock it's waiting on (that is, your applet's lock). Since it has already issued the repaint method, we know that sometime in the near future the browser will come in and run paint (at least we're hoping really hard). When the browser's update thread does so, it obtains the lock on the applet object (which it can, since the run thread is waiting) and draws the graphics. As its final dying act, it performs a notifyAll, which wakes up all threads waiting on this lock. Finally, the updater thread exits the paint method releasing the lock.

At this point, the run method picks up where it left off and iterates its while loop again. The sequence of events is shown in Table 1.

More on Threads

Threads are funny things, and you have to watch them closely. For example, the instant after repaint is called, the run thread could get kicked out of the CPU and the updater could enter. However, run (so far) hasn't released the lock, so the updater would stop waiting to obtain the lock. Based on this assumption, run would then reenter the CPU and get to its wait. Regardless of the devious and potentially evil games the thread scheduler tries to play, this code is guaranteed to provide a one repaint call per one paint call paradigm. We are using established thread synchronization techniques to synchronize the two threads.

This code will attempt to swipe all available CPU power for the applet. This might not necessarily be a bad thing for a hot action game. However, all applets should be written with perfect synchronization (that is, with this method or another), but not all applets should eat all CPU power doing repaints. Slowing this applet down is as easy as putting a Thread.sleep before the repaint method call in the run method (which is Thread.sleep's true use). Also, browsers such as Hotjava, which are built completely inside the Java paradigm may take great offense at you monopolizing the CPU with the Java VM.

This model is clean in that it does not violate future plans for the repaint/paint methodology. You could probably make the synchronized keyword limited to a block inside the paint method if you had a significant amount of work that could be done without affecting the synchronization (that is, drawing to an offscreen buffer can be done anytime, but copying it to the screen needs to be synchronized).

Is it Feasible?

Developing strategy or board games in Java today is not only feasible but there are few reasons not to. Although putting games on web pages is sexy, coming up with feasible payment methods is a challenge. Of course, Java is a programming language and doesn't need to run off the web. You can certainly write your game in Java and still do the typical CD-ROM distribution (readable by many platforms).

If you are considering developing action games in Java and you're a risk taker, your best move could be to start soon. Taking in consideration your development cycle, your game might be ready just as the real just-in-time compilers hit the market. Get yourself a high-end machine to do your testing--the risk may be well worth it by tapping into the platform independent gaming market.



Paul Tyma, the lead author of Java Primer Plus (The Waite Group, 1996) is a PhD candidate in Computer Engineering at Syracuse University. He can be reached at [email protected].