Writing High-Performance Graphical Java Components

Harold is a founding developer at Inxight Software Inc. He can be contacted at [email protected].

Java makes writing applications and applets easy, yet there are various pitfalls that I have encountered on the path to a truly profitable application. How do you go from seeing the benefits of simplicity, pointer avoidance, and garbage collection to building a commercially viable application? In this article, I offer some tips and tricks for writing high-performance, computationally intensive, graphical Java components. These techniques are based on my experience writing the Hyperbolic Tree for Java, a commercially available Java component that animates the display of hundreds of objects.

Hyperbolic Tree for Java (HTJ) displays, in a graphical way, large hierarchical data structures on the order of a few thousand nodes. The effect of the Hyperbolic Tree is a fish-eye view of the tree; see Figure 1. John Lamping and Ramana Rao wrote the original Hyperbolic Tree for Java component, spending a few days to port the original C++ code to Java. I spent another month or two making the code commercially ready. The HTJ API and product has been evolving since it was first released commercially in December of 1996. Complete details on the concepts and implementation of the Hyperbolic Tree are available at http://www.acm.org/ sigchi/chi95/ Electronic/documnts/papers/jl_bdy.htm.

The Hyperbolic Tree for Java makes heavy demands on the graphical display engine for several reasons. A key concept of the HTJ component is to animate transitions of the dataspace to help maintain perceptual continuity when moving from one place to another. A web browser, in contrast, makes discontinuous jumps, which has created the phenomenon of "getting lost in hyperspace." Also, since we are not using traditional Euclidean space, we must do a fair amount of complex math operations for each drawing.

The Hyperbolic Tree paints on the order of 50 nodes and 500 links between the nodes. The nodes have less space to be rendered as we get closer to the edge of the circle, so we also have to compute whether or not to display that node. Because of this, only 50 nodes are rendered even though the dataset may be 5000. Before painting any nodes, each of the thousands of nodes is laid out in hyperbolic space, and that layout is then mapped using the Poincaré projection from hyperbolic space onto a unit circle, which is then mapped onto the display.

To further illustrate the calculation size, each node involves many double floating-point calculations, including four square root, 57 multiply/divide, and 42 addition/subtraction operations. Each link involves an additional set of calculations, including 48 multiply/divide, 52 addition/ subtraction, two square root, two arctangent, two sine, and two cosine operations.

These demands on the Java Virtual Machine bring us to the edge of Java performance, and have forced us to deal with the wide variance in JVM performance. Even on the same computer hardware and the same operating system, the performances of different JVMs can vary by a factor of 5, 10, or even 30. Developers of graphical Java components must deal with this issue in one way or another, especially for animated graphics. What are the possible solutions?

Wait Until JVMs Improve

Waiting until Java performance improves may sound like a facetious solution, but for your particular application, you may require more performance than Java can currently support. In the three years I've been coding for Java, the performance has been steadily increasing, so your wait may not be that long. At the March 1998 JavaOne conference, I witnessed the HotSpot Java compiler in operation. It was an order or two of magnitude faster than the fastest JVM around today. The HotSpot compiler was released to Sun licensees in December 1998, and may already be available. In addition, the hardware is also getting faster, so the two trends are conspiring to meet your needs, which may exceed what Java can currently support.

Stating Minimal Browser Requirements Up Front

Stating minimal browser requirements up front may seem like a cop out, but if users understand what the minimum requirements for use of your component are, they will be much less likely to come back to you with complaints. Even if you do implement solutions that are supported on a variety of JVM abilities, you should still state your minimum requirements up front.

In the Hyperbolic Tree, we could draw all the nodes all the time. But nodes toward the edge of the circle have so little drawing space, they begin to disappear anyway, so we cease traversing the tree when we reach a specified limit where we believe the node has insufficient space to be displayed properly. If you can get away with not drawing something, don't draw it.

Simplify Drawing Where Possible

Another simplification we made was to draw straight lines instead of arcs during animation. The number of computations that are required to draw arcs for the Hyperbolic Tree is 43 multiplication/division, 45 addition/subtraction, two square roots, two arctangents, and four sin/cosines more than drawing a simple line. So we save significantly by using straight lines instead of arcs during animated transitions. When the display stops moving, we take advantage of the extra time available to draw our arcs. Look for the simplifications you can make when you are animating your display.

Use a Time-Bound Display Technique

A good way to address the issue of performance variances and performance inadequacies is to provide an upper bound for the time you are willing to take to draw an image. This is an especially useful technique in animation, where the time-bound display allows you to paint as many objects as possible, usually the most important ones, in a frame before time runs out. The human eye will forgive absent detail when the picture is moving. HDTV, MPEG, and other visual animation standards also take advantage of this fact by displaying less detail for highly dynamic displays than they do for static scenes.

Listing One illustrates how we implemented such a scheme in the Hyperbolic Tree. We are painting as many nodes and their children as we can in 200 milliseconds to maintain a minimum animation rate of five images per second. There are four classes: TimeBoundPainter, Pending-TreeGraphics, Queue, and Node. The Queue class describes a simple queue implementation, and Node is a representation of a tree, in that a Node has an array of Nodes as children. TimeBoundPainter drives the painting of a Queue. The Queue consists of objects of the class Pending-TreeGraphics, which represents the graphical objects in the tree that need to be painted.

The time-bound display technique is centered in the TimeBoundPainter class. The method paintTree is called within your animation loop. This method sets a deadline of when to stop painting by simply adding 200 milliseconds to the current time. This deadline is passed to the method runQueue, which processes the Queue of PendingTreeGraphics objects in a loop. Within that loop, runQueue first checks if the painting deadline has run out. If the deadline has run out, painting is halted, thus ensuring an animation rate of at least five frames per second.

Compression and Obfuscation

With most modem speeds still below 56K, the size of your application can be very important, especially when your application is being executed on demand as an applet in a web page. To decrease the size of your application, you can use both compression and obfuscation.

Not all browsers support compression. However, versions 4 of Netscape and Internet Explorer both support compressed ZIP and JAR files. Compressed classes require a small amount of decompression time after download, but the increased download speed will usually more than make up for the difference. Make sure to test your compressed JAR files, because in rare cases, compression will cause some JAR files to load improperly.

Another way to decrease the size of your Java application is through the use of obfuscation. Java class files leave all of your symbol information intact, which makes them easily decompiled into readable source code. A Java obfuscator converts all of your class, field, and method names into three, two, and even one character symbols. The primary intent of obfuscation is to make your code less readable, but a side benefit of obfuscation is that it can reduce the size of your class substantially. Obfuscation has reduced the Hyperbolic Tree class files in size by 20 percent.

There are some free Java obfuscation programs available on the Internet, including HashJava (http://www.sbktech .org/hashjava_old.html) and Jobe (http:// meurrens.ml.org/ip-Links/Java/ CodeEngineering/jobe-doc.html). These obfuscators may not work with the JDK 1.2. The company 4thPass (http://www. 4thpass .com/) offers a product called SourceGuard that does JDK 1.2-compliant obfuscation, and obfuscation is included as part of JBuilder 2.

Optimizing Code

One of the first temptations when addressing the performance issue may be to look at code optimization. While your intentions may be good, the results can be counter productive. I've spent many hours attempting to remove object allocations so that the garbage collector would be activated less frequently, with the only result being unwieldy code with a relatively small performance boost. Your efforts may only serve to obfuscate your source code, making it more difficult to adapt to future circumstances.

Because code optimization can be bad for the health of your source code, make sure you focus your efforts appropriately. The rule of thumb in the industry is that 80 percent of the execution time is spent in 20 percent of the code. Some say that the 80/20 rule should be the 90/10 rule. A 50 percent performance improvement in a segment of code that only runs 10 percent of the time will only yield an overall program performance of 5 percent. The best ways to find the bottlenecks that run 80 or 90 percent of the time are through the Java profiler, which is included in the JDK. You may also choose to use the various Java performance tools such as OptimizeIt (http://www.optimizeit.com/) or VisualQuantify.

Given this caveat, there are some areas that are useful to be aware of when looking at optimizing Java source code. Java's String class is an unusual beast. In Java, Strings are immutable. When you add two strings together, Java creates an entirely new String object. This simplifies the writing of code, but it can be a performance disaster in a tight loop. Use the StringBuffer class when constructing complex strings, or when the String processing will be repetitive. This will keep your garbage collector from having to pick up too many wasted Strings.

Thread synchronization is essential for correct operation when using shared resources, but the unnecessary use of the synchronized keyword does not come for free. Although the wizards at Sun have claimed that the overhead of making a method synchronized will go down in future releases of the JDK, it is quite costly in JDK 1.1 and earlier releases. Use the synchronized keyword only when necessary. Also, be aware that even though you may not have used synchronization yourself, the collection classes such as the Vector and Hashtable provided by the JDK are synchronized, so you are paying that overhead whether you need it or not with these classes.

Although garbage collection immensely simplifies the writing and debugging of your code, the garbage collection process is not free when it comes to performance. Having a garbage collector should not become an excuse for sloppy coding, so be frugal when allocating your objects. And as is the case when using the StringBuffer class, reuse space when possible rather than allocating new objects.

Conclusion

The Java universe is changing rapidly, perhaps more rapidly than the rest of the computer industry. There are several pitfalls that can be common to those who attempt to create a component that will take its place in a profitable ecological niche, the most important of these being performance. I hope that these various tricks help you make a commercially successful Java graphical component.

DDJ

Listing One

// An example of a time bound graphics painted in Java for a tree hierarchy
import java.util.Vector;
public class TimeBoundPainter {
  void paintTree(Node node) {
    runQueue(queueTreeGraphics( node ),
        200 + java.lang.System.currentTimeMillis());
  }
  static Queue queueTreeGraphics ( Node node ) {
    Queue q = new Queue();
    q.insert(new PendingTreeGraphics( node ));
    return q;
  }
  static Queue runQueue(Queue q, long limit) {
    while (q.isEmpty() ? false
              : limit == 0 ? true
                  : java.lang.System.currentTimeMillis() <= limit)
      ((PendingTreeGraphics) q.removeFirst()).doQueued(q);
    return q;
  }
}
class PendingTreeGraphics {
  Node node;
  double limit;

  PendingTreeGraphics( Node in_node ) {
    node = in_node;
  }
  void doQueued( Queue q ) {
      Node kids[] = node.children ;
      for (int i = 0; i < kids.length; i++) {
        Node kid = kids[i];
        paintLink( node, kid ) ;
        q.insert(new PendingTreeGraphics(kid));
      }
    paintNode( node );
  }
  void paintNode( Node node ) {/* node painting code */};
  void paintLink( Node parent, Node child ) {/* link painting code */};
}
class Queue {
  Vector entries;

  Queue() {
     entries = new Vector(8);
  }
  boolean isEmpty() {
    return entries.isEmpty();
  }
  Object removeFirst() {
    Object result = entries.firstElement();
    entries.removeElementAt(0);
    return result;
  }
  void insert( Object entry ) {
    entries.insertElementAt(entry, 0);
  }
}
class Node {
  Node[] children;
}

Back to Article