A Practical Guide

Many useful techniques exist for optimizing a Java program. Instead of focusing on one particular technique, this article considers the optimization process as a whole. Authors Erwin Vervaet and Maarten De Cock walk readers through the performance tuning of a puzzle-solving program, applying an assortment of techniques ranging from simple technical tips to more advanced algorithm optimizations. The end result is a spectacular performance increase (more than a million fold) between the first working implementation and the fully optimized solution.

Most Java performance-related articles focus on the many techniques that programmers can employ to speed up their programs. At one end of the spectrum you can find descriptions of relatively simple programming idioms, like the use of the StringBuffer class. At the other end you find discussions of more advanced techniques, like the use of object caches. Instead of adding to this list of techniques, we'll present a practical example that combines them to speed up a puzzle-solving program.

The program we will develop and optimize calculates all possible solutions for the Meteor puzzle, a brain teaser consisting of 10 puzzle pieces, each a different color made up of five hexagons (six-sided polygons with each side of equal length). The puzzle board itself is a rectangular grid of 50 hexagons laid out in a 5-by-10 pattern. You solve the puzzle by covering the entire board using the 10 available pieces. A possible solution to this puzzle is shown in Figure 1.

Figure 1. A solution for the Meteor puzzle

As simple as finding this solution might seem, it is a non-trivial problem to implement in a computer program. Writing that program will be a refreshing change from the contrived examples you can find in many other Java performance-related articles. It allows us to illustrate a number of different optimization techniques and the ways of combining them. However, before we start optimizing, we first need to develop a working solution.